实验四图的建立与遍历

实验类型：综合性 实验时数： 2 学时 一、实验目的

1. 掌握图的基本存储方法；

2. 掌握有关图的操作算法并用高级语言实现； 3. 熟练掌握图的两种搜索路径的遍历方法。

二、实验设备

Windows 计算机（含 Visual C++ 6.0）。

三、实验原理

1. 图是由若干个顶点和若干条边构成的结构， 每个顶点具有任意多个前驱

和 后继。顶点是一些具体对象的抽象， 而边是对象间关系的抽象。 图是一种复杂的 数据结构，其信息包括两部分：图中数据元素即顶点的信息，元素间的关系（顶 点之间的关系）——边或者弧的信息。

2. 图的常用存储结构包括邻接矩阵存储、邻接表存储、十字链表存储以及邻

接多重表存储。

3. 邻接表存储法类似于树的孩子链表表示法。 它对图中的每个顶点建立一

个 带头节点的线性链表， 用于存储图中与顶点相邻接的边或弧的信息。 头节点中存 放该顶点的信息。所有头节点用一个顺序表存放。

4. 邻接表存储图很容易找到任一顶点的邻接点， 但是要判定任意两个顶点

之 间是否有边或弧相连，则需搜索第 i 个或第 j 个链表，不及邻接矩阵方便。

四、实验内容及步骤

（一）实验内容

假设以一个带权有向图表示某一区域的公交线路网， 图中顶点代表一些区域 中的重要场所， 弧代表已有的公交线路， 弧上的权表示该线路上的票价 （或搭乘 所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票

价或最少的 时间从区域中的某一场所到达另一场所。

(二) 实验步骤

1. 定义结点结构，定义图结构。 2. 存储图信息；

3. 定义求任意两点最短路径函数； 4. 写出主函数。

(三) 实验提示

typedef struct node { int no; float wgt; struct node *next; }edgenode; typedef struct { char vtx; edgenode *link; }vexnode;

typedef vexnode Graph[n];

void Floyd(Graph G, float A[n][n], int p[n][n])

