鄰接表在有向圖中的應用

一、鄰接表的概念

鄰接表是一種圖的存儲結構。它由一個鏈表數組組成，每個節點表示圖中的一個頂點，每個節點對應的鏈表記錄與該頂點相鄰的所有頂點。

二、鄰接表在有向圖中的使用

有向圖是一種圖，其邊有一個方向。鄰接表在有向圖中的使用，主要有以下兩個方面：

1. 存儲有向圖信息

有向圖中每一條有向邊是從某一個頂點指向另一個頂點的，因此在鄰接表中，與每個頂點對應的鏈表記錄的是該頂點所指向的其他頂點。

比如，我們定義了一個有向圖G(V,E)，其中V為頂點集合，E為有向邊集合。那麼G的鄰接表定義如下：

class DirectedGraphNode {
public:
    int val;
    vector neighbors;
    DirectedGraphNode(int x) : val(x) {};
};

在上述定義中，每個DirectedGraphNode表示有向圖中的一個頂點，val為該頂點的值，neighbors為一個向量，記錄該頂點所指向的其他頂點。

2. 基於鄰接表的有向圖算法

鄰接表在有向圖的算法中應用廣泛，尤其是在圖搜索、拓撲排序、最短路徑等算法中。

三、鄰接表在有向圖中的實際案例

下面舉一個實際案例來說明鄰接表在有向圖中的應用。

假設有一個學校，其中每個班級都有一個班主任和若干個學生。如果所有班主任之間都有指導關係，則可以將這些班主任看作圖中的頂點，將指導關係看作圖中的有向邊。這樣就可以將該學校的組織結構看作一個有向圖。

為了方便存儲和查詢該學校的組織結構，可以使用鄰接表來表示該有向圖。具體做法如下：

1. 創建一個DirectedGraphNode類，用於表示有向圖中的頂點。

class DirectedGraphNode {
public:
    string name; // 班主任姓名
    vector neighbors; // 指導關係
    DirectedGraphNode(string n) : name(n) {};
};

2. 創建一個函數createGraph，該函數將學校的組織結構轉化成有向圖，並返回圖的根節點，即所有班主任之間都有指導關係的頂點。

DirectedGraphNode* createGraph() {
    // 創建班主任節點
    DirectedGraphNode* nodeA = new DirectedGraphNode("A");
    DirectedGraphNode* nodeB = new DirectedGraphNode("B");
    DirectedGraphNode* nodeC = new DirectedGraphNode("C");
    DirectedGraphNode* nodeD = new DirectedGraphNode("D");

    // 建立指導關係
    nodeA->neighbors.push_back(nodeB);
    nodeB->neighbors.push_back(nodeC);
    nodeC->neighbors.push_back(nodeD);
    nodeD->neighbors.push_back(nodeA);

    return nodeA;
}

3. 創建一個函數findRoot，該函數根據有向圖的組織結構，找出所有班主任之間都有指導關係的頂點，即圖的根節點。如果存在多個根節點，則返回任意一個即可。

DirectedGraphNode* findRoot(DirectedGraphNode* node) {
    queue q;
    unordered_set visited;

    q.push(node);
    visited.insert(node);

    while (!q.empty()) {
        DirectedGraphNode* cur = q.front();
        q.pop();

        for (int i = 0; i neighbors.size(); i++) {
            DirectedGraphNode* neighbor = cur->neighbors[i];
            if (visited.count(neighbor)) continue;
            visited.insert(neighbor);
            q.push(neighbor);
        }
    }

    return node;
}

在上述代碼中，我們使用廣度優先搜索遍歷了整個有向圖，並將遍歷到的頂點放入一個unordered_set中，以記錄已經訪問過的頂點。最後遍歷結束後，unordered_set中剩餘的頂點就是未被遍歷到的頂點，它們之間未建立指導關係，因此它們不是圖的根節點。剩下的頂點中任意一個都可以被認為是圖的根節點。