数据结构--图

0.什么是图？

<0>：表示“多对多”的关系

<2>：包括

i：一组顶点：通常用V（Vertex）表示顶点的集合

ii：一组边：通常用E（Edge）表示边的集合

（1）：边是顶点对： $（v，e）\in E，$ 其中 $v，w\in V$ v-------w

（2）：有向边<v，w>表示从v指向w的边（单行线） v------>w

（3）：不考虑重边和自回路

<3>：图的两种定义

i：二元组定义：一张图G是一个二元组(V, E)，其中V称为顶点集，E称为边集。他们也可以写成V(G)和E(G)。E的元素是一个二元组对，用(x, y)表示，其中 $x, y\in V$ .

ii：三元组定义：一张图G是一个三元组(V, E, I)，其中V称为顶点集(Vertices set)，E称为边集(Edges set)，E与V两两不相交；I称为关联函数，I将E中的每一个元素映射到V x V。如果I(e)=(u, v)( $e \in E, v \in V$ )那么称边e连接顶点u，v，而u，v称为e的端点，u，v此时关于e相邻。同时若两条边i，j有一个公共顶点u，那么称i，j关于u相邻。

1.图的分类

<1>：有向图、无向图

如果给图中每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点又有始点和终点之分。相反，边没有方向的图称为无向图。

<2>：简单图

一个图如果：

1.没有两条边，它们所关联的两个点都相同

2.每条边所关联的是两个不同的顶点。

则称为简单图。简单的有向图和无向图都可以使用以上的“二元组定义”。但形如（x, x）的序对不属于E。而无向图的边集必须是对称的，即如果 $(x, y)\in E, 那么(y, x) \in E$ .

<3>：多重图

若允许两结点间的边数多于一条，又允许顶点通过同一条边和自己关联，则为多重图的概念。它只能用“三元组的定义”。

2.关于图的一些重要的概念术语

（1）：阶(Order)：图G中顶集V的大小称为图G的阶。

（2）：子图(Sub-Graph)：图G'称作是图G的子图，如果

