目錄

1、最小生成樹

1.1 概念?

1.2 普利姆算法（Prim）

1.3 克魯斯卡爾算法（Kruskal）?

2、最短路徑

2.1 迪杰斯特拉算法（Dijkstra）

2.2 弗洛伊德算法（Floyd）?

2.3 BFS算法，Dijkstra算法，F(xiàn)loyd算法的對比

3、有向無環(huán)圖描述表達(dá)式

3.1 有向無環(huán)圖定義及特點

3.2 描述表達(dá)式

4、拓?fù)渑判?/p>

4.1 AOV網(wǎng)

4.2 步驟?

4.3 DFS實現(xiàn)拓?fù)渑判?

5、逆拓?fù)渑判?/p>

5.1 步驟?

5.2 DFS實現(xiàn)逆拓?fù)渑判??

6、關(guān)鍵路徑

6.1 AOE網(wǎng)?

6.2 求解方法

6.3 特性?

1、最小生成樹

1.1 概念?

????????最小生成樹是一種基于圖的算法，用于在一個連通加權(quán)無向圖中找到一棵生成樹，使得樹上所有邊的權(quán)重之和最小。最小生成樹指一張無向圖的生成樹中邊權(quán)最小的那棵樹。生成樹是指一張無向圖的一棵極小連通子圖，它包含了原圖的所有頂點，但只有足以構(gòu)成一棵樹的 n-1 條邊。最小生成樹可以用來解決最小通信代價、最小電纜費用、最小公路建設(shè)等問題。常見的求解最小生成樹的算法有Prim算法和Kruskal算法。

?

1.2 普利姆算法（Prim）

?????????Prim算法的基本思想是從一個任意頂點開始，每次添加一個距離該頂點最近的未訪問過的頂點和與之相連的邊，直到所有頂點都被訪問過。

其基本步驟如下：

1. 初始化：定義一個空的集合S表示已經(jīng)確定為最小生成樹的結(jié)點集合，和一個數(shù)組dist表示當(dāng)前結(jié)點到S集合中最短距離，初始時S集合為空，數(shù)組dist中所有元素為正無窮，將任意一個結(jié)點u加到S集合中。

2. 找到到S集合距離最近的結(jié)點v，并將v加入到S集合中。

3. 更新數(shù)組dist，更新S集合中的結(jié)點到其它結(jié)點的距離。對于所有不在S集合中的結(jié)點w，如果從v到w的距離小于dist[w]，則更新dist[w]的值為從v到w的距離。

4. 重復(fù)以上步驟2和步驟3，直到所有的結(jié)點都加入到S集合中，即構(gòu)成了最小生成樹。

該算法的時間復(fù)雜度為O(n^2)，其中n為圖的頂點數(shù)。

以下是用C語言實現(xiàn)Prim算法的代碼，假設(shè)圖的節(jié)點從0到n-1編號。

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

#define MAX_N 1000    // 最大頂點數(shù)
#define INF INT_MAX   // 正無窮
#define false 0
#define true 1

// 無向圖的鄰接矩陣表示法
int graph[MAX_N][MAX_N];   // 圖的鄰接矩陣
int visited[MAX_N];        // 標(biāo)記結(jié)點是否已加入最小生成樹
int dist[MAX_N];           // 記錄結(jié)點到最小生成樹的距離
int parent[MAX_N];         // 記錄結(jié)點的父節(jié)點（即最小生成樹的邊）

int prim(int n)
{
    // 初始化
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[0] = 0;  // 從結(jié)點0開始構(gòu)建最小生成樹

    for (int i = 0; i < n - 1; i++) {  // n - 1次循環(huán)
        int min_dist = INF;
        int min_index = -1;
        // 找出距離最小生成樹最近的結(jié)點
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }
        if (min_index == -1) {
            break;  // 找不到未訪問的結(jié)點，算法結(jié)束
        }
        visited[min_index] = true;
        // 更新未加入最小生成樹的結(jié)點到最小生成樹的距離和父節(jié)點
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[min_index][j] < dist[j]) {
                dist[j] = graph[min_index][j];
                parent[j] = min_index;
            }
        }
    }
    // 輸出最小生成樹
    int cost = 0;
    for (int i = 1; i < n; i++) {
        printf("%d -> %d : %d\n", parent[i], i, graph[i][parent[i]]);
        cost += graph[i][parent[i]];
    }
    return cost;
}

