（5）判断图G中是否存在边
2．假设图G采用邻接矩阵存储，分别设计实现以下要求的算法： （1）求出图G中每个顶点的入度。 （2）求出图G中每个顶点的出度
（3）求出图G中出度最大的一个顶点，输出该顶点的编号。 （4）计算图G中出度为0的顶点数。 （5）判断图G中是否存在边
4．一个连通图采用邻接表作为存储机构，设计一个算法实现从顶点v出发的深度优先遍历的非递归过程。
5．设计一个算法，求不带权无向连通图G中距离顶点v的最远顶点。
6．设计一个算法，判断无向图G是否是一棵树，若是树，返回1；否则返回0。 7．假设图采用邻接表存储，分别写出基于DFS和BPS遍历的算法来判别顶点i和顶点j（i!=j）之间是否有路径。
8．假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通，若连通则返回1；否则返回0。
9．假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的长度为1的所有简单路径。
10．假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。
11．假设图G采用邻接表存储，设计一个算法，从如图7-10所示的无向图G中
找出满足如下条件的一条路径： （1）给定起点vi和终点vj。
（2）给定一组必经点{7,9}，即输出的路径必须包含这些顶点。 （3）给定一组必避点{1,6}，即输出的路径不能包含这些顶点。
1 5 0 3 2 6 9 8 12 14 10 7 4 11 13
图7-10
12．假设图G采用邻接矩阵存储，采用遍历方法实际一个有向图的根的算法。
若有向图中存在一个顶点v，从v可以通过路径达达图中其它所有顶点，则称v为该有向图的根。
13．假设图G采用邻接矩阵存储，设计一个算法判断在给定的有向图中是否存
在一个简单有向回路，若存在，则以顶点序列的方法输出该回路（找到一条即可）。
14．采用堆排序来实现Kruskal算法，并说明时间复杂度O(elog2e)的理由。 15．如图7-11是一个城市连接图，图中权值表示两城市之间的里程（单位为100km），现要设计一条铁路贯通所有城市（即从一个任一城市可以到达其他城市）。设计一个算法，求出最小代价。假设每1km的铁路造价为1000万元。
3 4 6 0 1 2 6 5 4 5 5 3 2
1 5 6 图7-11 城市连通图
16．利用狄克斯特拉算法，设计一个可产生从指定顶点出发的最小生成树的算法。 17．设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度
定义为：MAX{从w到v的最短距离|wV(G)}如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。
18．假设图G采用邻接矩阵存储，采用弗洛伊德算法设计一个求有向图的根的
算法。若有向图中存在一个顶点v，从v可以通过路径到达图中其他所有顶点，则称v为该有向图的根。
19．设计一个算法，判断有向图是否存在回路。
20．对于一个使用邻接表存储的带权有向图G。试利用深度优先搜索方法，对该
图中所有顶点进行逆向拓扑排序。若邻接表的数据类型定义为AGraph，则算法的首部为：void dfs_topsort(AGraph *G) 若拓扑排序成功，表示图中不存在环；否则表示图中存在环。在这个算法中嵌套一个递归深度优先搜索算
法为：Dfs(AGaph G , int v)在遍历图的同时进行逆序拓扑排序，其中，v是顶点编号。
（1）给出该图的邻接表定义
（2）定义在算法中使用的全局辅助数组 （3）写出逆向拓扑排序的算法。
21．假设AOE网以邻接表方式存储，设计一个算法求该AOE网的所有关键活
动。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第7章 图习题(3)在线全文阅读。
相关推荐：