longpathlen=pathlen;
}
}
else
{ path[pathlen]= b->data;    //将当前结点放入 路径中
pathlen++;    //路径长度增 1
Longpath(b->lchild,path,pathlen,longpath,longpathlen); // 递归扫 描左子树 Longpath(b->rchild,path,pathlen,longpath,longpathlen); // 递归扫描右子 树 pathlen--;    //环境恢复
}
}

四、图

大纲要求：

（一） 图的概念
（二） 图的存储及基本操作
1    1. 邻接矩阵法
2    2. 邻接表法
（三） 图的遍历
3    1. 深度优先搜索
4    2. 广度优先搜索
（四） 图的基本应用及其复杂度分析
5    1. 最小（代价）生成树
6    2. 最短路径
 
7    3. 拓扑排序
1    4. 关键路径 知识点：
1．图的基本概念，包括：图的定义和特点、无向图、有向图、入度、出度、完全图、生成树、 路径长度、回路、（强）连通图、（强）连通分量等概念。掌握与这些概念相联系的相关 计 算题。在基本概念中，完全图、连通分量、生成树和邻接点是重点。
2．图的存储形式。图是复杂的数据结构，有顺序和链式两种存储结构：数组表示法（重 点是邻接矩阵），邻接表与逆邻接表，这两种存储结构对无向图和有向图均使用。
3．熟练掌握图的两种遍历算法：深度遍历和广度遍历。深度遍历和广度遍历是图的两种 基 本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于 二叉树一章的重要性。 掌握图的两种遍历算法的应用，图一章的算法设计题常常是基于这两种基本的遍历算 法 而设计的。例如，在（强）连通图中，主过程一次调用深（广）度优先遍历过程
（DFS/BFS），即可遍历全部顶点，故可以用此方法求出连通分量的个数，要会画出遍 历 中形成的深（广）度优先生成树和生成森林。又如，“求最长的最短路径问题”和 “判 断两顶点间是否存在长为K的简单路径问题”，就用到了广度遍历和深度遍历算法。
4. 最小生成树的概念。连通图的最小生成树通常是不唯一的，但最小生成树边上的权值 之 和是唯一的。掌握最小生成树的构造方法：PRIM算法和KRUSKAL算法，根据这两种算 法思想用图示法表示出求给定网的一棵最小生成树的过程。
5. 拓扑排序是在有向图上对入度（先、后）为零的顶点的一种排序，通常结果不唯一。拓 扑 排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句 话说，一种是“从前向后”的排序，一种是“从后向前”排。后一种排序出来的结果 是“逆拓扑有序”的。用拓扑排序和深度优先遍历都可判断图是否存在环路。
6. 关键路径问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键 路 径，二是最早时间的含义及求解方法，三是最晚时间的含义及求解方法。简单地说， 最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求 解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。 熟 练掌握求解的过程和步骤。关键路径问题是工程进度控制的重要方法，具有很强的 实用 性。理解“减少关键活动时间可以缩短工期”是指该活动为所有关键路径所共有， 且减 少到尚未改变关键路径的前提下有效。
7. 最短路径问题也是为图一章的难点问题。最短路径问题分为两种：一是求从某一点出
发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。解决第一个问题 用DIJSKTRA算法，解决第二个问题用FLOYD算法，注意区分。掌握这两个算法，并能手 工熟练模拟。掌握用求最短路径问题来解决的应用问题（如旅游景点及旅游路线的选 择问题）。

练习题：

（一）选择题：

1.    下列哪一种图的邻接矩阵是对称矩阵？（    B    ）
 






3.    有 n 个结点的无向图的边数最多为（ B    ）
A．n+1    B．n(n-1)/2       

4.    C．n(n+1)    D．2n(n+1)
在一个图中，所有顶点的度数之和与图的边数的比是（ C   
）   
    A．1:2    B．1:1
