实验七图汇编

《数据结构与算法》实验指导V2014

实验七 图

【实验目的】

1、掌握图的邻接矩阵和邻接表表示。

2、掌握图的深度优先和广度优先搜索方法。 3、掌握图的最小生成树Prim算法。 4、掌握图的拓扑排序算法。

5、掌握图的单源最短路径dijkstra算法。

【实验学时】

4-6学时

【实验预习】

回答以下问题：

1、写出图7-1无向图的邻接矩阵表示。

AGFCBDHE 图7-1 无向图G1

2、写出图7-2有向图的邻接表表示。

FEBA图7-2 有向图G2

CD 3、写出图7-1的深度优先搜索序列和广度优先搜索序列。 深度：ABDHECFG 广度：ABCFDEGH

4、写出图7-2的拓扑序列，说明该有向图是否有环？

5、根据图7-3，写出其最小生成树。 常熟理工学院计算机科学与工程学院

1

《数据结构与算法》实验指导V2014

A6155B5CD3642E6F 图7-3 无向带权图G3

6、根据图7-4，求从顶点A到其他顶点的单源最短路径。

F100A3010D505C60E2010B

图7-4有向带权图G4

【实验内容和要求】

1、 编写程序exp7_1.c，实现图的邻接矩阵存储及图的深度优先搜索和广度优先搜索。 以图7-1的无向图为例，补充完整程序，调试运行并写出运行结果。 运行结果：（包括输入数据）

常熟理工学院计算机科学与工程学院

2

《数据结构与算法》实验指导V2014

exp7_1.c参考程序如下： #include #define N 20 #define TRUE 1 #define FALSE 0 int visited[N]; /*访问标志数组*/ typedef struct { /*辅助队列的定义*/ int data[N]; int front,rear; }queue;

typedef struct { /*图的邻接矩阵表示*/ int vexnum,arcnum; char vexs[N]; int arcs[N][N]; }MGraph;

void createGraph(MGraph *g); /*建立一个无向图的邻接矩阵*/ void dfs(int i, MGraph *g); /*从第i个顶点出发深度优先搜索*/ void tdfs(MGraph *g); /*深度优先搜索整个图*/

void bfs(int k, MGraph *g); /*从第k个顶点广度优先搜索*/ void tbfs(MGraph *g); /*广度优先搜索整个图*/ void init_visit(); /*初始化访问标识数组*/

常熟理工学院计算机科学与工程学院

3