數據結構（C實現）------- 圖的鄰接矩陣表示

數據結構（C實現）------- 圖的鄰接矩陣表示

　　　鄰接矩陣是表示頂點之間相鄰頂點之間相鄰關系的矩陣。設Ｇ＝（Ｖ，Ｅ）是具有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<

完整代碼如下：

/*
 ============================================================================
 Name        : Graph.c
 Author      : jesson20121020
 Version     : 1.0
 Description : create Graph using Adjacency Matrix, Ansi-style
 ============================================================================
 */

#include 
#include 
#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;

/**
 * 根據名稱得到指定頂點在頂點集合中的下標
 * vex  頂點
 * return 如果找到，則返回下標，否則，返回０
 */
int getIndexOfVexs(char vex, MGraph *MG) {
	int i;
	for (i = 1; i <= MG->vexnum; i++) {
		if (MG->vexs[i] == vex) {
			return i;
		}
	}
	return 0;
}

/**
 * 創建鄰接矩陣
 */
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();
	}
}
/**
 * 打印鄰接矩陣和頂點信息
 */
void print_MG(MGraph MG) {
	int i, j;
	if(MG.type == DG){
		printf(Graph type: Direct graph
);
	}
	else{
		printf(Graph type: Undirect graph
);
	}

	printf(Graph vertex number: %d
,MG.vexnum);
	printf(Graph arc number: %d
,MG.arcnum);

	printf(Vertex set:
 );
	for (i = 1; i <= MG.vexnum; i++)
		printf(%c	, MG.vexs[i]);
	printf(
Adjacency Matrix:
);

	for (i = 1; i <= MG.vexnum; i++) {
		j = 1;
		for (; j < MG.vexnum; j++) {
			printf(%d	, MG.arcs[i][j]);
		}
		printf(%d
, MG.arcs[i][j]);
	}
}

/**
 * 主函數
 */
int main(void) {
	MGraph MG;
	create_MG(&MG);
	print_MG(MG);
	return EXIT_SUCCESS;
}

Please input graph type UG(0) or UDG(1) :0
Please input vexmun : 4
Please input arcnum : 4
Please input 1th vex(char):a
Please input 2th vex(char):b
Please input 3th vex(char):c
Please input 4th vex(char):d
Please input 1th arc v1(char) v2(char) : a b
Please input 2th arc v1(char) v2(char) : a c
Please input 3th arc v1(char) v2(char) : a d
Please input 4th arc v1(char) v2(char) : b c
Graph type: Direct graph
Graph vertex number: 4
Graph arc number: 4
vertex set:
 a	b	c	d	
Adjacency Matrix:
0	1	1	1
0	0	1	0
0	0	0	0
0	0	0	0