C．2:1    D．4:1               
5.    已    知    有    向    图    G=(V,E)        ，    其    中
V={v1,v2,v3,v4,v5,v6,v7}，E={<v1,v2>，<v1,v3>，<v1,v4>，<v2,v5>，<v3,v5>，
<v3,v6>，<v4,v6>，<v3,v7>，<v6,v7>}，G 的拓扑序列是（    A    ）。
A．v1,v3,v4,v6,v2,v5,v7    B．v1,v3,v2,v6,v4,v5,v7
C．v1,v3,v4,v5,v2,v6,v7    D．v1,v2,v5,v3,v4,v6,v7
6.    在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。
A．n    B. n+1
C. n-1    D. n/2
7.    简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有 n 个结点，其 邻接矩阵为 A[1…n,1…n]，且压缩存储在 B[1…k]，则 k 的值至少为（ D ）。 A． n(n+1)/2    B. n2/2
C. (n-1)(n+1)/2    D. n(n-1)/2
分析：简单无向图的邻接矩阵是对称的，且对角线元素均是 0，故压缩存储只须存储 下三角或上三角（均不包括对角线）即可。
8.    无向图中一个顶点的度是指图中（ C ） A．通过该顶点的简单路径数 B．通过 该顶点的回路数 C．与该顶点相邻接的 顶点数 D．与该顶点连通的顶点数
9.    一个含有 n 个顶点和 e 条边的简单无向图，在其邻接矩阵存储结构中共有（ D ）个零 元素。
A．e
B.    2e
C.    n2-e
D.    n2-2e
10. 若采用邻接矩阵来存储简单有向图，则其某一个顶点 i 的入度等于该矩阵（ D ）。
A．第 i 行中值为 1 的元素个数
B. 所有值为 1 的元素个数
C．第 i 行及第 i 列中值为 1 的元素总个数 D． 第 i 列中值为 1 的元素个数
11. 若一个具有 n 个结点、k 条边的非连通无向图是一个森林（n>k），则该森林中必有（
C ）棵树。
A．k    B. n
 
C. n-k    D. n+k
12. 若 G 是一个具有 36 条边的非连通无向图（不含自回路和多重边），则图 G 至少有（ B
）个顶点。
A．11    B. 10
C. 9    D. 8

（二）应用题

1、用深度优先搜索遍历如下图所示的无向图，试给出以 A 为起点的顶点访问序列（同一个 顶点的多个邻点，按字母顺序访问），并给出一个最小生成树。


      

 


答： 最小生成树
：

A    B    C
4
4
7
D    E    4    F    G
3
2    1    4    5
H    I    J

深度优先搜索顶点访问序列：A    B    E    D    H    I    F    C    G    J 2. 下面是求无向连通图最小生成树的一种方法。
将图中所有边按权重从大到小排序为（e1,e2,…,em）
i:=1
WHILE (所剩边数 >=顶点数) BEGIN
从图中删去 ei
 
若图不再连通，则恢复 ei
i:=i+1 END.
试证明这个算法所得的图是原图的最小代价生成树。

答: 无向连通图的生成树包含图中全部 n 个顶点，以及足以使图连通的 n-1 条边。而最小生 成树则是各边权值之和最小的生成树。从算法中 WHILE（所剩边数>=顶点数）来看，循环到 边数比顶点数少 1（即 n-1）停止，这符合 n 个顶点的连通图的生成树有 n-1 条边的定义； 由于边是按权值从大到小排序，删去的边是权值大的边，结果的生成树必是最小生成树； 算法中“若图不再连通，则恢复 ei”，含义是必须保留使图连通的边，这就保证了是生成 树，否则或者是有回路，或者成了连通分量，均不再是生成树。

3. 对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素 有哪些？ 答：遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情 况下邻接点 的顺序不同。

4、一个带权连通图的最小生成树是否唯一？说明在什么情况下最小生成树有可能不唯一？ 答：一个带权连通图的最小生成树有可能不唯一。当图中依附于某个顶点的多条边出现权 值相同的边时，就有可能得到的最小生成树不唯一。这里所说的最小生成树不唯一，是指 生成树的形状不唯一，这些生成树的权值之和应该是相同的。


5. 已知加权有向图 G 的邻接矩阵如下：
 
    15    2
 
12    
 
    
 
        6        

 
        
        
 
    8    4    
        
 
        3
 
        

        
 
            9 

    5        10
 
    
 
    4    
 
            