int main()
{
    int n;           // 結(jié)點數(shù)量
    int m;           // 邊數(shù)量
    scanf("%d%d", &n, &m);
    // 初始化鄰接矩陣
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = INF;
        }
    }
    // 讀入邊
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = w;
        graph[v][u] = w;  // 無向圖，所以要加上反向邊
    }
    int cost = prim(n);
    printf("cost = %d\n", cost);
    return 0;
}
 

????????dist數(shù)組記錄的是結(jié)點到最小生成樹的距離，parent數(shù)組記錄的是結(jié)點的父節(jié)點，visited數(shù)組記錄結(jié)點是否已加入最小生成樹。在每次循環(huán)中，找出距離最小生成樹最近的結(jié)點，并將其標(biāo)記為已訪問，再更新未加入最小生成樹的結(jié)點到最小生成樹的距離和父節(jié)點。最后輸出最小生成樹的邊，以及最小生成樹的總權(quán)值（即邊的權(quán)值之和）。

1.3 克魯斯卡爾算法（Kruskal）?

????????Kruskal算法的基本思想是先將圖中所有邊按邊權(quán)從小到大排序，然后逐個加入到生成樹中，但是要保證加入后生成樹仍然是無環(huán)的。如果加入某一條邊形成了環(huán)，則不加入該邊，繼續(xù)考慮下一條邊。?

步驟如下：

1. 將所有邊按照邊權(quán)從小到大排序；
2. 初始化一個空的樹；
3. 從排序后的邊列表中選擇權(quán)重最小的邊，并判斷這條邊的兩個端點是否在同一棵樹中；
4. 如果這條邊的兩個端點不在同一棵樹中，則將這條邊加入最小生成樹中，并將這兩個端點所在的樹合并成一棵樹；
5. 重復(fù)步驟3和步驟4，直到所有的邊都被考慮過。

?以下是用C語言實現(xiàn)Kruskal算法的代碼，假設(shè)圖的節(jié)點從0到n-1編號。

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

#define MAX_N 1000    // 最大頂點數(shù)
#define INF INT_MAX   // 正無窮
#define false 0
#define true 1

// 邊的結(jié)構(gòu)體
typedef struct Edge {
    int u;
    int v;
    int w;
} Edge;

Edge edges[MAX_N * MAX_N];  // 邊集合
int parent[MAX_N];         // 記錄結(jié)點的父節(jié)點
int rank[MAX_N];           // 記錄結(jié)點所在集合的秩

int cmp(const void* a, const void* b)
{
    Edge* edge1 = (Edge*)a;
    Edge* edge2 = (Edge*)b;
    return edge1->w - edge2->w;
}

int find(int x)
{
    // 路徑壓縮
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y)
{
    // 按秩合并
    int root_x = find(x);
    int root_y = find(y);
    if (rank[root_x] < rank[root_y]) {
        parent[root_x] = root_y;
    } else {
        parent[root_y] = root_x;
        if (rank[root_x] == rank[root_y]) {
            rank[root_x]++;
        }
    }
}

int kruskal(int n, int m)
{
    // 初始化
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    // 按邊權(quán)從小到大排序
    qsort(edges, m, sizeof(Edge), cmp);
    // 構(gòu)建最小生成樹
    int cost = 0;
    int count = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        if (find(u) != find(v)) {    // 判斷是否在同一個集合中
            unite(u, v);
            cost += w;
            count++;
            if (count == n - 1) {    // 邊數(shù)等于n-1，生成樹構(gòu)建完成
                break;
            }
        }
    }
    // 輸出最小生成樹邊
    for (int i = 0; i < n; i++) {
        if (parent[i] == i) {   // 找到根節(jié)點
            for (int j = 0; j < m; j++) {
                if ((edges[j].u == i && parent[edges[j].v] == i)
                    || (edges[j].v == i && parent[edges[j].u] == i)) {
                    printf("%d -> %d : %d\n", edges[j].u, edges[j].v, edges[j].w);
                }
            }
        }
    }
    return cost;
}

