数据结构：图

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

例如，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.$$

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

邻接矩阵方便看出任意两个顶点之间的关系，但是空间复杂度较高 $O(n^2)$，且当图的连接较为稀疏时空间浪费较多。

邻接表

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


/* ----- 顶点 ----- */
typedef char VertexData;
typedef int EdgeData;

struct node {
    int dest；          // 目标顶点位置
    EdgeData cost;      // 边的权值
    node *link;         // 下一条边的指针
};

/* ----- 顶点的邻接链表 ----- */
struct vnode {
    VertexData data;    // 顶点数据域
    node *adj;          // 边链表头指针
};

/* ----- 图 ----- */
struct adjgraph {
    vnode VetList[MaxVexNum];   // 邻接表
    int n,e;                    // 图中当前的顶点个数与边数
};

邻接表的示意图如下：

图的遍历

深度优先搜索（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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


/* ----- 深度优先搜索（递归形式）----- */
void Graph_Traverse(adjGraph &G) {
    int visit[16] = {0};
    
    for (int i = 1; i<=15; i++) {
        if (!visit[i]); {
            DFS(G, i, visit[]);
        }
    }
}

void DFS_recursion(adjGraph &G, int v, int visit[]) {
    printf("%c", G.Vexlist[v].data);
    visit[v] = 1;
    enode *w = G.Vexlist[v].adj;

    while (w != NULL) {
        if (!visit[w->dest]) {
            DFS_recursion(G, w, visit[]);
        }
        w = w->link;
    }
}

栈形式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


/* ----- 深度优先搜索（栈形式） ----- */
void DFS_stack(adjGraph &G) {
    int visit[16] = {0};
    
    // 每个连通分支调用一次DFS
    for (int i = 1; i <= 15; i++) {
        if (!visit[i]) {   
            stack<int> s;
            s.push(i);
            
            while (!s.empty()) {
                int top = s.top();
                s.pop();
                
                if (!visit[top]) {
                    printf("%c", G.Vexlist[top].data);
                    visit[top] = 1;
                }
                
                // 将所有未访问的邻接节点入栈
                enode *w = G.Vexlist[top].adj;
                while (w != NULL) {
                    if (!visit[w->dest]) {
                        s.push(w->dest);
                    }
                    w = w->link;
                }
            }
        }
    }
}

广度优先搜索（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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


// 广度优先搜索
void BFS(adjGraph &G) {
    int visit[16] = {0};
    for (int i = 1; i<=15; i++) {
        if (!visit[i]) {
            printf("%c", G.Vexlist[i].data);
            visit[i] = 1;

            queue<int> q;
            
            q.push(i);

            while (!q.empty()) {
                int head = q.front();
                q.pop();

                enode *w = G.Vexlist[head].adj;
                while (w != NULL) {
                    if (!visit[w->dest]) {
                        printf("%c", G.Vexlist[w->dest].data);
                        visit[w->dest] = 1;
                        q.push(w->dest);
                    }
                    w = w->link;
                }
            }
        }
    }
}

最小生成树

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

Prim算法

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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


/* ----- Prim 算法求最小生成树 ----- */
void Prim(Graph &G, int u) {    // u 表示初始时的顶点
    int lowcost[G.n] = {0};
    int adjvex[G.n] = {0};

    for (int i = 0; i < G.n; i++) {
        lowcost[i] = G.edge[u][i];
        adjvex[i] = u;
    }
    adjvex[u] = -1;

    // 查找最小的lowcost
    for (int i = 0; i < G.n && i != u; i++) {
        EdgeData min = MaxValue;
        int v = 0;
        // 查找生成树外顶点到生成树内顶点具有最小权值的边，v是当前具有最小权值的边
        for (int j = 0; j < G.n; j++) {
            if (adjvex[j] != -1 && lowcost[j] < min) {
                v = j;
                min = lowcost[w];
            }
        }
        // v != 0 表示找到所求的边，并加入生成树
        if (v != 0) {
            printf("%d, %d, %d", adjvex[v], v, lowcost[v]);
            adjvex[v] = -1;
            // 更新 adjvex 和 lowcost 数组
            for (int j = 0; j < G.n; j++) {
                if (adjvex[j] != -1 && G.edge[v][j] < lowcost[j]) {
                    lowcost[j] = G.edge[v][j];
                    adjvex[j] = v;
                }
            }
        }
    }
}

