数据结构--图
0.什么是图？
<0>：表示“多对多”的关系
<2>：包括
i：一组顶点：通常用V（Vertex）表示顶点的集合
ii：一组边：通常用E（Edge）表示边的集合
（1）：边是顶点对：其中v-------w
（2）：有向边
（3）：不考虑重边和自回路
<3>：图的两种定义
i：二元组定义：一张图G是一个二元组(V, E)，其中V称为顶点集，E称为边集。他们也可以写成V(G)和E(G)。E的元素是一个二元组对，用(x, y)表示，其中.
ii：三元组定义：一张图G是一个三元组(V, E, I)，其中V称为顶点集(Vertices set)，E称为边集(Edges set)，E与V两两不相交；I称为关联函数，I将E中的每一个元素映射到V x V。如果I(e)=(u, v)()那么称边e连接顶点u，v，而u，v称为e的端点，u，v此时关于e相邻。同时若两条边i，j有一个公共顶点u，那么称i，j关于u相邻。
1.图的分类
<1>：有向图、无向图
如果给图中每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点又有始点和终点之分。相反，边没有方向的图称为无向图。
<2>：简单图
一个图如果：
1.没有两条边，它们所关联的两个点都相同
2.每条边所关联的是两个不同的顶点。
则称为简单图。简单的有向图和无向图都可以使用以上的“二元组定义”。但形如（x, x）的序对不属于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)，度和边的关系有：.
（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)
4.如何表示一个图？
数据对象集：G(V, E)由一个非空的有限顶点集合V和一个有限边集合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的最小生成树
邻接矩阵、邻接表
（0）：邻接矩阵G[N][N]----N个顶点从0~N-1编号。
G[i][j] = 1 （若
对于有向图可以这么存储，但是对于无向图来说，G[i][j] = G[j][i]，所以会造成极大的空间浪费，故此，对于无向图我们可以使用一个长度为N(N+1)/2的一维数组A进行存储，G[i][j]在A中对应的下标为：(i*(i+1)/2+j)，对于网络，我们只要把G[i][j]的值定义为
文章图片
(1)：临界矩阵的优劣：
i：好处：
（2）：邻接表：G[N]是一个指针数组，对应矩阵每行一个链表，只存非零元素。对于网络，结构中要增加权重的域。
1.直观，简单，好理解
2.方便检查任意一堆顶点之间是否存在边
3.方便寻找人一丁点的所有"邻接点"
4.方便计算任意顶点的"度"
ii：坏处：
1.浪费空间，存在一些稀疏图
2.浪费时间
文章图片
(3)：邻接表的优劣：
i:优点：
5.图的遍历方法
1.方便查找任意顶点的所有“邻接点”
2.节约稀疏图的空间
3.方便计算无向图的任意顶点的度、对于有向图则要构造逆邻接表来方便计算出度
ii：坏处
1.不方便检查任意一堆顶点间是否存在边
<1>:深度优先搜索
1.首先将根节点放入stack中。
<2>.广度优先搜索
2.从stack中取出第一个节点，并检查它是否是目标。
i：如果找到目标，结束搜索并返回结果。
ii：否则将他的某一个尚未检验过的直接子节点加入stack中。
3.重复步骤2
4.如果不存在为检验过的直接子节点
i：将上一级节点加入stack中
ii：重复步骤2
5.重复步骤4
6.若stack为空，表示整张图都被检查过了----即途中没有所要搜寻的目标，结束搜索。
1.首先将根节点放入队列中
<3>：如果图不连通
2.从队列中取出第一个节点，并检验他是否为目标。
i:如果是目标，则结束搜索并回传结果。
ii：否则将他所有尚未检验过的直接子节点加入到队列中。
3.若队列为空，表示整张图都被检查过了----即途中没有所要搜寻的目标，结束搜索。
4.重复步骤2。
文章图片
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)最小，则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>:一般用于安排项目的工序
文章图片