int main()
{
    int n;           // 結(jié)點數(shù)量
    int m;           // 邊數(shù)量
    scanf("%d%d", &n, &m);
    // 讀入邊并構(gòu)建邊集合
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edges[i].u = u;
        edges[i].v = v;
        edges[i].w = w;
    }
    int cost = kruskal(n, m);
    printf("cost = %d\n", cost);
    return 0;
}
 

????????其中，邊的結(jié)構(gòu)體包括起點、終點和邊權(quán)。在Kruskal算法中，先對邊按照權(quán)值從小到大進行排序，每次取出最小的邊，如果它不連通任何已經(jīng)選出的邊，則加入最小生成樹中。為了判斷兩個結(jié)點是否在同一個集合中，可以使用并查集的數(shù)據(jù)結(jié)構(gòu)，其中parent數(shù)組記錄結(jié)點的父節(jié)點，rank數(shù)組記錄結(jié)點所在集合的秩。并查集的find和unite函數(shù)實現(xiàn)路徑壓縮和按秩合并。最后輸出最小生成樹的邊，以及最小生成樹的總權(quán)值（即邊的權(quán)值之和）。?

2、最短路徑

2.1 迪杰斯特拉算法（Dijkstra）

????????Dijkstra算法是一種解決單源最短路徑問題的貪心算法，它的基本思路是從起點開始，每次選擇當(dāng)前最短路徑中的一個頂點，然后更新它的鄰居的最短路徑。

以下是Dijkstra算法的詳細(xì)步驟：

1. 初始化數(shù)據(jù)結(jié)構(gòu)：創(chuàng)建一個距離數(shù)組dist，用來記錄起點到每個頂點的最短距離，初始化為正無窮；創(chuàng)建一個visited數(shù)組，記錄每個頂點是否被訪問過；創(chuàng)建一個前驅(qū)數(shù)組path，記錄每個頂點的前驅(qū)頂點。

2. 將起點的dist設(shè)為0，將visited設(shè)為false，將path設(shè)為null。

3. 對于起點的所有鄰居，更新它們的dist為起點到鄰居的距離，并將它們的path設(shè)為起點。

4. 重復(fù)以下步驟，直到所有頂點都被訪問過： a. 從未被訪問過的頂點中，選擇dist最小的頂點作為當(dāng)前頂點。 b. 將當(dāng)前頂點設(shè)為已訪問。 c. 對當(dāng)前頂點的所有鄰居，如果當(dāng)前頂點到鄰居的距離比鄰居的dist值小，就更新鄰居的dist值和path值。

5. 通過prev數(shù)組可找到從起點到任意頂點的最短路徑。

?下面是一個使用C語言實現(xiàn)Dijkstra算法的示例：

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

#define V 6    // 頂點數(shù)

