GENIA

数据结构-图-模板代码

2023-12-31

数据结构实验考试的时候会直接提供邻接表或者邻接矩阵作为输入，所以无需考虑图存储方面的代码量。图论的主要考点无非就是 图的遍历、最小生成树、最短路径问题

图的遍历（BFS/DFS）

这两种遍历方式几乎适用于所有图。在代码实现过程中，BFS要用到栈，DFS则要用到堆。当然，BFS 完全可以通过递归调用实现，和用栈实现本质上是一样的。

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;

void BFS(const vector<vector<int>>& graph, const map<char, int>& vertexMap, const map<int, char>& inverseVertexMap, char start) {
    int n = graph.size();
    // 创建一个队列存储待访问的元素
    std::queue<int> wait;
    // 创建一个数组用于标记节点是否被访问过
    vector<bool> visited(n, false);

    // 将起始节点入队并标记为已访问
    wait.push(vertexMap.at(start));
    visited[vertexMap.at(start)] = true;

    cout << "BFS遍历结果：" << endl;
    // 开始遍历
    while (!wait.empty()) {
        // 出队一个节点并访问该节点
        int current = wait.front();
        cout << inverseVertexMap.at(current) << endl;
        wait.pop();

        // 遍历当前节点的所有邻居
        for (int i = 0; i < n; i++) {
            // 若邻居未被访问过，则将邻居入队并将其标记为已访问
            if (visited[i] == false && graph[current][i] != 0 && graph[current][i] != 32767) {
                wait.push(i);
                visited[i] = true;
            }
        }
    }
}

void DFS(const vector<vector<int>>& graph, const map<char, int>& vertexMap, const map<int, char>& inverseVertexMap, char start) {
    int n = graph.size();
    // 创建一个栈存储待访问的元素
    stack<int> wait;
    // 创建一个数组用于标记节点是否被访问过
    vector<bool> visited(n, false);

    // 将起始节点入栈并标记为已访问
    wait.push(vertexMap.at(start));
    visited[vertexMap.at(start)] = true;

    cout << "DFS遍历结果：" << endl;
    // 开始遍历
    while (!wait.empty()) {
        // 弹出栈顶节点并访问该节点
        int current = wait.top();
        cout << inverseVertexMap.at(current) << endl;
        wait.pop();

        // 遍历当前节点的所有邻居
        for (int i = 0; i < n; i++) {
            // 若邻居未被访问过，则将邻居入栈并将其标记为已访问
            if (visited[i] == false && graph[current][i] != 0 && graph[current][i] != 32767) {
                wait.push(i);
                visited[i] = true;
            }
        }
    }
}

int main() {
    int n, m;
    cout << "输入顶点数与边数:\n";
    cin >> n >> m;

    // 定义邻接矩阵数组
    vector<vector<int>> graph(n, vector<int>(n));

    // 使用一个映射来将字母映射到对应的索引
    map<char, int> vertexMap;
    map<int, char> inverseVertexMap;

    cout << "依次输入顶点字母:\n";
    for (int i = 0; i < n; ++i) {
        char vertex;
        cin >> vertex;
        vertexMap[vertex] = i;
        inverseVertexMap[i] = vertex;
    }

    cout << "输入邻接矩阵:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
        }
    }

    // 输入遍历的起始点
    char start;
    cout << "输入 BFS 和 DFS 的起点：\n";
    cin >> start;
    BFS(graph, vertexMap, inverseVertexMap, start);
    DFS(graph, vertexMap, inverseVertexMap, start);

    return 0;
}

最小生成树

prim 的重心在节点的选取，Kruskal 的重心在边的选取。二者的核心都是贪婪算法。

Prim算法

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int INF = INT_MAX;

// 找到未包含在最小生成树中的顶点中，具有最小权值的顶点
int findMinKey(const vector<int>& key, const vector<bool>& mstSet, int n) {
    int minKey = INF, minIndex;

    for (int v = 0; v < n; ++v) {
        if (!mstSet[v] && key[v] < minKey) {
            minKey = key[v];
            minIndex = v;
        }
    }

    return minIndex;
}

// 使用Prim算法找到最小生成树
void primMST(const vector<vector<int>>& graph, int n) {
    vector<int> parent(n, -1);
    vector<int> key(n, INF);
    vector<bool> mstSet(n, false);

    key[0] = 0;

    for (int count = 0; count < n - 1; ++count) {
        int u = findMinKey(key, mstSet, n);
        mstSet[u] = true;

        for (int v = 0; v < n; ++v) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    // 输出最小生成树的边
    cout << "最小生成树的边:\n";
    for (int i = 1; i < n; ++i) {
        cout << "边: " << parent[i] << " - " << i << " 权值: " << graph[i][parent[i]] << "\n";
    }
}

int main() {
    int n, m;
    cout << "输入顶点数与边数:\n";
    cin >> n >> m;

    // 读取邻接矩阵
    vector<vector<int>> graph(n, vector<int>(n));

    cout << "输入邻接矩阵:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
        }
    }

    // 运行Prim算法
    primMST(graph, n);

    return 0;
}

