【例7-1】 设计一个算法，求不带权无向连通图G中距离顶点v最远的一个顶点（所谓最远就是到达v的路径长度最长）。

分析：

图的广度优先搜索遍历方式体现了由图中某个顶点开始，以由近向远层层扩展的方式遍历图中结点的过程，因此广度优先搜索遍历过程中的最后一个顶点一定是距离给定顶点最远的顶点。因此，只需修改广度优先搜索遍历算法，返回最后一个顶点即可。

由此可写出以下算法代码：

说明：考试时在本题代码前要加上一句“假设本题用邻接表作为图的存储结构”，以便阅卷老师对代码中结构体成员的引用的理解。

【例7-2】 设计一个算法，判断无向图G是否是一棵树。若是树，返回1，否则返回0。

分析：

一个无向图是一棵树的条件是有n-1条边的连通图，n为图中顶点的个数。边和顶点的数目是否满足条件可由图的信息直接判断，连通与否可以用遍历能否访问到所有顶点来判断。

由此可写出以下算法代码：

(www.daowen.com)

图7-9 en的变化过程

注意：最后一个if语句中的第二个表达式为什么是（G-＞n-1）==en/2，而不是（G-＞n-1）==en呢？在每次来到一个新顶点的时候，en中都累加了当前访问顶点的所有边。例如，在图7-9中，最后en等于10，正好是实际边数的两倍，可见（G-＞n-1）==en/2这种写法是正确的。

【例7-3】 图采用邻接表存储，设计一个算法，判别顶点i和顶点j（i！=j）之间是否有路径。

分析：

从顶点i开始进行一次深度搜索遍历，遍历过程中遇到j说明i与j之间有路径，否则没有路径。

算法代码如下：