// 尋找dist數(shù)組中最小值對應(yīng)的下標(biāo)
int minDistance(int dist[], bool visited[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (visited[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

// 打印最短路徑
void printPath(int path[], int dest)
{
    if (path[dest] == -1)
        return;

    printPath(path, path[dest]);
    printf("%d ", dest);
}

// 打印最短路徑和距離
void printSolution(int dist[], int path[], int src)
{
    printf("Vertex\tDistance\tPath");
    for (int i = 0; i < V; i++)
    {
        printf("\n%d -> %d\t%d\t\t%d ", src, i, dist[i], src);
        printPath(path, i);
    }
}

// Dijkstra算法
void dijkstra(int graph[V][V], int src)
{
    int dist[V];     // 存儲src到各個頂點的最短距離
    bool visited[V]; // 標(biāo)記頂點是否已訪問過
    int path[V];     // 存儲最短路徑

    // 初始化
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, visited[i] = false, path[i] = -1;

    dist[src] = 0;

    // 計算最短路徑
    for (int count = 0; count < V - 1; count++)
    {
        int u = minDistance(dist, visited);

        visited[u] = true;

        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], path[v] = u;
    }

    // 打印結(jié)果
    printSolution(dist, path, src);
}

int main()
{
    // 構(gòu)建鄰接矩陣
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0},
        {4, 0, 8, 0, 0, 0},
        {0, 8, 0, 7, 0, 4},
        {0, 0, 7, 0, 9, 14},
        {0, 0, 0, 9, 0, 10},
        {0, 0, 4, 14, 10, 0}
    };

    dijkstra(graph, 0);    // 計算從0開始的最短路徑

    return 0;
}
 

????????在上述代碼中，我們使用鄰接矩陣來表示圖，使用dist數(shù)組來記錄起點到各個頂點的最短距離，使用visited數(shù)組來記錄頂點是否已訪問過，使用path數(shù)組來記錄最短路徑。

2.2 弗洛伊德算法（Floyd）?

????????Floyd算法是一種動態(tài)規(guī)劃算法，用于解決有向圖中任意兩點之間的最短路徑問題。?時間復(fù)雜度為O(n^3)，其中n為節(jié)點數(shù)。其步驟如下：

????????1. 創(chuàng)建一個n × n的矩陣D來表示任意兩點之間的最短距離，其中n為圖的頂點數(shù)。

????????2. 初始化矩陣D，對于每個頂點i，設(shè)其到自身的距離為0，對于所有i和j之間存在邊的情況，設(shè)其距離為對應(yīng)的邊權(quán)值，如果不存在邊，則將對應(yīng)的D[i][j]設(shè)為無窮大。

????????3. 對于任意的k∈[1,n]，依次考慮頂點1~n，并計算經(jīng)過頂點k的最短路徑，即計算D[i][j] = min(D[i][j], D[i][k] + D[k][j])，其中i,j∈[1,n]。

????????4. 經(jīng)過第3步的計算后，矩陣D中存儲的即為任意兩點之間的最短距離。

????????5. 如果矩陣D中存在負(fù)環(huán)，說明存在一些頂點之間的距離可以無限縮小，此時無法得到正確的最短路徑。

????????6. 如果需要求出最短路徑，則需要借助于一個前驅(qū)矩陣P，其中P[i][j]表示從i到j(luò)的最短路徑上，j的前驅(qū)頂點是哪個。可以通過在計算D[i][j]時，將P[i][j]設(shè)置為經(jīng)過的頂點k，來得到前驅(qū)矩陣P。

?下面是C語言實現(xiàn)Floyd算法的示例代碼：

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

#define INF INT_MAX
#define MAXN 100

int dist[MAXN][MAXN];
int path[MAXN][MAXN];

void floyd(int n) {
    /* 初始化距離矩陣和路徑矩陣 */
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                dist[i][j] = 0;
                path[i][j] = -1; /* 表示 i 到 j 沒有中間節(jié)點 */
            } else {
                dist[i][j] = INF;
                path[i][j] = -1;
            }
        }
    }

    /* 根據(jù)邊權(quán)值更新距離矩陣和路徑矩陣 */
    int u, v, w;
    while (scanf("%d %d %d", &u, &v, &w) == 3) {
        dist[u][v] = w;
        path[u][v] = u; /* i 到 j 的路徑經(jīng)過 u */
    }

    /* 計算任意兩點之間的最短路徑 */
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] < INF && dist[k][j] < INF && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j]; /* i 到 j 的路徑經(jīng)過 u 的話，i 到 k 的路徑就經(jīng)過 u 了，于是將 i 到 k 的路徑經(jīng)過的節(jié)點掛到 i 到 j 的路徑上 */
                }
            }
        }
    }
}

void print_path(int u, int v) {
    if (path[u][v] == -1) { /* i 到 j 沒有中間節(jié)點 */
        printf("%d", v);
    } else { /* i 到 j 的路徑經(jīng)過 u */
        print_path(u, path[u][v]); /* 遞歸打印 i 到 u 的路徑 */
        printf("->%d", v);
    }
}