Kruskal算法

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 边的结构体
struct Edge {
    int start, end, weight;
};

int findfather(int a,const vector<int>& father)
{
    while (a != father[a])
    {
        a = father[a];
    }
    return a;
}

// 克鲁斯卡尔算法
void kruskal(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<Edge> edges;

    // 遍历邻接矩阵，将所有非零权重的边加入边集合
    // 克鲁斯卡尔算法通常用于求解带权无向图问题，所以这里只考虑一半矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (graph[i][j] != 0 && graph[i][j] != 32767) {
                edges.push_back({i, j, graph[i][j]});
            }
        }
    }

    // 按权重排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    // 最小生成树的边集合
    vector<Edge> mst;
    vector<int> father(n); //记录每个节点的父亲
    // 初始化父节点数组
    for (int i = 0; i < n; ++i)
    {
        father[i] = i;
    }

    for (int i = 0; i < edges.size() && mst.size() < n-1; ++i)
    {
        int s = edges[i].start;
        int e = edges[i].end;
        if (findfather(s,father) != findfather(e,father)) //判断父节点是否相同
        {
            mst.push_back({edges[i].start,edges[i].end,edges[i].weight});
            father[findfather(s,father)] = father[findfather(e,father)]; //将两点并入一个集合中
        }
    }

    if (mst.size() != n - 1)
    {
        cout <<  mst.size()  << "该图不连通" << endl;
        return;
    }
    else
    {
        cout << "最小生成树的各边如下：" << endl;
        for (int i = 0; i < mst.size(); ++i)
        {
            cout << mst[i].start << "-" << mst[i].end << " : " << mst[i].weight << endl;
        }
    }
}



int main() {
    int n, m;
    cout << "输入顶点数与边数:\n";
    cin >> n >> m;

    // 读取邻接矩阵
    vector<vector<int>> graph(n, vector<int>(n));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
        }
    }

    // 应用克鲁斯卡尔算法得到最小生成树
    kruskal(graph);

    return 0;
}

最短路径

迪杰斯特拉适用于求指定点到点的最短路径。

弗洛伊德算法可以一次性求出任意两点之间的最短路径。

Djikstra算法

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <vector>
#include <climits>
#include <stack>

using namespace std;

// Dijkstra算法，计算从start到所有顶点的最短路径
vector<int> dijkstra(vector<vector<int>>& graph, int start,vector<int>& parents) {
    int n = graph.size();
    // 用 visit 数组记录一个顶点是否被访问
    vector<bool> visited(n, false);
    // 记录起始点到各点的最短距离
    vector<int> distance(n, INT_MAX);
    distance[start] = 0;

    // 遍历所有顶点
    for (int count = 0; count < n; ++count) {
        int min_dist = INT_MAX; // 用于维护当前距离最小的顶点
        int min_vertex = -1;   // 用于存储当前距离最小的顶点的索引

        // 找出未访问过的距离最小的顶点
        for (int v = 0; v < n; ++v) {
            if (!visited[v] && distance[v] < min_dist) {
                min_dist = distance[v];
                min_vertex = v;
            }
        }

        // 若无法找到更小距离的顶点，则退出循环
        if (min_vertex == -1) {
            break;
        }

        // 标记该顶点为已访问
        visited[min_vertex] = true;

        // 更新与该顶点相邻的顶点的距离
        for (int neighbor = 0; neighbor < n; ++neighbor) {
            if(distance[min_vertex] + graph[min_vertex][neighbor] < distance[neighbor]){
                distance[neighbor] = distance[min_vertex] + graph[min_vertex][neighbor];
                // 如果最短路径值进行了更新，则更新父节点信息
                parents[neighbor] = min_vertex;
            }
        }
    }
    return distance;
}

// 输出从起点到终点的最短路径
void printShortestPath(vector<int>& parents, int start, int end) {
    // 因为最短路径是通过父节点列表逆推出来的，所以这里利用栈先进后出的特性
    stack<int> path;
    int current = end;

    while (current != start) {
        path.push(current);
        current = parents[current];
    }

    path.push(start);

    cout << "从顶点 " << start << " 到顶点 " << end << " 的最短路径为: ";

    while (!path.empty()) {
        cout << path.top() << " ";
        path.pop();
    }

    cout << endl;
}

int main() {
    int n, m;
    cout << "输入顶点数与边数:\n";
    cin >> n >> m;
    // 读取邻接矩阵
    vector<vector<int>> graph(n, vector<int>(n));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
        }
    }

    // 选择起始点
    int start;
    cout << "输入选择的起始点:";
    cin >> start;

    // 初始化父节点数组
    vector<int> parents(n, -1);

    // 调用Dijkstra算法
    vector<int> shortest_distances = dijkstra(graph, start,parents);

    // 输出最短路径结果
    cout << "从起始点 " << start << " 到达其余各顶点的最短路径:\n";
    for (int i = 0; i < n; ++i) {
        if (i != start) {
            if (shortest_distances[i] == INT_MAX) {
                cout << "顶点 " << i << ": 无路径\n";
            } else {
                cout << "顶点 " << i << ": " << shortest_distances[i] << "\n";
            }
            // 输出最短路径
            printShortestPath(parents, start, i);
        }
    }
    return 0;
}


