欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构(C实现)------- 图的邻接矩阵表示

程序员文章站 2022-07-04 11:48:30
     邻接矩阵是表示顶点之间相邻顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,若(vi,vj)属于E,则对应G的邻接矩阵中的元素A[i][j] =...

 

   邻接矩阵是表示顶点之间相邻顶点之间相邻关系的矩阵。设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<

 

完整代码如下:

 

/*
 ============================================================================
 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 如果找到,则返回下标,否则,返回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
);
	}
	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
   以上实现了图的邻接矩阵表示,其实,图还有其他的存储方式,如邻接表,十字链表等