（3）：生成子图：满足条件V(G') = V(G)的G的子图G'。

（4）：度(Degree)：一个顶点的度是指与该顶点相关联的总边数，顶点v的度记为d(v)，度和边的关系有： $\sum_{v\in V}^d(v) = 2 \vert E \vert$ .

（5）：出度(Out-degree)和入度(In-degree)：对有向图而言，顶点的度还可分为出度和入度。一个顶点的出度为d0，是指有d0条边以该顶点为起点，或说与该点关联的出边共有d0条。入度的概念也类似。

（6）：自环(Loop)：若一条边的两个顶点相同，则此边称作自环。

（7）：路径(Path)：从顶点u到顶点v的一条路径是指一个序列v0,e1,v2,e2,.....,vk, ei的起点和重点为vi-1, vi；k称作路径长度。v0 = u。称为路径起点。vk = v,称为路径终点。如果u = v，称该路径是闭的，否则称之为开的，如果v1.....vk两两不等，则称之为简单路径(可以是闭环)。

（8）：行迹(Trace）：如果路径P(u, v)中各边各不相同，则该路径称为u到v的一条行迹。

（9）：轨道(Track)：即简单路径。

（10）：距离(Distance)：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称作从u到v的距离。否则称为u到v的距离为无穷大。

（11）：桥(Bridge)：若去点一条边，便会是的整个图不连通，该边称为桥。

（12）：拓扑排序：是一个有向无环图的所有顶点的线性序列，该序列必须满足一下两个条件：

i：每个顶点出现且只出现以此

ii：若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面

（13）：连通：如果从v到w存在一条（无向）路径，则称v和w是连通的。

（14）：连通图：图中任意两点均连通。

（15）：连通分量：无向图的极大连通子图

3.抽象数据类型定义

类型名称：图(Graph)

数据对象集：G(V, E)由一个非空的有限顶点集合V和一个有限边集合E组成。

操作集：对于任意图 $G\in Graph, v\in V, e\in E$

1.Graph Create():建立并返回空图

2.Graph InsertVertex(Graph G, Vertex v):将v插入G

3.Graph InsertEdge(Graph G, Edge e):将e插入G

4.void DFS(Graph G, Vertex v):从顶点v出发的深度优先搜索

5.void BFS(Graph G, Vertex v):从顶点v出发的广度优先搜索

6.void ShortestPath(Graph G, Vertex v, int Dist[ ]):计算图G中顶点v到任意其他顶点的最短距离

7.void MST(Graph G):计算图G的最小生成树

4.如何表示一个图？

邻接矩阵、邻接表

（0）：邻接矩阵G[N][N]----N个顶点从0~N-1编号。

G[i][j] = 1 （若<vi，vj>是G中的边），否则G[i][j] = 0;

对于有向图可以这么存储，但是对于无向图来说，G[i][j] = G[j][i]，所以会造成极大的空间浪费，故此，对于无向图我们可以使用一个长度为N(N+1)/2的一维数组A进行存储，G[i][j]在A中对应的下标为：(i*(i+1)/2+j)，对于网络，我们只要把G[i][j]的值定义为<vi, vj>的权重即可。

(1)：临界矩阵的优劣：

i：好处：

1.直观，简单，好理解

2.方便检查任意一堆顶点之间是否存在边

3.方便寻找人一丁点的所有"邻接点"

4.方便计算任意顶点的"度"

ii：坏处：

1.浪费空间，存在一些稀疏图

2.浪费时间

（2）：邻接表：G[N]是一个指针数组，对应矩阵每行一个链表，只存非零元素。对于网络，结构中要增加权重的域。

(3)：邻接表的优劣：

i:优点：

1.方便查找任意顶点的所有“邻接点”

2.节约稀疏图的空间

3.方便计算无向图的任意顶点的度、对于有向图则要构造逆邻接表来方便计算出度

ii：坏处

1.不方便检查任意一堆顶点间是否存在边

5.图的遍历方法

<1>:深度优先搜索

1.首先将根节点放入stack中。

2.从stack中取出第一个节点，并检查它是否是目标。

i：如果找到目标，结束搜索并返回结果。

ii：否则将他的某一个尚未检验过的直接子节点加入stack中。

3.重复步骤2

4.如果不存在为检验过的直接子节点

i：将上一级节点加入stack中

ii：重复步骤2

5.重复步骤4

6.若stack为空，表示整张图都被检查过了----即途中没有所要搜寻的目标，结束搜索。

<2>.广度优先搜索

1.首先将根节点放入队列中

2.从队列中取出第一个节点，并检验他是否为目标。

i:如果是目标，则结束搜索并回传结果。

ii：否则将他所有尚未检验过的直接子节点加入到队列中。

3.若队列为空，表示整张图都被检查过了----即途中没有所要搜寻的目标，结束搜索。

4.重复步骤2。

<3>：如果图不连通

6.最短路径问题

<1>：最短路径问题的抽象

在网络中，求两个不同顶点之间所有路径中，边的权值之和最小的那一条路径。

i：这条路径就是两点之间的最短路径

ii：第一个顶点是源点，最后一个顶点是终点

<2>：问题分类

i：单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径。

*：（有向）无权图

**：（有向）有权图

ii：多源最短路径问题：求任意两点间的最短路径问题

<3>：无权图的单源最短路径算法

思路：按照递增（非递减）的顺序找出到各个顶点的最短路

算法：

1.将所有点的距离Dist和Path都设为-1/无穷大

2.根据起始点，将起始点的Dist设为0

3.运用广度优先遍历的思路，依次遍历下一个顶点，并将下一个顶点的Dist在原来的上一个顶点的基础上加1，路径就是前一个顶点

4.重复3直至所有顶点遍历完，结束。

这不就是广度优先搜索码！！！！

<4>：有权图的最短路径算法

i：Dijkstra算法：（单源算法）

1.把所有顶点的路径长度设为无穷大（INFINITY），即我们不知道任何通向这些顶点的路径。

2.将给定的源点加入最小堆（优先队列）中，对于该点的所有邻接顶点进行判断，如果该点的距离小于原先的值，则将该值进行更新。

3.将该点的所有邻接顶点加入最小堆中

4.从优先队列中挑选出一个路径值最小的顶点，弹出作为新的顶点重复2，3

5.所有的顶点都被处理过，结束。

注意，Dijkstra算法是用于权值都为正的情况

ii：Floyd算法

。。。。

先分割一下，还有一些没理解到位，效率变低了一点，出去打会球！

7.最小生成树问题(Minimum Spanning Tree)

ps:最小生成树存在 <--------> 图连通

定义：最小生成树是一副连通加权无向图中一颗权值最小的生成树。

在一个给定的无向图G=（V，E）中，（u，v）代表连接顶点u与顶点v的边，而w（u，v）代表此边的权重，若存在T为E的子集且（V，T）为树，使得： $w(T) = \sum_{(u,v)\in T}^n w(u,v)$ 的w(T)最小，则T为G的最小生成树。

<1>：Prim算法---让一个小树长大(稠密图比较合算）

（1）以某一个点开始，寻找当前该点可以访问的所有的边；

（2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；

（3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；

（4）此时由所有边构成的树即为最小生成树。

<2>：Kruskal算法

1.将每个顶点放入其自身的数据集合中，按照权值的升序来选择边。

2.当选择每条边时，判断定义边的顶点是否在不同的数据集中。如果是，将此边插入最小生成树的集合中，同时，将集合中包含每个顶点的联合体取出，如果不是，就移动到下一条边。（并查集)

3.重复这个过程直到所有的边都探查过。

8.拓扑排序（AOV--Activity On Vertex）

拓扑序：如果图中从v到w有一条有向路径，则v一定排在w之前。满足此条件的顶点序列称为一个拓扑序。获得一个拓扑序的过程就是拓扑排序

AOV如果有合理的拓扑序，则必定是有向无环图（Directed Acyclic Graph, DAG）

关键路径问题：AOE（Activity On Edge）网络

<1>:一般用于安排项目的工序