数据结构篇_编程思想板块_第五章图

• 编程思想板块最主要的内容是数据结构经典题目及解答题目所需的编程思想，愿对您能有所帮助

五、图

1）存储

1. 在简单运用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可忽略）

2. 当邻接矩阵的元素仅表示相应边是否存在时，数组的类型可采用0和1的枚举型

3. 当无向图的邻接矩阵是对称矩阵，对规模大邻接矩阵可采用压缩存储

4. 不同存储在图算法中的应用：

①　邻接矩阵很方便访问任意两点的边，但是不方便计算其邻接点；在深度和广度遍历中广泛的需要求某点的邻接点；所以邻接矩阵只在Floyed和Prim和Dijstra中采用

②　邻接表能很方便的求某顶点的邻接点，索引对于与遍历有关的算法大多都采用邻接表；如深度、广度、拓扑排序、关键路径。但他也有不足的地方，就是不方便求入度或是那些点可以到他的操作，所以有人引进逆邻接表

③　最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图， 另一个是存储无向图，在十字链表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中，凡是能用邻接表实现的一定能用十字链表和邻接多重表实现，并且它们的存储效率更高。

2）图的遍历

1．为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组 visited[ ]来标记顶点是否被访问过，初始状态为FALSE，访问过程中一旦某个结点被访问，就立即设为TRUE

2．对于同样一个图，基于邻接矩阵的遍历所得到的 DFS序列和 BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和 BFS序列是不唯一的

3．图的广度优先搜索的过程与二叉数的层次遍历是完全一致的

4．题目问？搜索得到的生成树的答案是一棵树（画图），并不是像遍历答案那样写出来

5．判断有向图有回路的主要方法：

①　深度优先遍历

②　拓扑排序

3）最小生成树

1. 构造算法常用性质：假设G=（V,E）是一个带权连通无向图，U是顶点集V的一个非空子集，若（u,v）是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一颗包含边（u,v）的最小生成树

（1）Prim(普里姆)算法

1. 算法思想：任取一顶点T加入，之后选择一个与当前T中顶点集合距离最近的顶点，依次进行下去直至全部图中所有顶点都并入T

2. 时间复杂度为O(|V|^2)

3. 因为与途中边的数目没有关系，即顶点数相同，不管边数都相同，故适合求解边稠密的图的最小生成树

（2）Kruskal（克鲁斯卡尔）算法

1. 算法思想：每次选择未加入T中的权值最小的边加入，直至T中所有顶点都在一个分量上（加入过程中不必保证T中都是连通的）

2. 通常在此算法中采用堆来存放边的集合，因此每次选择最小权值边只需O(log|E|)的时间

3. 时间复杂度为O(|E|log|E|)

4. 因为与结点的数目没有关系，即边数一定，不管顶点数复杂度都相同，故适合边稀疏而顶点较多的图

4）最短路径

1. 图遍历中广度优先搜索查找最短路径只对于无权图而言

2. 构造算法常用性质：两点之间的最短路径也包含了路径上其他顶点间的最短路径

（1）Dijkstra(迪杰斯特拉)求解单源最短路径问题

1. 算法思想：

①　初始化操作：假设从v0开始，设置三个数组：分别是final数组(标记各顶点是否能找到最短路径，可则设为True，最初是有v0能设为True（最先开始只能确定自己跟自己）),dist数组（目前为止能找到的最优路径长度，最初只有与v0直接相连的顶点才有权值填上，其他都为无穷），path数组（每个顶点在最短路径上的直接前驱，可以直接填0表示V0结点等，若无则设为-1）

②　第一轮：循环遍历所有结点，找到还没确定最短路径且dist最小的顶点v_i，令final[i]=true（表示现在可以确定v_i的最短路径就是dist[i]且它的直接前驱就是path[i]）

③　检查所有与v_i邻接的顶点，若其final值为false，则更新dist和path信息

④　第二轮：重复②③（只对final值还为false的点进行操作）

⑤　最后通过path可知两个顶点间的最短带权路径

1. 每一轮可确定一个顶点的最短路径，故需操作n-1次

