Graph

Graph Graph 题目链接

click here!

题目大意

构建图的邻接矩阵

邻接矩阵：如果一个图有n个顶点，那么我们就可以建立一个n*n的邻接矩阵，矩阵第i行第j列的值只能0或1，为0表示vi与vj没有边，反之则有边

输入

图的顶点个数n

接下来n行，每行都有：编号为id的顶点，该顶点存在mi条边，该顶点连接的mi个顶点的id

输出

邻接矩阵

思路

先根据顶点个数初始化n*n矩阵全为0，每读一个就修改即可

复杂度分析

时间复杂度：O(n^2)

空间复杂度: 由于我们采取邻接矩阵存储图，空间复杂度为点的个数的平方，即O(n^2)

AC参考代码

#include 
#include 
#include 
#include 
using namespace std;
typedef struct Graph {
	int vexnums;
	int** edge;
};
int main()
{
	Graph G;
	cin >> G.vexnums;
	G.edge = new int* [G.vexnums];
	for (int i = 0; i < G.vexnums; i++) {
		G.edge[i] = new int [G.vexnums];
	}
	for (int x = 0; x < G.vexnums; x++) {
		for (int y = 0; y < G.vexnums; y++) {
			G.edge[x][y] = 0;
		}
	}
	int vi, vj, n;
	for (int i = 0; i < G.vexnums; i++) {
		cin >> vi >> n;
		for (int x = 0;x < n;x++) {
			cin >> vj;
			G.edge[vi - 1][vj - 1] = 1;
		}
	}
	for (int x = 0; x < G.vexnums; x++) {
		for (int y = 0; y < G.vexnums; y++) {
			cout << G.edge[x][y];
			if (y != G.vexnums - 1)cout << ' ';
		}
		cout << endl;
	}
}