数据结构（C语言版）---图
1、图相关的专业术语
1）<v,w>：从v到w的一条弧，v表示弧尾，w表示弧头，有向弧。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。2）(v,w)：无向弧。
3）有向图：有向边的有限集合。
4）无向图：无向边的有限集合。
5）简单图：不存在重复边，不存在顶点到自身的边。
6）多重图：图中某两个结点之间的边数多余一条，又允许顶点通过同一条边和自己关联。
7）无向完全图：在无向图中，任意两个顶点之间都存在边。含有n个顶点的无向完全图有n(n-1)/2条边。
8）有向完全图：在有向图中，任意两个顶点之间都存在方向相反的两条弧。含有n个顶点的有向完全图有n(n-1)条有向边。
9）生成子图：子图的顶点的集合和图的顶点集合相同。
10）连通图：无向图中任意两个顶点都是连通的。
11）连通分量：无向图中的极大连通子图。
12）强连通图：有向图中任意两个顶点都是强连通的，即从顶点v到顶点w以及从顶点v到顶点w之间都有路径。
13）强连通分量：有向图中的极大强连通子图。
14）连通图的生成树：包含图中全部顶点的一个极小连通子图。图中顶点数为n，则生成树含有n-1条边。对于生成树而言，少一条边则变成非连通图，加一条边则形成回路。
15）无向图的度：依附于该顶点的边的条数。无向图的全部顶点的度的和等于边数的2倍。
16）有向图的度：入度和出度之和。有向图的全部顶点的入度之和等于出度之和等于边数。
17）回路或环：第一个顶点和最后一个顶点相同的路径。一个图有n个顶点，有大于n-1条边，则此图一定有环。
18）简单路径：顶点不重复出现的路径。
19）简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
20）有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图。
21）关节点：在删去顶点v以及和v相关联的各边之后，将图的一个连通分量分割成两个或两个以上的连通分量，则顶点v为关节点（割点）。
22）重连通图：一个没有关节点的连通图。
2、图的存储
1）邻接矩阵法
（1）邻接矩阵存储：指用一个一维数组存储图中顶点信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。
（2）邻接矩阵表示法的空间复杂度为O(n2)，n为顶点数。
（3）特点：无向图的邻接矩阵是对称矩阵（并且唯一）。
对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。
对于有向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度（或入度）。
稠密图使用邻接矩阵的存储表示。
（4）图的邻接矩阵存储结构
#define maxvertexnum 100
typedef struct {
char vex[maxvertexnum];
int edge[maxvertexnum][maxvertexnum];
int vexnum, arcnum;
}MGraph;
2）邻接表法
（1）邻接表：指对图中的每个顶点建立一个单链表。
第i个单链表中的结点表示依附于顶点的边（对于有向图则以顶点为尾的弧），这个单链表就称为顶点的边表（对于有向图则称为出边表）。
边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）。
（2）邻接表中的结点：顶点表结点和边表结点。
顶点表
| data（顶点域） | firstarc（边表头指针） |
边表
| adjvex（邻接点域） | nextarc（指针域） |
（3）特点：若为无向图，则所需存储空间为O(|V|+2|E|)；若为有向图，则所需存储空间为O(|V|+|E|)。
稀疏图采用邻接表存储。
方便找出一顶点的邻边。
有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数，求入度需要遍历全部的邻接表。
图的邻接表表示不唯一。
（4）图的邻接表存储结构
typedef struct ArcNode{
int adjvex;
struct ArcNode * next;
}ArcNode;
typedef struct VNode {
char data;
ArcNode * first;
}VNode,AdjList[maxvertexnum];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
3）十字链表法：有向图的一种链式存储结构。
（1）十字链表中的结点：弧结点和顶点结点。
弧结点
| tailvex（尾域） | headvex（头域） | hlink（链域，指向弧头相同的下一条弧） | tlink（链域，指向弧尾相同的下一条弧） | info（指向弧的相关信息） |
顶点结点
| data（存放顶点相关的数据信息） | firstin（指向该顶点为弧头的第一个弧结点） | firstout（指向该顶点为弧尾的第一个弧结点） |
（2）特点：图的十字链表表示不唯一，但一个十字链表表示确定一个图。
（3）图的十字链表存储结构
typedef struct ArcNode {
int tailvex, headvex;
struct ArcNode *hlink, *tlink;
}AreNode;
typedef struct VNode {
char data;
ArcNode *firstin, *firstout;
}VNode;
typedef struct {
VNode xlink[maxvertexnum];
int vexnum, arcnum;
}GLGraph;
4）邻接多重表法：无向图的一种链式存储结构。
（1）邻接多重表的结点：存储边和顶点的结点。
存储边的结点
| mark（标志域，可用于标记边是否被搜索过） | ivex（该边依附的其中一个顶点的位置） | ilink（指向下一条依附于顶点ivex的边） | jvex（该边依附的其中另一个顶点的位置） | jlink（指向下一条依附于顶点jvex的边） | info（指向和边相关的各种信息的指针域） |
存储顶点的结点
| data（存储该顶点的相关信息） | firstedge（指示第一条依附于该顶点的边） |
（2）图的邻接多重表存储结构
typedef struct ArcNode {
bool mark;
int ivex, jvex;
struct ArcNode *ilink, *jlink;
}AreNode;
typedef struct VNode {
char data;
ArcNode *firstdege;
}VNode;
typedef struct {
VNode adjmulist[maxvertexnum];
int vexnum, arcnum;
}AMLGraph;
3、图的遍历
1）广度优先搜索：优先考虑最早被发现的顶点，类似于二叉树的层序遍历。
（1）BFS算法：需要借助队列。空间复杂度O(|V|)。采用邻接表存储方式时，时间复杂度O(|V|+|E|)；采用邻接矩阵存储方式时，时间复杂度O(|V|2)。
（2）广度优先生成树：广度遍历得到的遍历树。给定图的邻接矩阵存储表示是唯一的，其广度优先生成树也是唯一的，由于邻接表存储表示不唯一，广度优先生成树不唯一。
2）深度优先搜索：优先考虑最后被发现的顶点，类似于树的先序遍历。
（1）DFS算法：需要借助栈。空间复杂度O(|V|)。采用邻接表存储方式时，时间复杂度O(|V|+|E|)；采用邻接矩阵存储方式时，时间复杂度O(|V|2)。
（2）深度优先生成树：深度优先生成树不唯一。
4、图的应用
1）最小生成树(MST)：生成树中权值最小的生成树。
（1）一个连通图的生成树是图的极小连通子图。
（2）性质：最小生成树不唯一，即最小生成树的树形不唯一。
当图中各边权值互不相等时，最小生成树唯一。
最小生成树的边的权值之和是唯一的，而且是最小的。
最小生成树的边数为顶点数减1。
（3）Prim算法：从顶点开始扩展最小生成树。
时间复杂度为O(|V|2)。
适用于求解边稠密的图的最小生成树。
（4）Kruskal算法：按权值的递增次序选择合适的边来构造最小生成树的方法。
时间复杂度为O(|E|log|E|)。
适用于边稀疏而顶点较多的图。
2）最短路径：带权路径长度最短的路径。
（1）Dijkstra算法：求单源最短路径，即求图中某一顶点到其他各顶点的最短路径。
使用邻接矩阵表示时，时间复杂度为O(|V|2)；采用带权的邻接表表示时，时间复杂度为O(|V|2)。找出所有结点对之间的最短距离，时间复杂度为O(|V|3)
（2）Floyd算法：求每对顶点间的最短路径。
3）拓扑排序
（1）有向无环图(DAG)：一个有向图中不存在环。
（2）拓扑排序：由一个有向无环图的顶点组成的序列，且满足以下条件：
每个顶点出现且只出现一次。
若顶点A在序列中排在顶点B的前面，则图中不存在从顶点B到顶点A的路径。
（3）时间复杂度为O(|V|+|E|)。
4）关键路径
（1）AOE网：在带权有向无环图中，以顶点表示时间，以有向边表示活动，以边上的权值表示完成该活动的开销，则称这种有向图为用边表示活动的网络。
（2）开始顶点（源点）：在AOE网中仅有一个入度为0的顶点，表示工程的开始。
（3）结束顶点（汇点）：在AOE网中仅有一个出度为0的顶点，表示工程的结束。
（4）关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径。
关键路径上的活动称为关键活动。
（5）最短时间：整个工程的关键路径的长度。
