第6节：高级图算法

我们将继续深入学习图论的高级图算法。这些算法解决了一些经典的图论问题，例如最短路径、最小生成树、图的连通性等。这些问题在实际应用中有着广泛的使用，如网络优化、交通路线规划、数据流分析等。

第6节：高级图算法

6.1 最短路径算法

最短路径问题是指在图中找到从一个顶点到另一个顶点的最短路径。根据图的性质，常见的最短路径算法包括：

Dijkstra算法（适用于无负权边的图）
Bellman-Ford算法（适用于有负权边的图）
Floyd-Warshall算法（用于计算所有顶点对之间的最短路径）

1. Dijkstra算法

Dijkstra算法用于计算从单个源点到其他所有顶点的最短路径，前提是边的权值都是非负的。该算法使用贪心策略，通过选择未处理的距离最小的顶点，逐步构造最短路径树。

Dijkstra算法的实现（使用邻接矩阵表示图）：

#include <stdio.h>
#include <limits.h>

#define V 5 // 图中顶点的数量

// 找到未访问顶点中距离最小的顶点
int minDistance(int dist[], int visited[]) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++) {
        if (!visited[v] && dist[v] <= min) {
            min = dist[v], minIndex = v;
        }
    }
    return minIndex;
}

// 打印源点到其他顶点的最短路径
void printSolution(int dist[]) {
    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d\t%d\n", i, dist[i]);
    }
}

// Dijkstra算法的实现
void dijkstra(int graph[V][V], int src) {
    int dist[V]; // dist[i] 保存源点到i的最短路径距离
    int visited[V]; // visited[i]表示顶点i是否已被处理

    // 初始化：所有顶点的距离为无穷大，所有顶点未被访问
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }

    dist[src] = 0; // 源点到自身的距离为0

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited); // 选取未访问顶点中距离最小的顶点
        visited[u] = 1;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printSolution(dist);
}

int main() {
    // 图的邻接矩阵表示
    int graph[V][V] = {
        {0, 10, 0, 30, 100},
        {10, 0, 50, 0, 0},
        {0, 50, 0, 20, 10},
        {30, 0, 20, 0, 60},
        {100, 0, 10, 60, 0}
    };

    dijkstra(graph, 0); // 从顶点0开始计算最短路径

    return 0;
}

运行结果：

Vertex  Distance from Source
0       0
1       10
2       50
3       30
4       60

2. Bellman-Ford算法

Bellman-Ford算法用于有负权边的图，它能够检测负权环。如果图中存在负权环，则说明不存在有效的最短路径，因为路径的权重可以无限小。

Bellman-Ford算法的实现（使用邻接矩阵表示图）：

#include <stdio.h>
#include <limits.h>

#define V 5 // 顶点数量
#define E 8 // 边数量

struct Edge {
    int src, dest, weight;
};

// 打印最短路径结果
void printArr(int dist[], int n) {
    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\n", i, dist[i]);
    }
}

// Bellman-Ford算法
void bellmanFord(struct Edge edges[], int src) {
    int dist[V];

    // 初始化所有顶点的距离为无穷大，源点距离为0
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
    }
    dist[src] = 0;

    // 对所有边进行V-1次松弛操作
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int weight = edges[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    // 检查是否存在负权环
    for (int i = 0; i < E; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;
        int weight = edges[i].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            printf("Graph contains negative weight cycle\n");
            return;
        }
    }

    printArr(dist, V);
}

int main() {
    struct Edge edges[E] = {
        {0, 1, -1}, {0, 2, 4}, {1, 2, 3},
        {1, 3, 2}, {1, 4, 2}, {3, 2, 5},
        {3, 1, 1}, {4, 3, -3}
    };

    bellmanFord(edges, 0); // 从顶点0开始计算最短路径

    return 0;
}

运行结果：

Vertex  Distance from Source
0       0
1       -1
2       2
3       -2
4       1

3. Floyd-Warshall算法

Floyd-Warshall算法用于计算所有顶点对之间的最短路径，适用于有向图。该算法通过动态规划的思想，在三重循环中逐步更新最短路径矩阵。

Floyd-Warshall算法的实现：

#include <stdio.h>