Prim算法

Kruskal算法

基本思想：基于贪心策略，通过逐步选择权重最小的边并避免环路，最终构造最小生成树。

算法步骤：

排序边：将所有边按权重从小到大排序。
初始化并查集：每个顶点初始为一个独立集合。
逐条选边：按排序顺序选取边，若该边连接的两个顶点属于不同集合（即不形成环），则将其加入生成树，并合并两个集合。
终止条件：当选中 $V−1$ 条边（$V$ 为顶点数）时停止，此时所有顶点连通且无环。

具体实现中运用的关键数据结构就是并查集（Union-Find）。它的功能：高效判断边的两个顶点是否属于同一连通分量（即是否形成环）。

Kruskal算法

活动网络

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>，就需要建立一个边结点，并将它链入相应边链表中，统计入度信息：

1
2
3
4
5


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

拓扑排序算法实现：

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

拓扑排序的过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


void TopologicalSort(adjGraph &G) {
    stack S; int j = 0;
    // 入度为零的顶点栈初始化
    if (!s.empty()) {
        s.pop();
    }
    
    for (int i = 0; i < G.n; i++)	{
        // 将入度为0的顶点进栈
        if (count[i] == 0) {
            s.push(i);
        }
    }	 
    // 期望输出n个顶点
    for (int i = 0; i < G.n; i++) {
        if (s.empty())	{
            return;         // 中途栈空，退出
        }                   // 网络中有回路，退出
        else {              // 继续拓扑排序
            j = s.top();
            printf("%d \n", j);

            // 扫描出边表，更新与j相连的顶点入度
            EdgeNode * p = G.VexList[j].adj;
            while (p != NULL) {	
                // 获得另一顶点		
                int k = p->dest;			
                if(count[k] == 0) {
                    s.push(k);      // 将入度为零的顶点进栈
                    count[k]-- ;    // 顶点入度减一
                } 	
                p = p->link;
            }
        }
    }
}

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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


/* ----- Dijkstra算法 ----- */
void ShortestPath(MTGraph G, int v) {
    EdgeData dist[G.n];         // 最短路径长度数组
    int path[G.n];              // 最短路径数组
    int S[G.n];                 // 最短路径顶点集
    for (int i = 0; i < n; i++) {
        dist[i] = G.edge[v][i];         // dist数组初始化
        S[i] = 0;                       // 集合S初始化
        if (dist[i] < MaxValue) {
            path[i] = v;
        }
        else path[i] = -1;              // path数组初始化
    }
    // 顶点v加入顶点集合
    S[v] = 1;       

    // 从顶点 v 确定 n-1 条路径
    for (int i = 0; i < G.n-1; i++) {
        float min = MaxValue;
        int u = v;
        // 选当前不在集合 S 中具有最短路径的顶点 u
        for (int j = 0; j < G.n; j++) {
            if (!S[j] && dist[j] < min) {
                u = j;		
                min = dist[j];
            }
        }
        // 将顶点 u 加入集合 S
        S[u] = 1;						
        // 修改可经过顶点 u 变短的路径值
        for (int w = 0; w < G.n; w++) {
            if (!S[w] && G.edge[u][w] < MaxValue && dist[u]+G.edge[u][w] < dist[w]) {
                // 顶点 w 未加入 S，且经过 u 可以缩短路径值
                dist[w] = dist[u] + G.edge[u][w]; 
                // 修改到 w 的最短路径
                path[w] = u;
            }
        }	// 选定各顶点到顶点 v 的最短路径
    }

    for (int i = 0; i < G.n; i++) {	// 打印各顶点的最短路径: 路径为逆向输出
        printf("\n");
        printf("Distance: %d; Path: %d", dist[i], i);
        // 输出终点的最短路径长度和终点
        int pre = path[i];      // 取终点的直接前驱
        while(pre != v) {     // 沿路径上溯输出
            printf ("<-- %d ", pre);
            if (pre == -1) {
                break;		// 无法从 v 到达该结点
            }
            pre = path[pre];
        }
    }
}