/* (32767表示正无穷)
样例输出：
输入顶点数与边数:
7 12
0 4 6 6 32767 32767 32767
32767 0 1 32767 7 32767 32767
32767 32767 0 32767 6 4 32767
32767 32767 2 0 32767 5 32767
32767 32767 32767 32767 0 32767 6
32767 32767 32767 32767 1 0 8
32767 32767 32767 32767 32767 32767 0
输入选择的起始点:0
从起始点 0 到达其余各顶点的最短路径:
顶点 1: 4
从顶点 0 到顶点 1 的最短路径为: 0 1
顶点 2: 5
从顶点 0 到顶点 2 的最短路径为: 0 1 2
顶点 3: 6
从顶点 0 到顶点 3 的最短路径为: 0 3
顶点 4: 10
从顶点 0 到顶点 4 的最短路径为: 0 1 2 5 4
顶点 5: 9
从顶点 0 到顶点 5 的最短路径为: 0 1 2 5
顶点 6: 16
从顶点 0 到顶点 6 的最短路径为: 0 1 2 5 4 6
*/

Floyd算法

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
#include <stack>
#include <climits>

using namespace std;

struct PathInfo {
    int distance;
    int intermediate;  // 用于存储中转节点
};

vector<vector<PathInfo>> Floyd(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<PathInfo>> pathInfo(n, vector<PathInfo>(n));
    vector<vector<int>> dist(graph);  // 使用邻接矩阵进行初始化

    // 初始化路径矩阵
    for (int i = 0; i < n; i++) { // 行索引
        for (int j = 0; j < n; j++) {  // 列索引
            if (i != j && dist[i][j] != 32767 ) {
                pathInfo[i][j].distance = dist[i][j];
                pathInfo[i][j].intermediate = i;  // 如果初始存在路径，则选取初始节点为中间节点
            } else if(i == j) {
                pathInfo[i][j].distance = 0;
                pathInfo[i][j].intermediate = -1;  // 没有路径则用 -1 表示
            }
            else{
                pathInfo[i][j].distance = INT_MAX;
                pathInfo[i][j].intermediate = -1;
            }
        }
    }

    // 更新路径矩阵
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                // A0 - Ak  i 为行索引   j 为列索引
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pathInfo[i][j].distance = dist[i][j];
                    pathInfo[i][j].intermediate = k;
                }
            }
        }
    }

    return pathInfo;
}

// 输出最短路径及其长度
void printShortestPath(int start, int end, const vector<vector<PathInfo>>& pathInfo) {
    if (pathInfo[start][end].distance == INT_MAX) {
        cout << "没有路径\n" << endl;
        return;
    }

    stack<int> path;
    int intermediate = pathInfo[start][end].intermediate;

    // 查找中间路径并依次入栈
    while (intermediate != start) {
        path.push(intermediate);
        intermediate = pathInfo[start][intermediate].intermediate;
    }

    // 利用栈的特性将路径输出
    cout << "路径为: " << start;
    while (!path.empty()) {
        cout << " -> " << path.top();
        path.pop();
    }
    cout << " -> " << end << endl;
}

int main() {
    int n, m;
    cout << "输入顶点数与边数:\n";
    cin >> n >> m;

    // 定义邻接矩阵数组
    vector<vector<int>> graph(n, vector<int>(n));

    cout << "输入邻接矩阵:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
        }
    }

    // 定义路径矩阵
    vector<vector<PathInfo>> pathInfo = Floyd(graph);

    // 输出最短路径矩阵
    cout << "最短路径矩阵为:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
                cout << pathInfo[i][j].distance << "\t";
            }
        cout << endl;
    }

    // 输出中间节点矩阵
    cout << "中间节点矩阵为:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << pathInfo[i][j].intermediate << "\t";
        }
        cout << endl;
    }

    // 指定起始顶点和终点
    int start, end;
    cout << "输入起始点和终点:\n";
    cin >> start >> end;

    // 输出最短路径
    printShortestPath(start, end, pathInfo);

    return 0;
}

/*
输入顶点数与边数:
6 16
输入邻接矩阵:
0 7 11 32767 32767 32767
7 0 10 9 32767 32767
11 10 0 5 7 8
32767 9 5 0 32767 32767
32767 32767 7 32767 0 6
32767 32767 8 32767 6 0
最短路径矩阵为:
0       7       11      16      18      19
7       0       10      9       17      18
11      10      0       5       7       8
16      9       5       0       12      13
18      17      7       12      0       6
19      18      8       13      6       0
中间节点矩阵为:
-1      0       0       1       2       2
1       -1      1       1       2       2
2       2       -1      2       2       2
1       3       3       -1      2       2
2       2       4       2       -1      4
2       2       5       2       5       -1
输入起始点和终点:
3 5
路径为: 3 -> 2 -> 5
 */
Tags: 数据结构 算法
← 固件基础 Cryptohack wp(1) - Modular Arithmetic →