#define V 4
#define INF 99999 // 用于表示无穷大的距离

// 打印矩阵
void printSolution(int dist[V][V]) {
    printf("Shortest distances between every pair of vertices:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) {
                printf("%7s", "INF");
            } else {
                printf("%7d", dist[i][j]);
            }
        }
        printf("\n");
    }
}

// Floyd-Warshall算法
void floydWarshall(int graph[V][V]) {
    int dist[V][V], i, j, k;

    // 初始化最短路径矩阵
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // 通过中间顶点逐步更新最短路径
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph);
    return 0;
}

运行结果：

Shortest distances between every pair of vertices:
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

6.2 最小生成树算法

最小生成树（MST）是图中的一棵树，它包含图中的所有顶点且边的总权值最小。常见的最小生成树算法有：

Kruskal算法：使用贪心策略，基于边的权重，逐渐加入最小权重的边，直到构造出一棵生成树。
Prim算法：基于顶点逐步扩展生成树，每次选择未加入树的顶点中与树最接近的顶点。

1. Kruskal算法

Kruskal算法通过逐步选择最小权重的边来构建最小生成树，通常使用**并查集（Disjoint Set Union, DSU）**来检测环。

Kruskal算法的实现：

#include <stdio.h>
#include <stdlib.h>

#define V 4 // 顶点数量
#define E 5 // 边数量

struct Edge {
    int src, dest, weight;
};

struct Graph {
    struct Edge edges[E];
};

// 并查集：查找根节点
int find(int parent[], int i) {
    if (parent[i] == i) {
        return i;
    }
    return find(parent, parent[i]);
}

// 并查集：合并两个集合
void unionSets(int parent[], int rank[], int x, int y) {
    int xroot = find(parent, x);
    int yroot = find(parent, y);

    if (rank[xroot] < rank[yroot]) {
        parent[xroot] = yroot;
    } else if (rank[xroot] > rank[yroot]) {
        parent[yroot] = xroot;
    } else {
        parent[yroot] = xroot;
        rank[xroot]++;
    }
}

// 比较函数用于根据边的权重排序
int compare(const void* a, const void* b) {
    struct Edge* edgeA = (struct Edge*)a;
    struct Edge* edgeB = (struct Edge*)b;
    return edgeA->weight - edgeB->weight;
}

// Kruskal算法
void kruskal(struct Graph* graph) {
    struct Edge result[V]; // 最小生成树的边
    int parent[V];
    int rank[V];

    // 初始化并查集
    for (int v = 0; v < V; v++) {
        parent[v] = v;
        rank[v] = 0;
    }

    // 按权重对边进行排序
    qsort(graph->edges, E, sizeof(graph->edges[0]), compare);

    int e = 0; // 已加入的边数
    int i = 0; // 当前考虑的边

    while (e < V - 1 && i < E) {
        struct Edge nextEdge = graph->edges[i++];

        int x = find(parent, nextEdge.src);
        int y = find(parent, nextEdge.dest);

        if (x != y) { // 如果不构成环
            result[e++] = nextEdge;
            unionSets(parent, rank, x, y);
        }
    }

    printf("Following are the edges in the constructed MST:\n");
    for (i = 0; i < e; i++) {
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
    }
}

int main() {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

    graph->edges[0] = (struct Edge){0, 1, 10};
    graph->edges[1] = (struct Edge){0, 2, 6};
    graph->edges[2] = (struct Edge){0, 3, 5};
    graph->edges[3] = (struct Edge){1, 3, 15};
    graph->edges[4] = (struct Edge){2, 3, 4};

    kruskal(graph);

    return 0;
}

运行结果：

Following are the edges in the constructed MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

练习题

Prim算法：实现Prim算法，使用优先队列来选择权重最小的边。
Dijkstra vs Bellman-Ford：编写程序对比Dijkstra和Bellman-Ford算法在有负权边图上的表现。
图的环检测：使用DFS或并查集实现无向图和有向图的环检测。
拓扑排序：在有向无环图（DAG）中，使用DFS实现拓扑排序。
旅行商问题：实现旅行商问题的近似解法。

完成这些练习后，你将掌握图的高级算法和技术。

菜单

分享

第6节：高级图算法