{

int i, j, k; for (i=0; i{

A[i][j]=G[i][j]; P[i][j]=-1;

}

for (k=0; kfor (j=0; j{

P[i][j]=k;

A[i][j]=A[i][k]+A[k][j];

}

}

五、思考题

1. 判断两点是否可达。

2. 如何对程序进行修改，找一条人最少的公交线路？ 3. 练习图的拓扑排序。

六、实验报告要求

1. 程序要添加适当的注释，程序的书写要采用缩进格式。

2. 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反

应，如插入删除时指定的位置不对等等。

3. 程序要做到界面友好， 在程序运行时用户可以根据相应的提示信息进行

操 作。

七、参考代码

1. 图的建立与遍历 #include #include #include #include

#define MAX_VERTEX_NUM 20 // 图的最大顶点数 #define MAXQSIZE 30 enum BOOL {False,True}; typedef struct ArcNode

{int adjvex; // 该弧所指向的顶点的位置

// 队列的最大容量

struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode; typedef struct

{ArcNode* AdjList[MAX_VERTEX_NUM]; // 指向第一条依附该顶点的弧的 指

//弧结点

针

int vexnum,arcnum; // 图的当前顶点和弧数

int GraphKind;//图的种类， 0---无向图， 1---有向图 }Graph; typedef struct

//队列结构

{int elem[MAXQSIZE]; // 数据域 int front; //队头指针 int rear; //队尾指针

}SqQueue;

BOOL visited[MAX_VERTEX_NUM]; // 全局变量——访问标志数组 void CreateGraph(Graph &); //生成图的邻接表 void DFSTraverse(Graph); // 深度优先搜索遍历图 void DFS(Graph,int); void BFSTraverse(Graph); //广度优先搜索遍历图 void Initial(SqQueue &);

// 初始化一个队列

BOOL QueueEmpty(SqQueue);

// 判断队列是否空

BOOL EnQueue(SqQueue &,int); //将一个元素入队列 BOOL DeQueue(SqQueue &,int &); //将一个元素出队列 int FirstAdjVex(Graph,int); //求图中某一顶点的第一个邻接顶点 int NextAdjVex(Graph,int,int); // 求某一顶点的下一个邻接顶点 void main()

{Graph G; // 采用邻接表结构的图 char j='y';

printf(\" 本程序将演示生成一个图，并对它进行遍历 .\\n\"); printf(\" 首先输入要生成的图的种类 .\\n\");

无向图, 1--有向图\\n\");

之后输入图的顶点数和弧数。 \\n 格式：顶点数，弧数；例如接着输入各边 (弧尾，弧头 ).\\n例如:\\n1,2\\n1,3\\n2,4\\n\");

printf(\"0---printf(\" :4,3\\n\"); printf(\"printf(\" 程序会生成一个图，并对它进行深度和广度遍历 .\\n\"); printf(\"深度遍

历:1->2->4->3\\n 广度遍历:1->2->3->4\\n\");

while(j!='N'&&j!='n')

{printf(\" 请输入要生成的图的种类 (0/1):\"); scanf(\"%d\

输入图的种类 printf(\" 请输入顶点数和弧数： \");

scanf(\"%d,%d\输入图的顶点数和弧数 CreateGraph(G); DFSTraverse(G); BFSTraverse(G);

// 生成邻接表结构的图 //深度优先搜索遍历图 //广度优先搜索遍历图

printf(\" 图遍历完毕，继续进行吗 ?(Y/N)\"); scanf(\" %c\

}

}

void CreateGraph(Graph &G) {// 构造邻接表结构的图 G int i; int start,end; ArcNode *s;

for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; // 初始化指针数组 for(i=1;i<=G.arcnum;i++)

{scanf(\"%d,%d\输入弧的起点和终点 s=(ArcNode

*)malloc(sizeof(ArcNode)); // 生成一个弧结点 s->nextarc=G.AdjList[start]; //

插入到邻接表中 s->adjvex=end;

G.AdjList[start]=s;

if(G.GraphKind==0) //若是无向图，再插入到终点的弧链中

{s=(ArcNode *)malloc(sizeof(ArcNode)); s->nextarc=G.AdjList[end]; s->adjvex=start;

G.AdjList[end]=s;

}

} }

void DFSTraverse(Graph G) {// 深度优先遍历图 G int i;

printf(\"DFSTraverse:\");

for(i=1;i<=G.vexnum;i++) visited[i]=False; // 访问标志数组初始化 for(i=1;i<=G.vexnum;i++)

if(!visited[i]) DFS(G,i); // 对尚未访问的顶点调用 DFS printf(\"\\b\\b \\n\");

}

void DFS(Graph G,int i)

{//从第 i 个顶点出发递归地深度遍历图 G int w;

visited[i]=True; //访问第 i 个顶点 printf(\"%d->\

for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))

if(!visited[w]) DFS(G,w); // 对尚未访问的邻接顶点 w 调用 DFS

}

void BFSTraverse(Graph G)

{//按广度优先非递归的遍历图 G，使用辅助队列 Q 和访问标志数组 visited int i,u,w; SqQueue Q;

printf(\"BFSTreverse:\");

for(i=1;i<= G.vexnum;i++) visited[i]=False; // 访问标志数组初始化 Initial(Q); //

初始化队列

for(i=1;i<=G.vexnum;i++)

if(!visited[i]) {visited[i]=True; //访问顶点 i printf(\"%d->\

EnQueue(Q,i);

//将序号 i 入队列

while(!QueueEmpty(Q)) // 若队列不空，继续 {DeQueue(Q,u); //将队头元素出队列并置为 u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))

if(!visited[w]) //对 u 的尚未访问的邻接顶点 w 进行访问并入队列

{visited[w]=True; printf(\"%d->\EnQueue(Q,w);

} } }

printf(\"\\b\\b \\n\");

}

int FirstAdjVex(Graph G,int v)

{//在图 G中寻找第 v 个顶点的第一个邻接顶点 if(!G.AdjList[v]) return 0;

else return(G.AdjList[v]->adjvex);

}

int NextAdjVex(Graph G,int v,int u)

{//在图 G中寻找第 v 个顶点的相对于 u的下一个邻接顶点 ArcNode *p; p=G.AdjList[v];

while(p->adjvex!=u) p=p->nextarc; // 在顶点 v 的弧链中找到顶点 u if(p->nextarc==NULL) return 0;

//若已是最后一个顶点，返回 0

else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号

}

void Initial(SqQueue &Q) {//队列初始化 Q.front=Q.rear=0;

}

BOOL QueueEmpty(SqQueue Q)

{// 判断队列是否已空，若空返回 True,否则返回 False if(Q.front==Q.rear) return True; else return False;

}

BOOL EnQueue(SqQueue &Q,int ch)

{// 入队列，成功返回 True，失败返回 False if((Q.rear+1)%MAXQSIZE==Q.front) return False; Q.elem[Q.rear]=ch;

Q.rear=(Q.rear+1)%MAXQSIZE; return True;

}

BOOL DeQueue(SqQueue &Q,int &ch)

{//出队列 ,成功返回 True，并用 ch 返回该元素值，失败返回if(Q.front==Q.rear) return False; ch=Q.elem[Q.front];

Q.front=(Q.front+1)%MAXQSIZE; return True;

//成功出队列，返回 True

}

False 2. 最短路径 --迪杰斯特拉算法 #include #include #include #include #define INFINITY 30000

//定义一个权值的最大值

#define MAX_VERTEX_NUM 20 // 图的最大顶点数 enum BOOL {False,True}; typedef struct

{int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum,arcnum; }Graph;

void CreateGraph(Graph &); //生成图的邻接矩阵

void ShortestPath_DiJ(Graph,int,int[][MAX_VERTEX_NUM],int[]);

//用迪杰斯特拉算法求从某一源点到其余顶点的最短路径 void Print_ShortestPath(Graph,int,int[][MAX_VERTEX_NUM],int[]);

//显示最短路径 void main()

{Graph G; // 采用邻接矩阵结构的图 char j='y'; int u;

int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 存放从源点到各顶

// 图的当前顶点和边数

点的最短路径

int D[MAX_VERTEX_NUM];

//存放从源点到各顶点的

最短路径的距离

printf(\" 本程序将演示利用迪杰斯特拉算法求 \\n 从图的一点到其余顶点的最

短路径 .\\n\");

printf(\" 首先输入图的顶点数和弧数 .\\n 格式：顶点数，弧数；例如 :5,7\\n\");

printf(\" 然 后 输 入 各 弧 和 权 值 .\\n 格 式 ： 弧 尾 ， 弧 头 ， 权

值 ； 例 如:\\n1,2,10\\n1,3,18\\n2,4,5\\n3,2,5\\n4,3,2\\n4,5,2\\n5,3,2\\n\");

printf(\" 再输入从哪个顶点出发，例如 :1\\n\");

printf(\"程序将会找出从 1 到其余顶点的最短路径 .\\n\"); printf(\"10 1->2\\n17 1->2->4->3\\n15 1->2->4\\n17 1->2->4->5\\n\"); while(j!='N'&&j!='n')

{CreateGraph(G);

// 生成邻接矩阵结构的图

printf(\" 从哪个顶点出发 :\");

scanf(\"%d\输入迪杰斯特拉算法中的起始顶点

ShortestPath_DiJ(G,u,P,D); /利/ 用迪杰斯特拉算法求最短路径 Print_ShortestPath(G,u,P,D); /显/ 示最短路径 printf(\" 最短路径演示

完毕，继续进行吗 ?(Y/N)\");

scanf(\" %c\

}

}

void CreateGraph(Graph &G) {// 构造邻接矩阵结构的图 G int i,j;

int start,end,weight;

printf(\" 请输入图的顶点数和弧数 (顶点数，弧数 ):\");

scanf(\"%d,%d\输入图的顶点数和边数 for(i=1;i<=G.vexnum;i++)

for(j=1;j<=G.vexnum;j++)

G.arcs[i][j]=INFINITY; // 初始化邻接矩阵

printf(\" 输入各弧和权值，格式：弧尾，弧头，权值 \\n\"); for(i=1;i<=G.arcnum;i++)

{scanf(\"%d,%d,%d\输入边的起点和终点及权值 G.arcs[start][end]=weight;

}

}

void ShortestPath_DiJ(Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[]) {//用

迪杰斯特拉算法求有向网 G 的v0顶点到其余顶点 v的最短路径 P[v]及 其带权路径长度 D[v]

//若 P[v][0] ≠0,表明从源点出发存在一条到顶点 v 的最短路径，该路径存

放 在 P[v] 中

//final[v] 为 True 则表明已经找到从 v0 到 v 的最短路径 int i,j,w,v; int min;

BOOL final[MAX_VERTEX_NUM]; for(v=1;v<=G.vexnum;v++) // 初始化

{final[v]=False; D[v]=G.arcs[v0][v]; for(i=0;i<=G.vexnum;i++) P[v][i]=0; // 设

空路径

//if(D[v]}

D[v0]=0; final[v0]=True; // 初始时， v0 属于 S 集

//开始主循环，每次求得 v0到某个顶点 v 的最短路径，并加 v 到 S集 for(i=1;i<=G.vexnum;i++) //寻找其余 G.vexnum-1 个顶点

{v=0; min=INFINITY; for(w=1;w<=G.vexnum;w++) // 寻找当前离 v0 最近的

顶点 v if((!final[w])&&(D[w]{v=w;min=D[w];}

if(!v) break; // 若 v=0 表明所有与 v0 有通路的顶点均已找到了最短路

径， 退出主循环

final[v]=True; // 将 v 加入 S 集 for(j=0;P[v][j]!=0;j++) ; P[v][j]=v;

//将路径 P[v] 延伸到顶点 v

for(w=1;w<=G.vexnum;w++) // 更新当前最短路径及距离 if(!final[w]&&(min+G.arcs[v][w]for(j=0;P[v][j]!=0;j++) P[w][j]=P[v][j];

} } }

void Print_ShortestPath(Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[]) {//显示从顶点 u 到其余顶点的最短路径及距离 int v,j;

printf(\"The shortest path from Vertex %d to the other Vertex:\\n\"); for(v=1;v<=G.vexnum;v++)

{if(P[v][0]==0) continue; // 表明顶点 v0 到顶点 v 没有通路 printf(\"%-4d\

printf(\"\\b\\b \\n\");

}

}

3. 最短路径 --弗洛依德算法 #include #include #include #include #define INFINITY 10000

//定义权值的最大值

#define MAX_NUM 20 // 图的最大顶点数 enum BOOL {False,True}; typedef struct

{int arcs[MAX_NUM][MAX_NUM]; // 邻接矩阵

int vexnum,arcnum; }Graph;

// 图的当前顶点和边数

void CreateGraph(Graph &); //生成图的邻接矩阵 void

ShortestPath_Floyd(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);

//用弗洛依德算法求每对顶点之间的最短路径 void

Print_ShortestPath(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);

//显示用弗洛依德算法所求得的最短路径

void Print_OnePath(int,int,int,BOOL[][MAX_NUM][MAX_NUM]); //显示一对顶

点之间的最短路径

void main()

{Graph G; // 采用邻接矩阵结构的图 char j='y'; int u;

BOOL P[MAX_NUM][MAX_NUM][MAX_NUM]; // 存放每对顶点的最短路 径 int D[MAX_NUM][MAX_NUM];

//存放每对顶点的最短路径的距离

printf(\" 本程序演示弗洛依德算法求图的每一对顶点之间的最短路径。 \\n\"); printf(\"首先输入图的顶点和弧的数目。 \\n 例如： 3,5\\n\"); printf(\" 接 着 输 入 弧 (i,j) 和 其 权 值 。 \\n 例 如 ： \\n1,2,4\\n2,1,6\\n1,3,11\\n3,1,3\\n2,3,2\\n\");

printf(\" 程序将会显示出每对顶点之间的最短路径值和所经过的路径： \\n\"); printf(\"4 1->2\\n6 1->2->3\\n5 2->3->1\\n2 2->3\\n3 3->1\\n7 3->1->2\\n\");

while(j!='N'&&j!='n')

{CreateGraph(G);

// 生成邻接矩阵结构的图

ShortestPath_Floyd(G,P,D); /利/ 用弗洛依德算法求最短路径 Print_ShortestPath(G,P,D); /显/ 示每对顶点之间的最短路径 printf(\" 继续执行吗 ?(Y/N)\"); scanf(\" %c\

}

printf(\" 程序运行结束，按任意键退出窗口 !\"); getch();

}

void CreateGraph(Graph &G) {// 构造邻接矩阵结构的图 G int i,j;

int start,end,weight;

printf(\" 请输入顶点和弧的数目，格式：顶点数，弧数 \\n\"); scanf(\"%d,%d\输入图的顶点数和边数 for(i=1;i<=G.vexnum;i++)

for(j=1;j<=G.vexnum;j++)

G.arcs[i][j]=INFINITY; // 初始化邻接矩阵

printf(\" 请输入各条弧和其权值，格式：弧尾，弧头，权值： \\n\"); for(i=1;i<=G.arcnum;i++)

{scanf(\"%d,%d,%d\输入边的起点和终点及权值 G.arcs[start][end]=weight;

} }

void ShortestPath_Floyd(Graph G,BOOL P[][MAX_NUM][MAX_NUM],int D[][MAX_NUM])

{//用弗洛依德算法求有向网 G的每对顶点 v和 w之间的最短路径 P[v][w] //及其带权路径长度 D[v][w],

//若 P[v][w][u] 为 True,表明 u是从 v到 w 当前求得最短路径上的顶点 int u,v,w,i;

for(v=1;v<=G.vexnum;v++) // 各对顶点之间的初始已知路径及距离 for(w=1;w<=G.vexnum;w++) {D[v][w]=G.arcs[v][w];

for(u=1;u<=G.vexnum;u++) P[v][w][u]=False; if(D[v][w]// 从 v 到 w 有直接路径

{P[v][w][v]=True;P[v][w][w]=True;}

}

for(u=1;u<=G.vexnum;u++)

for(v=1;v<=G.vexnum;v++)

for(w=1;w<=G.vexnum;w++) if(D[v][u]+D[u][w]经 u 到 w 的一条路径更短 {D[v][w]=D[v][u]+D[u][w];

for(i=1;i<=G.vexnum;i++)

if(P[v][u][i]||P[u][w][i])

P[v][w][i]=True;

}

}

void Print_ShortestPath(Graph G,BOOL P[][MAX_NUM][MAX_NUM],int D[][MAX_NUM])

{//显示每对顶点之间的最短路径及距离 int v,w,j;

printf(\"最短路径： \\n\"); for(v=1;v<=G.vexnum;v++)

for(w=1;w<=G.vexnum;w++) if(D[v][w]通路

{printf(\"%-5d\从 v 到 w 的最短距离

Print_OnePath(v,w,G.vexnum,P); /显/ 示从 v 到 w 的最短路径 printf(\"\\n\");

} }

void Print_OnePath(int v,int w,int num,BOOL P[][MAX_NUM][MAX_NUM]) {//显示从 v到 w的最短路径 int i; for(i=1;i<=num;i++)

if(i!=v&&i!=w&&P[v][w][i]==True) break;

if(i>num) printf(\"%d->%d\说明从 v 到 w 不需经过其它的顶点 else {Print_OnePath(v,i,num,P); //否则从 v 到 w 需经过顶点 i，先显示从 v 到 i 的最

短路径

if(i<10) printf(\"\\b\"); //控制显示格式，消除多余的 \"->\" else printf(\"\\b\\b\");

Print_OnePath(i,w,num,P); //显示从 i 到 w 的最短路径

}

}