实现图的邻接矩阵和邻接表存储

1． 需求分析

对于下图所示的有向图G，编写一个程序完成如下功能： 1． 建立G的邻接矩阵并输出之

2． 由G的邻接矩阵产生邻接表并输出之

3． 再由2的邻接表产生对应的邻接矩阵并输出之

2． 系统设计

1． 图的抽象数据类型定义： ADT Graph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集 数据关系R： R={VR}

VR={|v,w∈V且P(v,w),表示从v到w的弧，

谓词P(v,w)定义了弧的意义或信息}

基本操作P：

CreatGraph(&G,V,VR)

初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图G DestroyGraph(&G) 初始条件：图G存在 操作结果：销毁图G InsertVex(&G,v)

初始条件：图G存在，v和图中顶点有相同特征 操作结果：在图G中增添新顶点v ……

InsertArc(&G,v,w)

初始条件：图G存在，v和w是G中两个顶点

操作结果：在G中增添弧，若G是无向的则还增添对称弧 ……

DFSTraverse(G,Visit())

初始条件：图G存在，Visit是顶点的应用函数

操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。

—

一旦Visit()失败，则操作失败 BFSTraverse(G,Visit())

初始条件：图G存在，Visit是顶点的应用函数

操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败 }ADT Graph

2． 主程序的流程：

调用CreateMG函数创建邻接矩阵M； 调用PrintMatrix函数输出邻接矩阵M

调用CreateMGtoDN函数，由邻接矩阵M创建邻接表G 调用PrintDN函数输出邻接表G

调用CreateDNtoMG函数，由邻接表M创建邻接矩阵N 调用PrintMatrix函数输出邻接矩阵N 3．函数关系调用图：

3．调试分析

（1）在MGraph的定义中有枚举类型

typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}

赋值语句G.kind(int)=M.kind(GraphKind);是正确的，而反过来M.kind=G.kind则是错误的， 要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enum{DG,DN,UDG,UDN}

会自动赋值DG=0；DN=1，UDG=2，UDN=3；可以自动从GraphKind类型转换到int型，但不会自动从int型转换到GraphKind类型

欢迎下载

2

—

（2）算法的时间复杂度分析：

CreateMG、CreateMGtoDN、CreateDNtoMG、PrintMatrix、PrintDN的时间复杂度均为O(n2) n为图的顶点数，所以main：T(n)= O(n2)

4．测试结果

用需求分析中的测试数据 输入：

欢迎下载

3

—

输出：

5、用户手册

（1）输入顶点数和弧数； （2）输入顶点内容；

（3）按行序输入邻接矩阵，输入各弧相应权值

（4）回车输出邻接矩阵M、邻接表G和邻接矩阵N

6、附录 源程序：

#include #include

#define MAX_VERTEX_NUM 20 typedef int VRType; typedef int InfoType; typedef int VertexType;

typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网} typedef struct ArcCell{

VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻； //对带权图则为权值类型 InfoType *info;//该弧相关信息的指针

欢迎下载

4

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{

VertexType vexs[MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵

int vexnum,arcnum;//图的当前顶点数和弧数 GraphKind kind;//图的种类标志 }MGraph;

void CreateMG(MGraph &M){ int i,j;

M.kind=DN;

printf(\"输入顶点数:\"); scanf(\"%d\printf(\"输入弧数:\");

scanf(\"%d\printf(\"输入顶点:\\n\"); for(i=0;iscanf(\"%d\} }

typedef struct ArcNode{

int adjvex;//该弧所指向的顶点在数组中的下标 struct ArcNode *nextarc;

InfoType *info;//该弧相关信息的指针 }ArcNode;

typedef struct VNode{

VertexType data;//顶点信息

ArcNode *firstarc;//指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices;

int vexnum,arcnum;//图的当前顶点数和弧数 int kind;//图的种类标志 }ALGraph;

欢迎下载

—

5

void PrintDN(ALGraph G){ int i;ArcNode *p; printf(\"顶点:\\n\");

for(i=0;iprintf(\"%2d\printf(\"\\n弧:\\n\");

for(i=0;iprintf(\"%d→%d(%d)\\p=p->nextarc; }

printf(\"\\n\"); }//for }

void CreateMGtoDN(ALGraph &G,MGraph M){ //采用邻接表存储表示,构造有向图G(G.kind=DN) int i,j;ArcNode *p; G.kind=M.kind;

G.vexnum=M.vexnum; G.arcnum=M.arcnum;

for(i=0;iG.vertices[i].firstarc=NULL;//初始化指针 }

for(i=0;ip=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=M.arcs[i][j].info; G.vertices[i].firstarc=p; } }

void CreateDNtoMG(MGraph &M,ALGraph G){ int i,j;ArcNode *p;

M.kind=GraphKind(G.kind); M.vexnum=G.vexnum; M.arcnum=G.arcnum; for(i=0;i欢迎下载

—

6

p=G.vertices[i].firstarc; while(p){

M.arcs[i][p->adjvex].adj=1; p=p->nextarc; }//while

for(j=0;jvoid PrintMatrix(MGraph M){ int i,j;

for(i=0;ivoid main(){

MGraph M,N;ALGraph G; CreateMG(M); PrintMatrix(M);

CreateMGtoDN(G,M); PrintDN(G);

CreateDNtoMG(N,G); PrintMatrix(N); }

欢迎下载 —

7