2. 与Prim算法的相似之处：前者的dist数组存储的是当前最短路径，后者的lowcast数组存储的是当前最小权值

3. 不适用于边上带有负权值的

4. 几个不同问题概念的比较：

①　单源最短路径问题:已知有向带权图，求从某个源点出发到其余各个顶点的最短路径

②　单目标最短路径问题:将图中每条边反向，转换为单源最短路径问题

③　单顶点对间最短路径问题:以分别对不同顶点转换为单源最短路径问题

④　所有顶点对间最短路径问题:分别对图中不同顶点对转换为单源最短路径问题

（2）Floyd（弗洛伊德）求各顶点之间最短路径问题

1. 算法思想（运用了动态规划思想）：

①　初始化操作：设置两个矩阵（二维数组）：矩阵A(目前能找到的各个顶点间最短路径长度，初始时不允许在其他顶点中转，主对角线值为0，无路径则为无穷)，矩阵path（目前能找到的两个顶点之间的中转点，初始时都为-1即都没有中转点）

②　设置允许在V0中转时，更新A和path：遍历矩阵A，对于A中每一个元素都需要进行例如A[2][1]，则判断A[2][1]>A[2][0]+A[0][1]吗，大于则更新A[2][1]的操作，并把相应path值更新为0

③　再设置允许V1进行中转,重复②依次允许下去，直至每个结点都允许了一遍

④　每次操作都是基于上次选取的允许中转点的基础上进行更新矩阵A和path，故输出路径时要注意把当前path值和之前经历过的允许中转的点一并为最短路径；若path值为-1则表示两个结点之间没有中转点就是最短路径了

1. 允许图中带有负权值的边，但不允许有包含带负权值的边组成的回路

注：也可用Dijkstra算法求所有顶点间的最短路径，重复|V|次即可，总的时间复杂度也是O(|V|^3)

5）答题（画图）格式

6）图经典题目的编程思想

1. 如何对无环有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上?

答：按各顶点的出度进行排序。n个顶点的有向图，其顶点的最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即只要存在弧<i,j>，就不管顶点j的出度是否大于顶点i的出度，都把i编号在顶点j的编号之前，因为只有i≤j、弧<i,j>对应的1才能出现在邻接矩阵的上三角

2. 下面是一种称为“破圈法”的求解最小生成树的方法:所谓“破图法”，是指“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止.这种方法是正确的,说明理由（学习该题的证明过程）

答：由于经过“破辫法”之后，最终没有回路，故一定可以构造出一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为T，假设T不是最小生成树，则必然存在最小生成树T0，使得它与T的公共边尽可能地多，则将T0与T取并集，得到一个图,此图中必然存在回路，由于“破圈法”的定义就是从回路中去除权最大的边，此时生成的T的权必然是最小的，这与原假设T不是最小生成树矛盾，从而T是最小生成树

3. 试设计一个算法，判断一个无向围G是否为一棵树。若是一棵树，则算法返回true,否则返回false

算法思想：

一个无向图G是一棵树的条件是，G必须是无回路的连通图或有n-1条边的连通图。这里

采用后者作为判断条件。对连通的判定，可用能否遍历全部顶点来实现。可以采用深度优先搜索算法在遍历图的过程中统计可能访问到的顶点个数和边的条数，若一次遍历就能访问到n个顶点和n-1条边，则可断定此图是一棵树

4. 写出图的深度优先搜索DFS算法的非递归算法(图采用邻接表形式)（非递归和栈常用于实现递归）

算法思想：

在深度优先搜索的非递归算法中使用了一个栈S来记忆下一步可能访问的顶点，同时使用了一个访问标记数组visited[i]来记忆第i个顶点是否在栈内或曾经在栈内,若是则它以后不能再进栈

注意:由于使用了栈，使得遍历的方式从右端到左端进行，不同于常规的从左端到右端，但

仍然是深度优先遍历

5. 分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在由顶点y到顶点y的路径(i≠j)。注意，算法中涉及的图的基本操作必须在此存储结构上实现

6. 假设图用邻接表表示，设计一个算法，输出从顶点Vi到顶点Vj的所有简单路径