【C语言】图的邻接矩阵表示法实现

介绍图的邻接矩阵表示法C语言实现

图是一种复杂的数据结构。图的常见表示法有邻接矩阵、邻接表和十字链表。

1、假设现在已经对图有了一定的认识,现在来看图的邻接矩阵表示法所用到的数据结构:

//2015011001 C语言定义图的邻接矩阵表示法
#define MAXV 20  //顶点最大个数
typedef char InfoType;
//定义顶点
typedef struct{
	int no;  //顶点编号
	InfoType data;  //顶点其他信息
}VertexType
//定义图
typedef struct{
	int edges[MAXV][MAXV]; //邻接矩阵
	int vexnum,arcnum;  //顶点数目,边的数目
	VertexType vexs[MAXV]; //存放顶点的信息
}MGraph

只是定义了相关的存储结构,并未实现。

2、现在来看图的邻接表表示法用到的结构:

//2015011002 C语言定义图的邻接表表示法
#include "mgraph.c"  //邻接矩阵
#define MAX_VERTEX_NUM 20  //最大结点数目
typedef enum {DG,DN,UDG,UDN}GraphKind;  //图的种类标记
//定义边或者弧的结构
typedef struct ArcNode{
	int adjvex;//边或者弧所指定点的位置
	InfoType *info; //边或者弧相关的信息,例如权值weight
	struct ArcNode *nextArc;   //指向下一个边或者弧的结点
}ArcNode;
//定义顶点数组
typedef struct VNode {
	VertexType data;   //顶点携带的信息
	ArcNode *firstarc;     //指向第一条依附于该顶点的边或者弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
//图的结构
typedef struct graphs{
	AdjList vertices; //顶点数组
	int vexnum,arcnum; //顶点数目,边的数目
	GraphKind kind;   //图的种类标记
}ALgraph;

类似的,只定义了存储结构。

3、现在用完整的代码实现图的邻接矩阵表示法。

首先这是实现邻接矩阵的完整代码

//2015011003 C语言定义图的邻接矩阵实现
//此文件为用到的相关函数
#define VERTEX_MAX 26  //最大顶点数目
#define MAXVALUE 32767  //顶点最大权值
//定义图
typedef struct{
	char Vertex[VERTEX_MAX];  //保存顶点信息
	int Edges[VERTEX_MAX][VERTEX_MAX]; //保存边的权值
	int isTrav[VERTEX_MAX]; //是否遍历
	int VertexNum ;  //顶点数目
	int EdgeNum;     //边的数目
	int GraphType;   //图的类型,0是无向图,1是有向图
}MatrixGraph;
//创建图的邻接矩阵
void Createlin(MatrixGraph *G){
	int i,j,k,weight;  //i,j,k分别为迭代数,weight是权值
	char start,end; //边或者弧的起始顶点
	printf("please input the node's info:\n"); //输入各个顶点的信息
	for(i=0;i<G->VertexNum;i++){
		getchar();
		printf("this is the %d num:",i+1);
		scanf("%c",&(G->Vertex[i]));//保存到数组中
	}
	//输入每个边的起始顶点和权值
	printf("please input the num and the weight of each edge:\n");
	for(k=0;k<G->EdgeNum;k++){
		getchar();
		printf("this is %d edge:",k+1);
		scanf("%c,%c,%d",&start,&end,&weight);//起点,终点,权值
		for(i=0;start!=G->Vertex[i];i++);//查找起点
		for(j=0;end!=G->Vertex[j];j++);	//查找终点
		G->Edges[i][j]=weight;//保存权值
		if(G->GraphType==0){    //若是无向图,就在对角位置保存权值
		G->Edges[j][i]=weight;	}
	}

}
//输出邻接矩阵的内容
void Outlin(MatrixGraph *G){
	int i,j;//迭代数
	for(j=0;j<G->VertexNum;j++){
		printf("\t%c",G->Vertex[j]);}  //第一行输出顶点信息
		printf("\n");
		for(i=0;i<G->VertexNum;i++){
			printf("%c",G->Vertex[i]);
			for(j=0;j<G->VertexNum;j++){
				if(G->Edges[i][j]==MAXVALUE)  //如果权是最大值就输出MAX
					printf("\tMAX");
				else
					printf("\t%d",G->Edges[i][j]);//否则就输出权值
			}
			printf("\n");
		}
}

这是用到的测试代码:

//测试图的邻接矩阵
#include <stdio.h>
#include "tu.c" //包含进来C语言实现图的邻接矩阵的文件
int main(){
	MatrixGraph G; //定义一个图
	int i,j;//迭代数
	//输入图的类型,0是无向图,1是有向图
	printf("please choose the type of graph(0 or 1)");
	scanf("%d",&G.GraphType);//保存图的类型
	//输入顶点数目和边的数目
	printf("please input the VertexNum and the EdgesNum of the Graph:");
	scanf("%d,%d",&G.VertexNum,&G.EdgeNum);//保存顶点和边的数目
	for(i=0;i<G.VertexNum;i++)//清空矩阵
		for(j=0;j<G.VertexNum;j++)
			G.Edges[i][j]=MAXVALUE;//设置各元素的值为最大值
	Createlin(&G);//创建邻接矩阵
	printf("the graph's data is :\n");
	Outlin(&G);//输出邻接矩阵
	getchar();
	return 0;

}

第三部分代码在CentOS环境下用Linux-C 编写,用gcc 编译通过,代码无错,同时注释详细,可直接参考学习。

图的邻接矩阵实现就到这里。后期会继续总结,加油!

参考资料:张子言.《常用算法深入学习实录》.电子工业出版社

刘凯宁
20150110

Share

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*


*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>