int main() {
    int n;
    scanf("%d", &n);

    floyd(n);

    int s, t;
    scanf("%d %d", &s, &t);

    printf("%d\n", dist[s][t]);
    print_path(s, t);

    return 0;
}
 

????????該代碼首先讀入圖的規(guī)模 n，然后讀入每條邊的起點、終點和邊權(quán)值，根據(jù)這些信息構(gòu)建鄰接矩陣。然后，它使用Floyd算法計算任意兩點之間的最短路徑和路徑矩陣。最后，給定起點 s?和終點 t，輸出它們之間的最短路程和路徑。

2.3 BFS算法，Dijkstra算法，F(xiàn)loyd算法的對比

?

3、有向無環(huán)圖描述表達(dá)式

3.1 有向無環(huán)圖定義及特點

????????有向無環(huán)圖（Directed Acyclic Graph，簡稱DAG）是一種有向圖，其中不存在環(huán)路，即從任意一個頂點出發(fā)不可能經(jīng)過若干條邊回到此頂點。通常用來表示任務(wù)調(diào)度、依賴關(guān)系等場景，具有以下特點：

1. 有向性：DAG中所有邊均有方向，即起點指向終點。

2. 無環(huán)性：DAG中不存在環(huán)路，即不能從一個頂點出發(fā)沿其周游返回此頂點。

3. 頂點與邊的關(guān)系：DAG中的頂點表示任務(wù)、事件、狀態(tài)等，邊表示依賴關(guān)系、控制關(guān)系等。

4. 拓?fù)渑判颍篋AG可以進行拓?fù)渑判?，即將DAG中所有頂點排序，使得對于任意一條邊(u,v)，頂點u都排在v的前面。

3.2 描述表達(dá)式

?????????有向無環(huán)圖可以用于描述表達(dá)式的計算順序，其中每個節(jié)點表示一個操作符或操作數(shù)，每個有向邊表示操作數(shù)或操作符之間的依賴關(guān)系和計算順序。

?

例如，對于表達(dá)式 "5*(2+3)":

????????首先，將 "+" 表示為一個節(jié)點，并有兩個入邊和一條出邊； 然后，將 "2" 和 "3" 也表示為節(jié)點，并分別與 "+" 節(jié)點相連； 接著，再將 "*" 表示為節(jié)點，并與 "5" 和 "+" 節(jié)點相連； 最后，整個有向無環(huán)圖如圖所示：

         +        // "+" 節(jié)點
        / \
       /   \
      2     3    // "2" 和 "3" 節(jié)點
       \   /
        \ /
         *       // "*" 節(jié)點
         |
         5       // "5" 節(jié)點

????????按照拓?fù)渑判虻捻樞虮闅v這個有向無環(huán)圖，就可以得到表達(dá)式的計算順序：2 -> 3 -> + -> 5 -> *，即先計算 2 和 3 的和，再將結(jié)果與 5 相乘，最后得到結(jié)果 25。

4、拓?fù)渑判?/h2>

4.1 AOV網(wǎng)

?

4.2 步驟?

拓?fù)渑判蚴菍τ邢驁D進行排序的一種算法，步驟如下：

1. 初始化：首先，將所有入度為0的頂點加入到一個隊列中。

2. 遍歷：從隊列中取出一個頂點，輸出該頂點并刪除該頂點的所有出邊（即將它所指向的頂點的入度減1）。如果該頂點刪除后所指向的結(jié)點入度為0，則將其加入隊列中。

3. 重復(fù)遍歷：重復(fù)以上操作，直到隊列為空為止。

4. 判斷：如果輸出的頂點數(shù)等于圖中的頂點數(shù)，則拓?fù)渑判虺晒Γ⑤敵鼋Y(jié)果；否則，圖中存在環(huán)，拓?fù)渑判蚴　?/p>

?

4.3 DFS實現(xiàn)拓?fù)渑判?

