C++ 从图中的所有其他节点可以访问的节点数

从图中的任何特定节点可以到达的节点数称为从图中的所有其他节点可访问的节点数。它显示了图中的可达性和连通性程度。我们从每个节点开始，探索到其他节点的所有可访问路径，以获取此计数。我们在遍历图时记录访问的节点。图中可到达的节点数量包括所有可到达的节点。这对于理解网络关系和信息流效率至关重要。

使用的方法

可达性矩阵
连接组件

可达性矩阵

使用可达性矩阵来统计图中的可达节点，可达性矩阵是一个方阵。矩阵的[i][j]项表示节点j是否可以从节点i到达。通过检查矩阵的行，可以确定网络中每个节点可以到达的节点。每行中的“1”的数目表示从给定节点可以到达的节点数，提供了关于图的一般连通性和可达性的信息。这个矩阵有助于理解图中节点之间的关联性和关系，提供了关于节点在图中的可访问程度的有用见解。

步骤

将n视为图G中节点的总数。
创建一个名为ReachabilityMatrix的二维数组，大小为n×n，并初始化为零。
对于每个节点i，从0到n−1：

开始深度优先搜索（DFS）或广度优先搜索（BFS）从节点i。

将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技术改变了传统技术。图的可达性信息由可达性矩阵表示，让我们能够确定每个节点可从哪些节点到达。最后，识别连通分量可以更容易地计算在单个分量内可访问的节点数。理解这个数量对于评估各种网络系统（包括计算机网络、社交网络和交通网络）中信息流的有效性至关重要。