?

　　　邻接矩阵是表示顶点之间相邻顶点之间相邻关系的矩阵。设Ｇ＝（Ｖ，Ｅ）是具有n个顶点的图，若(vi,vj)属于Ｅ，则对应Ｇ的邻接矩阵中的元素A[i][j] = wij 或１,否则，Ａ[i][j] = 0或无穷大,其中，wij可以指边的权重。

　　　无向图或无向网的邻接矩阵一定是对称的，因为当(vi,vj)属于E时，也有(vj,vi)属于E。而有向图或有向网的邻接矩阵不一定对称，所以用邻接矩阵表示一个有n个顶点的有向图或有向网时，所需的存储空间为n^2。由于无向图或无向网的邻接矩阵是对称的，因此可采用压缩存储的方法，仅存储下三角矩阵（包括主对角线上的元素）中的元素，存储空间只需n*(n+1)/2。显然，邻接矩阵表示法的空间复杂度为s(n) = O(n^2)。

　　　用邻接矩阵表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要一个一维数组存储顶点信息。设计如下：

?

#define MAX_VEX_NUM 50
typedef char VertexType;
typedef enum {
	DG, UDG
} GraphType;
typedef struct {
	VertexType vexs[MAX_VEX_NUM];
	int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
	int vexnum, arcnum;
	GraphType type;
} MGraph;

?

　　(1)　输入图的类型（无向图还是有向图）

　　(2)　输入图的顶点数，边数

　　(3)　输入顶点的字符信息，建立顶点数组

　　(4)　初始化邻接矩阵

　　(5)　输入边的信息，建立图的邻接矩阵，注意区分是图的类型，另外，如果是有权图，邻接矩阵保存其边的权重，这里是无权图。

?

算法源代码如下：

?

void create_MG(MGraph *MG) {
	int i, j, k;
	int v1, v2, type;
	char c1, c2;
	printf(Please input graph type DG(0) or UDG(1) :);
	scanf(%d, &type);
	if (type == 0)
		MG->type = DG;
	else if (type == 1)
		MG->type = UDG;
	else {
		printf(Please input correct graph type DG(0) or UDG(1)!);
		return;
	}

	printf(Please input vexmun : );
	scanf(%d, &MG->vexnum);
	printf(Please input arcnum : );
	scanf(%d, &MG->arcnum);
	getchar();
	for (i = 1; i <= MG->vexnum; i++) {
		printf(Please input %dth vex(char):, i);
		scanf(%c, &MG->vexs[i]);
		getchar();
	}

	//初始化邻接矩阵
	for (i = 1; i <= MG->vexnum; i++) {
		for (j = 1; j <= MG->vexnum; j++) {
			MG->arcs[i][j] = 0;
		}
	}

	//输入边的信息，建立邻接矩阵
	for (k = 1; k <= MG->arcnum; k++) {
		printf(Please input %dth arc v1(char) v2(char) : , k);

		scanf(%c %c, &c1, &c2);
		v1 = getIndexOfVexs(c1, MG);
		v2 = getIndexOfVexs(c2, MG);
		if (MG->type上 == 1)
			MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1;
		else
			MG->arcs[v1][v2] = 1;
		getchar();
	}
}

?

　　　该算法的时间复杂度为O(n^2+n*e)，其中O(n^2)的时间耗费在邻接矩阵的初始化操作上，O(n*e)的时间耗费在邻接矩阵的建立操作上，因为在一般情况下，e<

?

完整代码如下：

?