《数据结构与算法》(清华)典型例题

学习必备 欢迎下载

inti，j；

edgenode * p；

for(i=0；i

for (i＝0；i

If (g—>arcs[i][j]＝0) {

p＝(edgenode * )malloc(sizeof (edgenode))； //创建一个结点 p—>adjvex=j

p—>next=ga[i].link； //链人链表 ga[i].1inkt = p；

p=(edgenode * )malloc ( sizeof ( edgenode))； //创建另一个结点 p—>adjvex=i；

p—>next=ga[j].link； //创建一个结点 ga[j].1ink t=p； } } }

[例11-41] 设计一个算法，求无向图的连通分量个数。

解析：由深度优先搜索遍历算法和广度优先搜索遍历算法可知，调用一次深度优先搜 索递归算法或广度优先搜索递归算法只能遍历图中1个连通分量。因此，只需要记录递归 函数被调用的次数，该次数就是图中连通分量的个数。具体算法如下： iht visited[n]； int count(graph * g) {

int i，m=0；

for( i=0；i

for( i＝0；i

dfs(g，i)；

n++； //每调用一次，计数器加1 }

return n； }

[例11—42] 假设图用邻接矩阵表示，设计一个算法，输出含指定顶点vi的所有简单回路。

解析：用数组p保存走过的路径。定义递归算法path (g，i，k)，其功能是确定路径上第k+1个顶点的序号。调用这个算法之前，先将i存入p[0]中。假设p[k]的值为t，检查邻接矩阵的第t行：如果vs是vt相邻的未被访问点，则将vs标记为已被访问，将s存入p[k+1]中，并递归调用path (g，i，k+1)函数。为了实现回溯，在执行path (g，i，k+1)调用后，要

学习必备 欢迎下载

重新将vs标记为未被访问。若Vp[k]到Vi存在一条边，则表示找到了一条路径，输出p数组。具体算法如下： intvisited[n]； int p[n]；

void path(graph * g，int i，int k) {

int s；

if(g—>arcs[p[k]][i]＝＝1) //找到一条路径并输出 {

for(s=o；s<＝k；s++)

printf(”％d \\n”，p[s])； } else {

s=0； while (s

if(g—>arcs[p[k]][s]＝＝1&& visited[s]＝＝0) {

visited[s]＝1； p[k+1]＝s；

path(g，i，k+1)； visited[s]＝0； }

s++； } } }

void disppath(graph * g，int i) {

int k； p[0]＝i；

for(k=0；k

(例11—43) 给定n个村庄之间的交通图，若村庄i和村庄j之间有道路，则将顶点i和顶点j用边连接，边上的权叶表示这条道路的长度。现要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路径最近?试设计一个算法解决此问题，并应用该算法解答图11.23所示实例。

学习必备 欢迎下载

解析：算法基本思想如下： (1)建立图的邻接矩阵。

(2)用Floyd算法计算每一对顶点间的最短路径。

(3)找出从每一个顶点出发到其余各顶点的最短路径中的最长路径。 (4)在这n条最长路径中找出最短的一条，则它的出发点即为所求。 具体算法如下：

inthospital(intn，int C[][]，int A[][]) //C为邻接矩阵，A是路径长度矩阵 {

inti，j，k，m，s； for(i＝0；i

for(k＝0；k

if(A[i][k])+A[k][i]

for(i＝1；i

s=0；

for(j＝0；js) s=A[i][j]；

if(s

m=s； k＝i； } }

return k； //返回所求村庄序号 }

实例分析：最初的邻接矩阵为

学习必备 欢迎下载

经过Floyd算法处理之后，求出每一对顶点之间的最短路径，原邻接矩阵变换为

由矩阵可见，每列中的最大值依次为：9，9，6，7，9，9，其中的最小值为6。因此医 应该选村庄v3，使得离医院最远的村庄到医院的路径最短。