????????DFS實現(xiàn)拓?fù)渑判虻幕舅悸肥牵簭娜我庖粋€沒有后繼節(jié)點的節(jié)點出發(fā)，沿著它的各個鏈路不斷深入，并記錄經(jīng)過的節(jié)點，直到到達(dá)一個沒有出邊的節(jié)點為止。在返回的過程中，將經(jīng)過的節(jié)點依次加入結(jié)果數(shù)組中，直到所有的節(jié)點都加入到結(jié)果數(shù)組中。

DFS實現(xiàn)拓?fù)渑判虻腃語言代碼示例：

#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000

int n, m;
int G[MAXN][MAXN];  //鄰接矩陣存圖
int vis[MAXN], res[MAXN], idx = 0;  //vis數(shù)組用于記錄是否訪問過，res數(shù)組用于存儲結(jié)果

void dfs(int u){
    vis[u] = 1;  //標(biāo)記為已訪問
    for(int v = 0; v < n; v++){
        if(G[u][v] && !vis[v]){  //如果v是u的后繼節(jié)點且未被訪問過
            dfs(v);  //繼續(xù)深入
        }
    }
    res[idx++] = u;  //將該節(jié)點存入結(jié)果數(shù)組中
}

void topSort(){
    for(int i = 0; i < n; i++){
        if(!vis[i]){  //從未被訪問過的節(jié)點出發(fā)
            dfs(i);
        }
    }
    for(int i = n - 1; i >= 0; i--){  //倒序輸出結(jié)果數(shù)組
        printf("%d ", res[i]);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        G[u][v] = 1;  //有向邊
    }
    topSort();
    return 0;
}
 

????????其中，G數(shù)組為鄰接矩陣存儲圖，vis數(shù)組用于記錄是否訪問過，res數(shù)組用于存儲結(jié)果，idx為結(jié)果數(shù)組的下標(biāo)。topSort函數(shù)是主要的拓?fù)渑判蛩惴?，遍歷所有節(jié)點并調(diào)用dfs函數(shù)，dfs函數(shù)通過遞歸的方式實現(xiàn)深度優(yōu)先遍歷。最后，倒序輸出結(jié)果數(shù)組，即可得到拓?fù)渑判虻慕Y(jié)果。

5、逆拓?fù)渑判?/h2>

5.1 步驟?

????????逆拓?fù)渑判蚴侵冈谝粋€有向無環(huán)圖中，對于每個節(jié)點v，輸出所有能夠到達(dá)v的節(jié)點。逆拓?fù)渑判虻牟襟E如下：

1. 初始化一個空的結(jié)果列表和一個空的隊列。
2. 對于每個節(jié)點v，計算能夠到達(dá)v的節(jié)點數(shù)目，記為out_degree[v]。
3. 將所有out_degree[v]為0（出度為0）的節(jié)點加入隊列。
4. 當(dāng)隊列非空時，取出隊首節(jié)點u，并將其加入結(jié)果列表。
5. 對于u的每個鄰居節(jié)點v，將out_degree[v]減1。
6. 若out_degree[v]等于0，則將v加入隊列。
7. 重復(fù)步驟4-6直到隊列為空。
8. 返回結(jié)果列表。

5.2 DFS實現(xiàn)逆拓?fù)渑判??

????????逆拓?fù)渑判蛑傅氖窃谝粋€有向無環(huán)圖(DAG)中，對所有節(jié)點進行排序，使得對于任意一條有向邊(u, v)，都有排在前面的節(jié)點先于排在后面的節(jié)點。逆拓?fù)渑判蚩梢酝ㄟ^深度優(yōu)先搜索(DFS)實現(xiàn)。具體實現(xiàn)步驟如下：

1. 定義一個數(shù)組visited，用于記錄每個節(jié)點是否已經(jīng)被訪問過，初始值為0。

2. 定義一個棧stack，用于存儲已經(jīng)訪問過的節(jié)點。

