数据结构：图

图是一种复杂的数据结构，结点之间的关系可以是任意的，任意两个数据元素之间都有可能相关。

例如，RunicDolphin806在游玩《群星》游戏时

地图

这部分地图可以简化为一个图：

图

图的基本概念

概念	解释
顶点	图中的数据元素，记为 $V$
弧	若 $\left<v,w\right> \in VR$，则 $\left<v,w\right>$ 表示从 $v$ 到 $w$ 的一条弧，且称 $v$ 为弧尾（初始点），$w$ 为弧头（终端点）
边	若 $\left<v,w\right> \in VR$ 且 $\left<w,v\right> \in VR$，则可记这两条弧为一条边
无向图	若 $\left<v,w\right> \in VR$ 时必有 $\left<w,v\right> \in VR$，则此时称该图为无向图
完全图	对于 $n$ 个顶点的无向图，若有 $\displaystyle \frac{n(n-1)}{2}$ 条边，则称为完全图
有向完全图	对于 $n$ 个顶点的有向图，若有 $n(n-1)$ 条弧，则称为有向完全图
权	与图的边或弧相关的数
子图	对于两个图 $G=(V,\{E\})$ 和 $G'=(V',\{E'\})$，如果 $V' \subseteq V$ 且 $E' \subseteq E$，则称 $G'$ 是 $G$ 的子图

图的存储

邻接矩阵

设图 $G = (V,E)$ 是一个有 $n$ 个顶点的图，则其邻接矩阵是一个二维数组 G.edge[n][n]，定义

$$G.edge[i][j] = \left\{ \begin{matrix} 1， & \left< i,j \right> \in E \ 或\ (i,j) \in E \\\\ 0， & 其他 \end{matrix} \right.$$

由定义可知，无向图的邻接矩阵是对称的。

邻接表

邻接表是图的一种链式存储结构

设图中有 $n$ 个顶点，$e$ 条边，则

用邻接表表示无向图时，需要 $n$ 个顶点结点，$2e$ 个边结点；
用邻接表表示有向图时，若不考虑逆邻接表，只需 $n$ 个顶点结点，$e$ 个边结点

 1/* ----- 顶点 ----- */
 2typedef char VertexData;
 3typedef int EdgeData;
 4
 5struct node {
 6    int dest；          // 目标顶点位置
 7    EdgeData cost;      // 边的权值
 8    node *link;         // 下一条边的指针
 9};
10
11/* ----- 顶点的邻接链表 ----- */
12struct vnode {
13    VertexData data;    // 顶点数据域
14    node *adj;          // 边链表头指针
15};
16
17/* ----- 图 ----- */
18struct adjgraph {
19    vnode VetList[MaxVexNum];   // 邻接表
20    int n,e;                    // 图中当前的顶点个数与边数
21};

邻接表的示意图如下：

图的遍历

深度优先搜索（DFS）

基本步骤：

访问图的某一个起始顶点 $v$ 后，由 $v$ 出发，访问它的任意一个未访问的邻接结点 $w_1$；
再从 $w_1$ 出发，访问与 $w_1$ 邻接但还没有访问过的顶点 $w_2$；
再从 $w_2$ 出发，重复过程2；
直到到达所有邻接结点都被访问过的某个顶点 $u$；
退回到访问顶点 $u$ 之前访问的顶点，若还有未访问的邻接结点，则再从此结点出发重复过程2；如果没有，则继续回退；
重复上述过程，直到所有的顶点都被访问一次为止。

特点：

采用递归或栈的形式进行；
对每个顶点至多调用一次 DFS 函数；
时间复杂度取决于所采用的存储结构：邻接矩阵 $O(n^2)$，邻接表 $O(n+e)$

递归形式：

 1/* ----- 深度优先搜索（递归形式）----- */
 2void Graph_Traverse(adjGraph &G) {
 3    int visit[16] = {0};
 4    
 5    for (int i = 1; i<=15; i++) {
 6        if (!visit[i]); {
 7            DFS(G, i, visit[]);
 8        }
 9    }
10}
11
12void DFS_recursion(adjGraph &G, int v, int visit[]) {
13    printf("%c", G.Vexlist[v].data);
14    visit[v] = 1;
15    enode *w = G.Vexlist[v].adj;
16
17    while (w != NULL) {
18        if (!visit[w->dest]) {
19            DFS_recursion(G, w, visit[]);
20        }
21        w = w->link;
22    }
23}

栈形式：

 1/* ----- 深度优先搜索（栈形式） ----- */
 2void DFS_stack(adjGraph &G) {
 3    int visit[16] = {0};
 4    
 5    // 每个连通分支调用一次DFS
 6    for (int i = 1; i <= 15; i++) {
 7        if (!visit[i]) {   
 8            stack<int> s;
 9            s.push(i);
10            
11            while (!s.empty()) {
12                int top = s.top();
13                s.pop();
14                
15                if (!visit[top]) {
16                    printf("%c", G.Vexlist[top].data);
17                    visit[top] = 1;
18                }
19                
20                // 将所有未访问的邻接节点入栈
21                enode *w = G.Vexlist[top].adj;
22                while (w != NULL) {
23                    if (!visit[w->dest]) {
24                        s.push(w->dest);
25                    }
26                    w = w->link;
27                }
28            }
29        }
30    }
31}

广度优先搜索（BFS）

基本步骤：

访问起始顶点 $v$；
由 $v$ 出发，依次访问 $v$ 的各个未被访问过的邻接顶点 $w_1$，$w_2$，$\cdots$， $w_t$；
再顺序访问 $w_1$，$w_2$，$\cdots$， $w_t$ 的所有还未被访问过的邻接顶点；
再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，以此类推，直到图中所有顶点都被访问到为止。

特点：

BFS 遍历图的时间复杂度和 DFS 遍历的时间复杂度相同；
耗费的时间均取决于所采用的存储结构：邻接矩阵 $O(n^2)$，邻接表 $O(n+e)$；
BFS 和 DFS 仅是对顶点的访问顺序不同。

队列形式：

 1// 广度优先搜索
 2void BFS(adjGraph &G) {
 3    int visit[16] = {0};
 4    for (int i = 1; i<=15; i++) {
 5        if (!visit[i]) {
 6            printf("%c", G.Vexlist[i].data);
 7            visit[i] = 1;
 8
 9            queue<int> q;
10            
11            q.push(i);
12
13            while (!q.empty()) {
14                int head = q.front();
15                q.pop();
16
17                enode *w = G.Vexlist[head].adj;
18                while (w != NULL) {
19                    if (!visit[w->dest]) {
20                        printf("%c", G.Vexlist[w->dest].data);
21                        visit[w->dest] = 1;
22                        q.push(w->dest);
23                    }
24                    w = w->link;
25                }
26            }
27        }
28    }
29}

最小生成树

对于一个有 $n$ 个顶点的图，必须且仅用该网络中的 $n-1$ 条边来联结网络中的 $n$ 个顶点；不能产生回路；各边权值总和最小的树。

Prim 算法是求最小生成树的一种有效方法：

已知，图 $N =(V,E)$，生成树顶点集合 $U$；
从某一顶点 $u_0$ 出发，选择与它关联的具有最小权值的边 $(u_0,v)$，将顶点 $v$ 加入到生成树顶点集合 $U$ 中；
每次从一个顶点在 $U$ 中，而另一个顶点不在 $U$（即 $V-U$）中的各条边中选择权值最小的边 $(u,u')$，把它的顶点 $v$ 加入到集合 $U$ 中；
直至网络中的所有顶点都加入到生成树顶点集合 $U$ 中为止。

辅助数组	作用
`lowcost[]`	存放生成树顶点集合 $U$ 内顶点到生成树外 $V-U$ 各顶点的各边上的当前最小权值
`adjvex[]`	记录生成树顶点集合外各顶点 $u'$ 距离集合内哪个顶点 $u$ 最近，否则记录为 `-1`

 1/* ----- Prim 算法求最小生成树 ----- */
 2void Prim(Graph &G, int u) {    // u 表示初始时的顶点
 3    int lowcost[G.n] = {0};
 4    int adjvex[G.n] = {0};
 5
 6    for (int i = 0; i < G.n; i++) {
 7        lowcost[i] = G.edge[u][i];
 8        adjvex[i] = u;
 9    }
10    adjvex[u] = -1;
11
12    // 查找最小的lowcost
13    for (int i = 0; i < G.n && i != u; i++) {
14        EdgeData min = MaxValue;
15        int v = 0;
16        // 查找生成树外顶点到生成树内顶点具有最小权值的边，v是当前具有最小权值的边
17        for (int j = 0; j < G.n; j++) {
18            if (adjvex[j] != -1 && lowcost[j] < min) {
19                v = j;
20                min = lowcost[w];
21            }
22        }
23        // v != 0 表示找到所求的边，并加入生成树
24        if (v != 0) {
25            printf("%d, %d, %d", adjvex[v], v, lowcost[v]);
26            adjvex[v] = -1;
27            // 更新 adjvex 和 lowcost 数组
28            for (int j = 0; j < G.n; j++) {
29                if (adjvex[j] != -1 && G.edge[v][j] < lowcost[j]) {
30                    lowcost[j] = G.edge[v][j];
31                    adjvex[j] = v;
32                }
33            }
34        }
35    }
36}

活动网络

AOV网络

用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边 $\left< v_i, v_j \right>$ 表示活动 $v_i$ 必须先于活动 $v_j$ 进行。这种有向图叫做顶点表示活动的 AOV 网络。

将各个顶点（代表各个活动）排列成一个线性有序的序列，使得 AOV 网络中所有应存在的前驱和后继关系都能得到满足。这种构造 AOV 网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。

例如，下图的一个拓扑有序序列为：$C_1, C_2, C_3, C_4, C_5, C_6, C_8, C_9, C_7$

在邻接表中增设一个数组count[]，记录各顶点入度。入度为零的顶点即无前驱顶点。在输入数据前，顶点表VexList[] 和入度数组count[]全部初始化。在输入数据时，每输入一条边<j, k>，就需要建立一个边结点，并将它链入相应边链表中，统计入度信息：

1EdgeNode *p = new EdgeNode;
2p->dest = k;                // 建立边结点
3p->link = G.VexList[j].adj; // 链入顶点 j 的边链表的前端
4VexList[j].adj = p;
5count[k]++;                 // 顶点 k 入度加一

拓扑排序算法实现：

输入 AOV 网络，令 $n$ 为顶点个数。
在 AOV 网络中选一个没有直接前驱的顶点，并输出之；
从图中删去该顶点，同时删去所有它发出的有向边；
重复以上 1,2步，直到全部顶点均已输出，拓扑排序完成，说明无有向环；或还有未输出的顶点，但已跳出处理循环，说明图中剩下的顶点都有直接前驱。这时网络中必存在有向环。

拓扑排序的过程

 1void TopologicalSort(adjGraph &G) {
 2    stack S; int j = 0;
 3    // 入度为零的顶点栈初始化
 4    if (!s.empty()) {
 5        s.pop();
 6    }
 7    
 8    for (int i = 0; i < G.n; i++)	{
 9        // 将入度为0的顶点进栈
10        if (count[i] == 0) {
11            s.push(i);
12        }
13    }	 
14    // 期望输出n个顶点
15    for (int i = 0; i < G.n; i++) {
16        if (s.empty())	{
17            return;         // 中途栈空，退出
18        }                   // 网络中有回路，退出
19        else {              // 继续拓扑排序
20            j = s.top();
21            printf("%d \n", j);
22
23            // 扫描出边表，更新与j相连的顶点入度
24            EdgeNode * p = G.VexList[j].adj;
25            while (p != NULL) {	
26                // 获得另一顶点		
27                int k = p->dest;			
28                if(count[k] == 0) {
29                    s.push(k);      // 将入度为零的顶点进栈
30                    count[k]-- ;    // 顶点入度减一
31                } 	
32                p = p->link;
33            }
34        }
35    }
36}

AOE网络

如果在有向无环的带权图中，用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称 AOE 网络。

完成工程的最短时间是从开始点到完成点的最长路径的长度。

概念	内容
关键路径	路径长度最长的路径
`e[i]`	活动 $a_i$ 的最早开始时间
`l[i]`	活动 $a_i$ 的最迟开始时间
`l[i]-e[i]`	完成活动 $a_i$ 的时间余量
关键活动	满足 `l[i] == e[i]` 的活动 $a_i$

求关键路径的算法：

输入 $e$ 条弧 <j,k>，建立 AOE 网的存储结构；
从源点 $v_0$ 出发，令 ve[0] = 0，按拓扑排序求出其余各顶点的最早发生时间 ve[i] $(1 \leqslant i \leqslant n-1)$。如果得到的拓扑有序序列中顶点个数小于网中的顶点数 $n$，则说明网中存在环，不能求关键路径；
从汇点 $v_n$ 出发，令vl[n-1] = ve[n-1]，按逆拓扑有序求出其余各顶点的最迟发生时间 vl[i] $(2 \leqslant i \leqslant n-2)$；
根据各顶点的ve和vl值，求每条弧 $s$ 最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。

最短路径

从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，找到一条路径使得沿此路径上各边上的权值总和达到最小的过程。

算法	适用问题
Dijkstra算法	边上权值非负情形的单源最短路径问题
Bellman和Ford算法	边上权值为任意值的单源最短路径问题
Floyd算法	所有顶点之间的最短路径

单源最短路径问题

给定一个带权有向图 $G$ 与源点 $v$，求从 $v$ 到 $G$ 中其它顶点的最短路径（限定各边上的权值大于或等于 0）。

Dijkstra 算法

首先求出长度最短的一条最短路径；
再参照它求出长度次短的一条最短路径；依次类推……
直到从顶点 $v$ 到其它各顶点的最短路径全部求出为止。

引入辅助数组dist[]。它的每一个分量dist[i]表示当前找到的从源点v0到终点vi的最短路径的长度。

步骤	操作
初始状态	若从源点`v0`到顶点`vi`有边，则`dist[i]`为该边上的权值；若从源点`v0`到顶点`vi`无边，则`dist[i]`为 $\infty$。
求`dist[]`数组	长度为 $\mathrm{dist[j]} = \underset{i}{\mathrm{min}}\{⁡\mathrm{dist}[i] \ \|\ v_i \in V\}$ 的路径是从源点`v0`出发的长度最短的最短路径，其值为`(v0, vj)`的最短路径的长度。
求解次短路径	假设次短路径终点为`vk`，则这条最短路径或为`(v0, vk)`，或为`(v0, vj, vk)`；次短路径长度为`edge[0][k]`或`dist[j] + edge[j][k]`
更新`dist[]`数组	每次求得一条最短路径后，其终点`vk`加入集合`S`，然后对所有的 $v_i \in V-S$，修改其`dist[i]`值。

假设 $S$ 是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0出发，中间只经过 $S$ 中的顶点便可到达的那些顶点vx $(v_x \in V-S)$ 的路径。

Dijkstra算法的求解过程

 1/* ----- Dijkstra算法 ----- */
 2void ShortestPath(MTGraph G, int v) {
 3    EdgeData dist[G.n];         // 最短路径长度数组
 4    int path[G.n];              // 最短路径数组
 5    int S[G.n];                 // 最短路径顶点集
 6    for (int i = 0; i < n; i++) {
 7        dist[i] = G.edge[v][i];         // dist数组初始化
 8        S[i] = 0;                       // 集合S初始化
 9        if (dist[i] < MaxValue) {
10            path[i] = v;
11        }
12        else path[i] = -1;              // path数组初始化
13    }
14    // 顶点v加入顶点集合
15    S[v] = 1;       
16
17    // 从顶点 v 确定 n-1 条路径
18    for (int i = 0; i < G.n-1; i++) {
19        float min = MaxValue;
20        int u = v;
21        // 选当前不在集合 S 中具有最短路径的顶点 u
22        for (int j = 0; j < G.n; j++) {
23            if (!S[j] && dist[j] < min) {
24                u = j;		
25                min = dist[j];
26            }
27        }
28        // 将顶点 u 加入集合 S
29        S[u] = 1;						
30        // 修改可经过顶点 u 变短的路径值
31        for (int w = 0; w < G.n; w++) {
32            if (!S[w] && G.edge[u][w] < MaxValue && dist[u]+G.edge[u][w] < dist[w]) {
33                // 顶点 w 未加入 S，且经过 u 可以缩短路径值
34                dist[w] = dist[u] + G.edge[u][w]; 
35                // 修改到 w 的最短路径
36                path[w] = u;
37            }
38        }	// 选定各顶点到顶点 v 的最短路径
39    }
40
41    for (int i = 0; i < G.n; i++) {	// 打印各顶点的最短路径: 路径为逆向输出
42        printf("\n");
43        printf("Distance: %d; Path: %d", dist[i], i);
44        // 输出终点的最短路径长度和终点
45        int pre = path[i];      // 取终点的直接前驱
46        while(pre != v) {     // 沿路径上溯输出
47            printf ("<-- %d ", pre);
48            if (pre == -1) {
49                break;		// 无法从 v 到达该结点
50            }
51            pre = path[pre];
52        }
53    }
54}