导言：
图是数据结构教材上的最后一种数据结构了，它的使用范围最广，最多，也是最贴合我们实际生活的，图是一个多对多的数据结构，在前面的学习，了解到了一对一的数据结构----线性结构，以及一对多的结构----树形结构，现在要学的多对多的结构----图，
图是对我们现实生活中很多实体的抽象，因为实际的生活中，的确关系是复杂多样的，它们之间的联系，使用多对多的结构来表示是再好不过的
一.图的定义
什么是图？
表示多对多的关系
包含：
一组顶点：通常使用V（Vertex）来表示顶点集合
一组边：通常使用E（Eage）表示边的集合
- 边是顶点对<v，w> ∈E，其中v，w ∈V
- 有向边<v，w>表示从v指向w的单向边（单行线）
- 不考虑重边和自回路
抽象数据类型的数据定义：
数据名称：图
数据对象集：G（V，E）由一个非空的有限顶点集合v和一个有限边集合E组成
操作集：对于任意图，G∈Graph，以及v∈V，e∈E
常见的图有：有向图，无向图
有向图的特点是单路径可达，也就是两个顶点所在的单条边上，只有箭头指向的方向才可以到达，反之则是不可达的
而无向图的特点是有边即可达，它是没有方向的区分的，两节点都可以通过这条边互相访问，
在边的基础上还有一个权重的概念，在边上有一个值，这个值在实际生活中可能代表着不同的东西，比如两点间的距离，两点的关系程度等等
图的表示方法数组
邻接矩阵表示：邻接矩阵其实就是一个二维表G[N][N]，N指的是顶点个数，即从0~N-1个顶点
其中，从一个点出发，0代表不可达，1表示可达
G[i][j] = 1 时，<vi，vj>之间有边，=0则无边
如上图：
这就是我们通过邻接矩阵来表示的一个无向图，
在邻接矩阵中有一条斜线，就是灰色的，它的值全为0，这是因为，我们默认的图都是没有自回路的，所以它自己到不了自己
然后再观察被灰色的斜线分开的两部分，它们是对称的，这就是说，我们使用邻接矩阵来存储图，每次都有大概一半空间是浪费的
后面就要着手怎么减少这一半的空间浪费？最简单的方式就是只存储上三角矩阵或者只存储下三角矩阵
使用一个长度为N*(N+1)/2的一维数组来存储
例如 原矩阵中的点 Gi j 它在一维数组的位置是A（i*（i+1）/2+j）
对于数组中的值，既可以是0和1，也可以是后面会用到的权值
如上图：
我们采用一维数组A来存储下三角矩阵
我们可以来简单计算一下 V [5][1] 它在一维数组中的位置
5*（5+1）/2+1 = 16
故此节点在一维数组的位置是A [16]
使用邻接矩阵实现图的好处：
- 直观，简单，便于理解
- 方便检查任意节点
- 方便找到任意节点上的所有结点
- 方便计算任意结点的度
它的缺点也很明显：那就是很浪费空间，对于稀疏矩阵来说，还比较浪费时间
图的表示方法链表
对于图的表示，不仅仅是可以使用数组，还可以使用链表
但是，使用链表表示是有局限性的，链表表示它得有两个域，数据域和指针域，所以说，链表表示要比矩阵直接多了一倍的空间
如果使用链表表示图，那么此图一定要满足是稀疏的，因为稀疏图在矩阵中很占空间的原因是无效的 0 边太多
而链表的优势就是只记录有用的 1 边，对于稀疏图，链表的优势就体现出来了，虽然需要两倍空间，但是记录的值少了
如上图：
便是使用链表实现的图，可以看到除了链表需要两个域之外，它依旧有重复的数据
比如结点2可以到结点1，所以链表上记录了，但是在结点1上又记录了结点2，它们的意义相同，但是却记录了两次
邻接表的优点：
- 方便找任意结点的邻接结点
- 节约稀疏图的空间
- 方便计算任意顶点的度
小结：关于图的表示，书上只写了两种方法，但是实际上的表示多种多样，五花八门，具体怎么表示，还是依赖于你使用的图是什么样的
二.图的遍历
图的遍历指的是对图中的每个元素进行访问，且不重复
图的遍历可以解决生活中很多问题，比如迷宫，最优路径等等，
当然，得取决于你的遍历方式是什么样的，我们现在使用最多的两种方式就是深度优先DFS和广度优先BFS
深度优先DFS
如上图：为深度优先遍历
深度优先的步骤：
第一步，我们需要给定一个结点，然后入栈，压入栈中
第二步，把刚刚入栈的元素的一个相邻元素也压入栈中，如果存在多个，可以随便定义一个规则压入栈中
第三步，继续压入栈中一个元素
第四步，重复第三步
第五步，继续压入栈中一个元素，此时以当前结点是没有没入栈的结点了
第六步，出栈一个元素，以栈顶元素为基准，如果有它的邻接点未入栈的，继续入栈
第七步，重复第六步
最后，当栈中元素只有起点时，且起点周围都没有没入过栈的元素时，出栈起点元素，深度遍历完成
伪代码描述：
void DFS(Vertex V){
Visted[V]=true;
for(V的每个邻接点W){
if(!Visted[W])
DFS(W);
}
}
广度优先BFS
如上图：广度优先遍历
遍历步骤：
第一步，入队一个起点元素
第二步，出队队列中的一个元素，并且遍历它，然后入队它的相邻元素，注意，是直接相连的所有结点
第三步，重复第二步
第四步，当结点的相邻元素入过队了，就不用入队了，只入队没有进入过的
最后，当队列为空时，最后一个结点的邻接点都入过队，那么遍历完成
伪代码描述：
viod BFS（Vertex V）{
visited[V]=true;
InQueue(V,Q);
while(!IsEmpty(Q)){
V=delQueue(Q);
for(V的每个相邻结点W){
visited[W]=true;
InQueue(W,Q);
}
}
}
图的相关定义
连通：如果v和w之间存在一条无向路径，则称v和w是连通的
路径：v到w之间的顶点集合，其中任两结点间都有图中的边，路径的长度是路径中的的边数（有权值是要对应乘上权值），如果v到w的所有顶点都不同，则称简单路径
回路：起点等于终点的路径
连通图：任意两顶点都连通
连通分量：无向的极大连通图
- 极大顶点数：再加一顶点后图就不连通了
- 极大边数：包含子图中的所有顶点相连的所有边
强连通：有向图中顶点v和顶点w之间存在双向路径，称v和w是强连通
强连通图：有向图中任意两点都强连通
强连通分量：有向图中极大连通子图
拓展：对于本就不连通的图我们怎么遍历？
思路：我们不在以一个连通分量为单位遍历，而是以图的顶点集合
因为不管是BFS还是DFS都是以连通分量为单位遍历的，如果两个连通分量就无法完全遍历这个图了，但是不是每个图都是一个完整的连通分量，也有多个连通分量
所以我们对于不连通的图选择使用把此图的顶点集合遍历完成后才算结束遍历
伪代码描述：
void DFS(Vertex V){
Visted[V]=true;
for(V的每个邻接点W){
if(!Visted[W])
DFS(W);
}
}
void ListComponents（Graph G）{
for（each V in G ）{
if(!visited[V]){
DFS(V); // or BFS
}
}
}
此时，ListComponents函数就用于多个连通分量图的控制
对每个连通分量进行BFS或者DFS遍历
这样就可以做到不连通的图依旧可以完全遍历了
三.图的实现操作
用邻接矩阵表示图，
我们怎么确定两点之间是否有边呢？其实我们可以使用G [ i ] [ j ] ，它就是代表二维数组中的一个点，但是它的i值对应图中的一个顶点，并且它的j值对应的图中的另一个顶点，
所以基于这个特点，只要G [ i ] [ j ] 点为 1 的时候就定义图中的 i 顶点 和 j 顶点是有边，为 0 的时候就定义它是无边的
#define MaxI 10
#define MaxJ 10
typedef int WeightType;
typedef struct GNode* PtrToGNode;
struct GNode
{
int Ne; //边数
int Nv; //顶点数
WeightType G[MaxI][MaxJ]; //确定两顶点是否有边
// DataType Data[MaxI]; //存放顶点数据域
};
typedef PtrToGNode MGraph;
如上代码：
GNode 结构体就是核心块，它用于标识每一个顶点
图的初始化
上面的代码描述了一个图的结构，仔细看看内部的代码，就会知道核心还是一个二维数组在存储顶点，然后Ne是存储当前的已有边数，Nv是存储的顶点数
所谓图的初始化，其实就是需要先把二维数组构建出来，
此时不知道那两个顶点是有边的，所以在构造的时候，初始化肯定二维数组的元素都是 0
且变数也是 0
typedef int Vertex;
MGraph createGraph(int VertexNum) {
Vertex v, w; //顶点
MGraph mGraph; //构造的图结构体
mGraph = (MGraph)malloc(sizeof(struct GNode));
mGraph->Nv = VertexNum;
mGraph->Ne = 0;
//二维数组顶点清 0
for(v = 0;v<mGraph->Nv;v++)
for (w = 0; w < mGraph->Nv; w++) {
mGraph->G[v][w] = 0;
}
return mGraph;
}
如上代码：
创建图的函数要传入的参数就是顶点的个数，以顶点数来构造二维数组的大小
向图中插入边
插入边，在这里被抽象成了也就是二维数组是有值的，二维数组的下标就对应了图的顶点，类似的图的两顶点之间才存在边
所以在插入边操作的时候，很自然的传入函数中两个顶点，对应的在二维数组描述的图中，做出相应的更改
typedef struct ENode* PtrToENode;
struct ENode
{
Vertex v1;
Vertex v2;
WeightType weight;
};
typedef PtrToENode Edge;
void InsertEdge(MGraph mg, Edge e) {
// 插入边
mg->G[e->v1][e->v2] = e->weight;
// 无向图还要反向插入一条
mg->G[e->v2][e->v1] = e->weight;
}
在插入边的时候也构造了一个结构体，此结构体是专门用于记录边属性的
v1和v2就是其中的顶点，weight是权重
当在插入边的时候，如果无权重，可以选择插入 1 用来标识顶点间有边
完整的建立一个图
需要完整的建立一个图，首先要清楚，需要那些操作，很简单，就是初始化和插入操作
初始化操作很显然需要知道有多少个顶点
而插入操作则是需要知道边，也就是那两个顶点是有边的
基于上面的分析，就可以知道在建立的实训需要那些参数，很显然，需要总顶点数和总边数，以及每个边的属性
MGraph BuildGraph() {
MGraph Graph;
Edge E;
Vertex V;
int Nv, i;
scanf_s("%d", &Nv);
Graph = createGraph(Nv);
scanf_s("%d", &(Graph->Ne));
if (Graph->Ne !=0)
{
E = (Edge)malloc(sizeof(struct ENode));
for (i = 0; i < Graph->Ne; i++) {
scanf_s("%d %d %d", &E->v1, &E->v2, &E->weight);
InsertEdge(Graph, E);
}
}
/*
* //当顶点有数据的时候插入
for (i = 0; i < Graph->Nv; i++) {
scanf_s("%d", &(Graph->Data));
}
*/
return Graph;
}
建立图时输入的格式：
Nv（总顶点数） Ne（总边数）
v1 v2 weight
........
四.拓展且实现
已知先序，中序序列直接求后序序列
在前面的学习中，可以通过递归的使用栈结构来完成树的先序，中序，后序遍历，
并且在给定两个序列的情况下，可以把后面一个序列手写出来
如上图，就是通过已知先序和中序序列写出来的后序序列
那么这样的操作怎么使用代码来描述呢？
1 // 已知先序序列，中序序列,构造后序序列
2 void solve(int preL, int inL, int postL, int n) {
3 //pre：先序序列 in：中序序列 post：后序序列
4 //preL：当前元素在先序序列的位置
5 // inL：当前元素在中序序列的位置
6 //postL：当前元素在后序序列的位置
7 if (n == 0)
8 return;
9 if (n == 1)
10 {
11 post[postL] = pre[preL];
12 return;
13 }
14 root = pre[preL];
15 post[postL + n - 1] = root;
16 int L,R;
17 for (int i = 0; i < n; i++) {
18 if (in[inL + 1] == root) {
19 L = i;
20 break;
21 }
22 }
23 R = n - L - 1;
24 solve(preL + 1, inL, postL, L);
25 solve(preL + L + 1, inL + L + 1, postL + L, R);
26 }
第7行代码表示，当一个结点左右都没了元素，说明到底了，就回溯
第9行代码表示，只有一个元素在根结点前面，那么此结点就直接插入到后序序列中
后面的代码执行表示序列中存在多个元素，那么就要考虑是否还存在其它子树或者左节点和右结点分别是那个
第17行的代码是用来在中序序列中找根结点的，只要找到了根节点的位置，基本可以确定以此根结点左边有多少元素，右边有多少元素
再后面的代码则是继续递归的计算左子树和右子树结点的位置
计算完全二叉树而左子树规模
如上图，在完全二叉树的非叶子结点层中，总有 2 的 h 次方 - 1 个结点 （h指的是非叶子结点层数）
基于这个特性，可以很简单的计算出左子树的非叶子结点层的结点树，那就是 (2h - 1) / 2
对于叶子结点则需要考虑X的值是多少，它的取值范围应该是 0 ~ 2h-1
为0 很明显表示无叶子结点层 2h-1则表示左子树的叶子结点层是满的，也是左子树的最大取值
所以在求X的时候，应该考虑到结果是否比2h-1大，如果大，那么左子树就取值2h-1否则就取值X
如上图，总结点有 9 个 ，非叶子结点层的结点有 2h-1 = 7 个
9 - 7 = 2
2h-1 = 4
4 > 2
则左子树的规模为 (2h - 1) / 2 + 2 = 7 / 2 + 2 = 3 + 2 = 5
上图中以根结点为准左子树的规模就是 5
无权单源最短路径
无权单源最短路径的计算方式是根据单一的起点，借助队列，将元素入队，在出队一个元素的时候把此元素可达且路径为直连的元素入队
其实这就是广度优先算法，它探索了所有的结点到结点的可能性，把所有的路径都给列举出来了
void UnWeighted(Vertex s) {
Enqueue(s, Q);
while (!IsEmpty(Q))
{
v = Dequeue(Q);
for(v 的每一个邻接结点 w)
if (dist[w] == -1) {
dist[w] = dist[v] + 1;
path[w] = v;
Enqueue(w, Q);
}
}
}
如上代码：
dist[ ] 数组用来记录起点到当前结点的路劲长度
path[ ] 数组用来记录此结点的前一个结点，可以用来复刻路径
图的最小生成树
解决图的最小生成树问题，一般使用贪婪算法来解决，它需要的是最小生成树，换言之就是权重最小的树，如果每一次连接都是权重最的，那么总体上来说权重应该是比较小的
贪婪算法解决此类问题很明显的一个优势就是通俗易懂且算法编写起来很快，并且它是按照一般的解题思想来做的，相对于其它算法又有科学性
使用贪婪算法解决最小生成树的约束
- 只能用图里有的边
- 只能正好用掉 | V | - 1 条边
- 最小生成树无回路
Prim算法
Prim算法的解决思路是让一棵小树慢慢成长为一棵大树
在给定一个图中的一个起点的时候，需要在这个起点的基础上，找出和它直连顶点间，边最小的，然后收录这个顶点，在以被收录顶点为开始，重复以上操作
伪代码描述Prim算法：
1 void Prim(){
2 MST = {s}; //初始化一棵最小树
3 while(1){
4 v = 未收录顶点中dist的最小值;
5 if(不存在这样的v){
6 break;
7 }
8 将v 收录到MST中
9 dist[v] = 0 ;//标记无权重，表示已访问
10 for(v的每个邻接点){
11 if(dist[w]!=0)
12 if(边的权重<dist[w]) //连通的两顶点
13 {
14 dist[w]=边的权重;
15 parent[w]=v;
16 }
17 }
18 }
19 if(MST收录的顶点没有 |v| 个)
20 Error("图是非连通的");
21 }
第10行代码以前的代码都是把一个存在的新结点收录到最小生成树集合中，重点看看第10行以后的代码
第11行代码描述的是邻接结点没被访问的情况
第12行代码描述的是两顶点是连通的，因为初始化的时候，如果两顶点不连通是正无穷，如果不连通，则是 65535 和 65535 比较，很显然此行代码就不成立
第13行代码就是，开始收录新找到的结点，当然是满足以上条件的顶点
第19行代码如果顶点数比图的总顶点数少，说明图中有未连通的顶点，最小生成树要是在一个连通图中构成
Kruskal算法
这种算法适合解决稀疏图，并且顶点和边数无限接近，比如顶点有 n 个 ，那么边数 大于等于 n - 1 条
它的思想是小树汇聚成森林，在图中，每个单一顶点都可以被认定为一棵树，通过对边的选取，慢慢把这些树进行连接
与Prim算法不同的是，Prim算法每次收录的是可达的顶点，Kruskal算法每次收录的都是权值最小的边
如上图：
通过收录边来构造最小生成树，重点看一下第 4 步，为什么要把4和2之间的边收录，因为最小生成树在图中，不仅要在图中不造成回路，还要使得在图中每个顶点是连通的，
所以在第三步收录了 2-3 号边的时候，看起来顶点2和顶点4貌似已经在最小生成树中了，实则不然，因为此时它们是两颗树，所以在第 4 步将它们 2 - 4 号边也收录了，这样四个顶点才在一棵最小生成树中
然后继续寻找权值相对最小的收录边，完成小树构成森林
伪代码描述：
void Kruskal(Graph G){
MST = { }; //选取边的集合
while(MST找不到 |v|-1 条边 && E 中还有边){
从E中选取一条权值最小的边e;
将e从E中删除;
if(e不在MST中构成回路) {
将e加入MST;
}
else{
无视e的存在;
}
if(MST中不到 |v|-1 条边)
Error("图不连通");
}
}
注意Kruxkal算法的 MST 集合是用来收集边的，其它的算法思想和Prim算法都是差不多的
它们二者都是贪婪算法的代表
-
-
-
-
博客编辑于
---------------------浙江大学陈越老师《数据结构》
标签：连通,遍历,元素,结点,算法,顶点,数据结构,之图 From： https://www.cnblogs.com/5ran2yl/p/17495834.html