3. 對于每個節(jié)點u，進行DFS搜索，具體步驟如下：

   a. 標(biāo)記節(jié)點u已經(jīng)被訪問過，visited[u]=1。

   b. 對于節(jié)點u的每個鄰接節(jié)點v，如果該節(jié)點還沒有被訪問過，則進行DFS搜索。

   c. 將節(jié)點u入棧。

4. 當(dāng)所有節(jié)點都搜索完畢后，從棧頂開始按順序取出節(jié)點，生成逆拓?fù)渑判蚪Y(jié)果。

下面是C語言實現(xiàn)代碼：

#include <stdio.h>
#define MAX_VERTEX_NUM 100

int visited[MAX_VERTEX_NUM], topo[MAX_VERTEX_NUM], top = -1;
int vex_num, arc_num;
int Graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

void DFS(int u) {
    visited[u] = 1;
    int v;
    for (v = 0; v < vex_num; v++) {
        if (Graph[u][v] == 1 && visited[v] == 0) {
            DFS(v);
        }
    }
    topo[++top] = u;
}

void TopoSort() {
    int i, j;
    for (i = 0; i < vex_num; i++) {
        visited[i] = 0;
    }
    top = -1;
    for (i = 0; i < vex_num; i++) {
        if (visited[i] == 0) {
            DFS(i);
        }
    }
    printf("逆拓?fù)渑判蚪Y(jié)果：");
    for (i = vex_num - 1; i >= 0; i--) {
        printf("%d ", topo[i]);
    }
}

int main() {
    int i, j, u, v;
    scanf("%d%d", &vex_num, &arc_num);
    for (i = 0; i < vex_num; i++) {
        for (j = 0; j < vex_num; j++) {
            Graph[i][j] = 0;
        }
    }
    for (i = 0; i < arc_num; i++) {
        scanf("%d%d", &u, &v);
        Graph[u][v] = 1;
    }
    TopoSort();
    return 0;
}

示例輸入：

7 10
0 1
0 2
1 3
1 5
1 4
2 5
3 6
4 6
5 4
5 6

示例輸出：

逆拓?fù)渑判蚪Y(jié)果：0 2 1 5 4 3 6

6、關(guān)鍵路徑

6.1 AOE網(wǎng)?

?

6.2 求解方法

????????關(guān)鍵路徑是某個項目中的最長路徑，它決定了整個項目的總時長，需要正確地計算和管理。以下是關(guān)鍵路徑的求解方法：

1. 確定項目的活動和它們的先后關(guān)系。

2. 繪制網(wǎng)絡(luò)圖，包括活動的節(jié)點和它們之間的連接線，確定每個活動的預(yù)計持續(xù)時間和最早開始時間。

3. 根據(jù)網(wǎng)絡(luò)圖計算每個活動的最早開始時間和最遲開始時間。

4. 計算每個活動的最早完成時間和最遲完成時間。

5. 通過計算每個活動的浮動時間，確定哪些活動是關(guān)鍵路徑上的活動。

6. 將關(guān)鍵路徑上的活動按照其完成時間的順序排列，找出整個項目的最長時間和關(guān)鍵路徑。

7. 對于非關(guān)鍵路徑上的活動，可以進行資源優(yōu)化，以縮短項目的總時長。

總之，關(guān)鍵路徑的求解需要清晰的項目規(guī)劃和正確的計算方法，能夠幫助項目管理人員更好地控制項目進度和資源，確保項目按時完成。

?

6.3 特性?

?

博主正在學(xué)習(xí)中，如果博文中有解釋錯誤的內(nèi)容，請大家指出??

????????????圖的應(yīng)用的知識點總結(jié)就到這里啦，如果對博文還滿意的話，勞煩各位大佬兒動動“發(fā)財?shù)男∈帧绷粝履鷮Σ┪牡馁澓蛯Σ┲鞯年P(guān)注吧????????????

文章來源地址http://www.zghlxwxcb.cn/news/detail-731328.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】圖的應(yīng)用：最小生成樹；最短路徑；有向無環(huán)圖描述表達(dá)式；拓?fù)渑判?；逆拓?fù)渑判?；關(guān)鍵路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！