[C++ 算法模板] 图形存储 - 邻接矩阵

邻接矩阵

• 邻接矩阵相比于上一篇博客邻接表的讲解要简单得多

1. 数据结构，如果将二维数组 $g$ 定义为全局变量，那默认初始化应该为 $0$ ，如果题目中存在自环，可以做特判，$memset$ 初始化数组 $g$ 为 $0x3f3f3f3f$ 表示无穷大，$0$ 表示自环

// 邻接矩阵
int d[N]; // 存储每个顶点的度
int g[N][N]; // 邻接矩阵

2. 以下模板是无向图的邻接矩阵模板，如果改成有向图，和邻接表一样，不需要对称建边，比如有一条边是 $(1,3)$，则 $d[1]++,\ g[1][3]=1 $ 即可

// 输入边
while(m--) {
    int u,v;
    scanf("%d%d",&u,&v);
    // 邻接矩阵建边
    d[u]++,d[v]++; // 顶点u和顶点v度数+1
    g[u][v]=1,g[v][u]=1; // 互相可达,为0表示不可达(如果题目涉及自环可用memset初始化为0x3f3f3f3f表示不可达)
}

• 完整代码如下，注意代码采用无向图模板

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 图的存储-邻接矩阵

const int N=1e3+5;
const int M=(1e5+5)*2; // 无向图建边最大边数为题目最大边数*2

// 邻接矩阵
int d[N]; // 存储每个顶点的度
int g[N][N]; // 邻接矩阵

int main() {
	// 假设题目编号默认从1开始
	int n,m; // 存储顶点数和边数
	// 输入边
	while(m--) {
		int u,v;
		scanf("%d%d",&u,&v);
		// 邻接矩阵建边
		d[u]++,d[v]++; // 顶点u和顶点v度数+1
		g[u][v]=1,g[v][u]=1; // 互相可达,为0表示不可达(如果题目涉及自环可用memset初始化为0x3f3f3f3f表示不可达)
	}
	// 输出邻接矩阵
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			cout<<g[i][j]<<' ';
		}
		cout<<endl;
	}
	return 0;
}

• 关于邻接表和链式前向星的讲解在我的博客：【C++模板】图的存储-邻接表，手撕链式前向星，超详细代码注释

洛谷3643 图的存储

题目链接：B3643 图的存储 - 洛谷

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e3+10; // 最大顶点
const int M=(1e5+10)*2; // 最大边数

int n,m; // 顶点数和边数
int u,v;

// 邻接矩阵
int d[N]; // 存度数
int g[N][N]; // 邻接矩阵

// 邻接表
int h[N]; // h[i]:编号i的顶点的
int ne[M];
int e[M];
int idx; // 建树因子

// 链式前向星(头插法)
void add(int a,int b) {
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int main() {
	cin>>n>>m;
	memset(h,-1,sizeof h); // 初始化
	while(m--) {
		scanf("%d%d",&u,&v);
		// 邻接矩阵建边
		d[u]++,d[v]++; // 度数+1
		g[u][v]=1,g[v][u]=1; // 互达
		// 邻接表建边
		add(u,v);
		add(v,u);
	}
	// 遍历邻接矩阵
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			cout<<g[i][j]<<' ';
		}
		cout<<endl;
	}
	// 遍历邻接表
	for(int i=1;i<=n;i++) {
		cout<<d[i]<<' '; // 先输出点i的度数
		vector<int> s;
		for(int j=h[i];j!=-1;j=ne[j]) {
			int t=e[j];
			s.push_back(t);
		}
		// 编号从小到大排序
		sort(s.begin(),s.end());
		for(auto t:s) cout<<t<<' ';
		cout<<endl;
	}
	return 0;
}