图的遍历与Dijkstra最短路算法实现

0 概述

本实验使用C++语言实现了图的遍历与Dijkstra最短路算法，使用邻接表存储图。

1 实验设计

1.1 算法实现原理

定义n为顶点数，m为边数。

定义二维可变数组graph[u][v]，其中u、v为顶点，代表 u -> v 有一条边，边权为w。

1	vector<vector<int>> graph;

1.2 算法设计与分析

定义数组vis[u]，其中u为顶点，代表u是否被访问过。

1	vector<bool> vis;

DFS深度优先搜索

从起点顶点u开始，递归遍历这个点的所有邻接点。

当遍历到这个点的时候，标记该点为已访问，直到所有点都被访问后，遍历结束。

void dfs(int u) {
    if (vis[u]) return;
    printf("%d ", u);
    vis[u] = true;
    for (int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if (!vis[v]) {
            dfs(v);
        }
    }
}

BFS广度优先搜索

从起点顶点开始，遍历这个点的所有邻接点。

每遍历一个点，将该点的所有邻接点加入队列，标记该点为已访问，直到队列为空，遍历结束。

void bfs(int u) {
    printf("%d ", u);
    vis[u] = true;
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            if (!vis[v]) {
                printf("%d ", v);
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

Dijkstra最短路算法

在实现Dijkstra最短路算法的过程中，创建了一个结构体edge，其中v是边的终点，w是边的权重。

1
2
3

struct edge {
    int v, w; // v: 终点， w: 权重
};

每次通过遍历，找到一条没有被访问过的距离最小的顶点，对这个点的所有邻接点更新距离为可能的最短距离。

void dijkstra(int s) {
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, min = INF;
        // 找到未访问的、距离最小的顶点
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < min) {
                u = j;
                min = dis[j];
            }
        }
        if (u == -1) break;
        vis[u] = true;
        // 更新距离（松弛）
        for (int j = 0; j < graph[u].size(); j++) {
            int v = graph[u][j].v;
            int w = graph[u][j].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
            }
        }
    }
}

2 实验结果说明与分析

BFS与DFS

第一行输入点和边的数量。

接下来每行为一条边的信息，其中第一个数字为起点，第二个数字为终点。

输入如下：

经过DFS和BFS遍历后，输出结果如下：

1 2	1 2 3 4 5 1 2 3 4 5

代码在homework3/graph.cpp。

Dijkstra最短路算法

第一行输入点和边的数量。

接下来每行为一条边的信息，其中第一个数字为起点，第二个数字为终点，第三个数字为边权。

输入如下：

输出起点（点1）到其他所有点的最短距离。

通过更改函数参数，可以设定任意一个起点。

输出如下：

node 1 to 1: minimum weight is 0
node 1 to 2: minimum weight is 8
node 1 to 3: minimum weight is 5
node 1 to 4: minimum weight is 9
node 1 to 5: minimum weight is 7

代码开源在：https://gitee.com/littlebear0729/data-structure-and-algorithm/tree/master/homework3