圖中所有其他節點可訪問的節點數

圖中從任何特定節點可以到達的節點數量稱為圖中所有其他節點可訪問的節點數。它顯示了圖內可達性和連通性的程度。為了獲得此計數，我們從每個節點開始並調查所有可訪問的其他節點的路徑。在遍歷圖時，我們記錄可以訪問的節點。圖中可到達節點的計數包括所有可以到達的節點。這對於理解網路關係和資訊流效率至關重要。

使用的方法

  • 可達性矩陣

  • 連通分量

可達性矩陣

使用可達性矩陣（一個方陣）來計算圖中可到達的節點。矩陣的[i][j]項分別表示是否可以從節點i到達節點j。透過檢查矩陣的行，可以找到網路中從每個節點可以到達的節點。每一行中“1”的數量表示從給定節點可以到達的節點數，從而提供有關圖的總體連通性和可達性的資訊。透過提供有關圖中節點可訪問性的有用見解，該矩陣有助於理解圖中節點之間的連通性和關係。

演算法

  • 假設圖G中的節點總數為n。

  • 建立一個大小為n x n的二維陣列ReachabilityMatrix，其初始值為零。

  • 對於每個節點i，從0到n−1

    從節點i開始深度優先搜尋（DFS）或廣度優先搜尋（BFS）。

    將ReachabilityMatrix的值設定為1，並將所有從節點i可到達的節點標記為已訪問。

  • ReachabilityMatrix中有四行。

    計算行中“1”的數量，並將總和新增到count[]陣列的適當位置。

  • 給出count[]陣列。

示例

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int main() {
    int N = 5; 
    vector<vector<int>> graph(N);

    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[0].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(4);
    graph[2].push_back(4);

    vector<vector<bool>> reachabilityMatrix(N, vector<bool> (N, false));
    for (int i = 0; i < N; ++i) {
        vector<bool> visited(N, false);
        dfs(i, graph, visited);
        reachabilityMatrix[i] = visited;
    }

    for (int i = 0; i < N; ++i) {
        int count = 0;
        for (int j = 0; j < N; ++j) {
            if (reachabilityMatrix[i][j]) {
                count++;
            }
        }
        cout << "Vertex " << i << " can reach " << count << " nodes." << endl;
    }

    return 0;
}

輸出

Vertex 0 can reach 5 nodes.
Vertex 1 can reach 4 nodes.
Vertex 2 can reach 3 nodes.
Vertex 3 can reach 2 nodes.
Vertex 4 can reach 1 nodes.

連通分量

在“圖中所有其他節點可訪問的節點數”的上下文中，連通分量是可以透過直接或間接邊連線的節點集合，並且允許彼此之間進行通訊。我們識別這些相關的元件以便計算從每個其他節點可以到達的節點數量。在同一組件內，節點可以相互通訊。透過揭示特定元件中從所有其他節點可以到達的節點數量，計算每個元件的大小有助於我們更好地理解圖的整體連通性和資訊流效率。

演算法

  • 將圖G作為鄰接表或矩陣作為輸入。

  • 建立一個空的列表或陣列來跟蹤從每個節點可以到達的節點數量。

  • 建立一個空的集合來記錄已訪問的節點。

  • 建立的變數的初始值應為圖中的節點總數。

  • 迭代遍歷圖中的每個節點

    初始化一個變數來計算從當前節點可以到達的節點數，並將其設定為1（節點本身）。a. 如果當前節點未被訪問：i。

    從當前節點進行深度優先搜尋（DFS）或廣度優先搜尋（BFS）遍歷。

    在遍歷時標記已訪問的節點並增加每個已訪問節點的計數。

  • 對於每個節點，使用可到達的節點數來更新列表或陣列。

  • 重複步驟5，直到訪問所有節點。

  • 現在，列表或陣列包含圖中從每個節點可以到達的節點數。

  • 最後一步是返回包含各個節點中可用節點數的列表，該列表可以作為輸出執行。

示例

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int countConnectedComponents(vector<vector<int>>& graph) {
    int N = graph.size();
    vector<bool> visited(N, false);
    int count = 0;
    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            dfs(i, graph, visited);
            count++;
        }
    }
    return count;
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},   
        {0, 2},   
        {0, 1},   
        {4},      
        {3},      
        {}        
    };

    int connectedComponents = countConnectedComponents(graph);
    cout << "Number of connected components: " << connectedComponents << endl;

    return 0;
}

輸出

Number of connected components: 3

結論

總之，圖中從所有其他節點可到達的節點數量是網路中連線性和可達性的關鍵指標。為了有效地計算此計數，Floyd-Warshall演算法、可達性矩陣和連通分量是至關重要的工具。Floyd-Warshall演算法修改了傳統方法，以估計從每個節點可以到達多少個節點。可達性矩陣表示圖的可達性資訊，使我們能夠確定從每個節點可以到達哪些節點。最後，識別連通分量使計算單個元件內可到達的節點變得更容易。理解此計數對於評估各種網路系統（包括計算機網路、社交網路和交通網路）中資訊流的效率至關重要。

更新於：2023年8月2日

415 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始
廣告