一、图的存储结构

昨天给大家讲了图的存储结构，一共有四种，邻接表，邻接矩阵，十字链表以及邻接多重表，每个表都有自己的特色以及用途。

今天要给大家分享的是将一个用邻接表表示的图转为邻接矩阵表示，我们知道，邻接矩阵中，存储形式比较简单，普通的邻接矩阵只有0和1，0表示两个节点之间没有边，1表示有边。所以我们要遍历邻接表的每一个结点，得到它的边表，通过其next指针域获得与之相邻的所有边，并在矩阵中的对应位置赋值为1，剩余位置均赋值为0即可。

当然为了方便起见，我们将邻接矩阵的每个边初始化为0，在转化过程中，直接寻找存在的边，赋值为1即可。

二、代码

#define MaxVertexNum 100  //Maximum value of the vertex number#define M 5typedef char VertexType; //the type of vertextypedef int EdgeType; // the type of wight on the edge in weighted graph 带权图中边上的权值的类型// the graph are storaged by adjacency matrix 邻接矩阵存储图typedef struct {	VertexType Vex[MaxVertexNum]; //vertex list	EdgeType Edge[MaxVertexNum][MaxVertexNum];  // adjacency matrix	int vexNum, arcNum;  //current vertex number and arc of graph}MGraph;//the graph are storaged by adjacency listtypedef struct ArcNode {	int adjvex;  // the location of the vertex which was pointed by arc	struct ArcNode *next;}ArcNode;typedef struct VNode {	VertexType data;	ArcNode *first;}VNode, AdjList[MaxVertexNum];typedef struct {	AdjList vertices;  // adjacency list	int vexNum, arcNum;  // current vertex number and arc of graph}*ALGraph;void ConvertGraph(ALGraph &G, EdgeType Edge[M][M]){	for (int i = 0; i < G->vexNum; i++)	{		ArcNode *p = G->vertices[i].first;		while (!p)		{			Edge[i][p->adjvex] = 1;			p = p->next;		}	}}

转载地址：http://hdyni.baihongyu.com/

你可能感兴趣的文章