首页 > 代码库 > 数据结构(C实现)------- 图的邻接矩阵表示
数据结构(C实现)------- 图的邻接矩阵表示
[本文是自己学习所做笔记,欢迎转载,但请注明出处:http://blog.csdn.net/jesson20121020]
邻接矩阵是表示顶点之间相邻顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,若(vi,vj)属于E,则对应G的邻接矩阵中的元素A[i][j] = wij 或1,否则,A[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<<n^2,所以,该算法的时间复杂度为O(n^2)。
完整代码如下:
/* ============================================================================ Name : Graph.c Author : jesson20121020 Version : 1.0 Description : create Graph using Adjacency Matrix, Ansi-style ============================================================================ */ #include <stdio.h> #include <stdlib.h> #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 如果找到,则返回下标,否则,返回0 */ 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\n"); } else{ printf("Graph type: Undirect graph\n"); } printf("Graph vertex number: %d\n",MG.vexnum); printf("Graph arc number: %d\n",MG.arcnum); printf("Vertex set:\n "); for (i = 1; i <= MG.vexnum; i++) printf("%c\t", MG.vexs[i]); printf("\nAdjacency Matrix:\n"); for (i = 1; i <= MG.vexnum; i++) { j = 1; for (; j < MG.vexnum; j++) { printf("%d\t", MG.arcs[i][j]); } printf("%d\n", 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以上实现了图的邻接矩阵表示,其实,图还有其他的存储方式,如邻接表,十字链表等
数据结构(C实现)------- 图的邻接矩阵表示