无向图中从指定节点获取所有可达节点的算法实现

问题说明 #

作为图论新手，需求是：给定任意无向图，从随机指定的节点出发，找出所有可访问的节点。以如下邻接矩阵为例：

期望得到的结果是：从A/D/E出发，可达节点为{A,D,E}；从B/C出发，可达节点为{B,C}。

数学形式说明 #

无向图的连通分量是图的一个子图，其中任意两个节点之间都存在路径，且子图外的节点与子图内节点无路径相连。

对于无向图 ( G=(V,E) )，其中 ( V ) 是节点集合，( E ) 是边集合：

1. 定义节点间的可达关系：若存在路径 ( v_0 \to v_1 \to ... \to v_k )（其中 ( v_0 = u, v_k = v )，且每条 ( (v_i, v_{i+1}) \in E )），则称 ( u ) 可达 ( v )，记作 ( u \sim v )。
2. 可达关系是等价关系（满足自反性、对称性、传递性），每个等价类对应一个连通分量。
3. 从节点 ( s ) 出发的所有可达节点，就是 ( s ) 所在的等价类（连通分量）。

代码实现 #

Python 实现（基于DFS） #

def find_reachable_nodes(adj_matrix, start_node, node_names):
    node_index = node_names.index(start_node)
    visited = [False] * len(adj_matrix)
    reachable = []
    
    def dfs(index):
        if visited[index]:
            return
        visited[index] = True
        reachable.append(node_names[index])
        for i in range(len(adj_matrix[index])):
            if adj_matrix[index][i] == 1 and not visited[i]:
                dfs(i)
    
    dfs(node_index)
    return reachable

# 示例使用
adj_matrix = [
    [0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 0, 1, 0]
]
node_names = ['A', 'B', 'C', 'D', 'E']

print(find_reachable_nodes(adj_matrix, 'A', node_names))  # 输出: ['A', 'D', 'E']
print(find_reachable_nodes(adj_matrix, 'B', node_names))  # 输出: ['B', 'C']

C# 实现（基于BFS） #

using System;
using System.Collections.Generic;

class GraphReachability
{
    static List<char> FindReachableNodes(int[,] adjMatrix, char startNode, char[] nodeNames)
    {
        int startIndex = Array.IndexOf(nodeNames, startNode);
        bool[] visited = new bool[nodeNames.Length];
        List<char> reachable = new List<char>();
        Queue<int> queue = new Queue<int>();

        visited[startIndex] = true;
        queue.Enqueue(startIndex);

        while (queue.Count > 0)
        {
            int current = queue.Dequeue();
            reachable.Add(nodeNames[current]);

            for (int i = 0; i < nodeNames.Length; i++)
            {
                if (adjMatrix[current, i] == 1 && !visited[i])
                {
                    visited[i] = true;
                    queue.Enqueue(i);
                }
            }
        }

        return reachable;
    }

    static void Main()
    {
        int[,] adjMatrix = {
            {0, 0, 0, 1, 0},
            {0, 0, 1, 0, 0},
            {0, 1, 0, 0, 0},
            {1, 0, 0, 0, 1},
            {0, 0, 0, 1, 0}
        };
        char[] nodeNames = {'A', 'B', 'C', 'D', 'E'};

        List<char> reachableFromA = FindReachableNodes(adjMatrix, 'A', nodeNames);
        Console.WriteLine(string.Join(", ", reachableFromA));  // 输出: A, D, E

        List<char> reachableFromB = FindReachableNodes(adjMatrix, 'B', nodeNames);
        Console.WriteLine(string.Join(", ", reachableFromB));  // 输出: B, C
    }
}

C++ 实现（基于DFS） #

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void dfs(int index, const vector<vector<int>>& adj_matrix, vector<bool>& visited, vector<char>& reachable, const vector<char>& node_names) {
    if (visited[index]) return;
    visited[index] = true;
    reachable.push_back(node_names[index]);
    for (int i = 0; i < adj_matrix[index].size(); ++i) {
        if (adj_matrix[index][i] == 1 && !visited[i]) {
            dfs(i, adj_matrix, visited, reachable, node_names);
        }
    }
}

vector<char> find_reachable_nodes(const vector<vector<int>>& adj_matrix, char start_node, const vector<char>& node_names) {
    auto it = find(node_names.begin(), node_names.end(), start_node);
    int start_index = it - node_names.begin();
    vector<bool> visited(node_names.size(), false);
    vector<char> reachable;
    dfs(start_index, adj_matrix, visited, reachable, node_names);
    return reachable;
}

int main() {
    vector<vector<int>> adj_matrix = {
        {0, 0, 0, 1, 0},
        {0, 0, 1, 0, 0},
        {0, 1, 0, 0, 0},
        {1, 0, 0, 0, 1},
        {0, 0, 0, 1, 0}
    };
    vector<char> node_names = {'A', 'B', 'C', 'D', 'E'};

    vector<char> reachableA = find_reachable_nodes(adj_matrix, 'A', node_names);
    for (char c : reachableA) cout << c << " ";  // 输出: A D E
    cout << endl;

    vector<char> reachableB = find_reachable_nodes(adj_matrix, 'B', node_names);
    for (char c : reachableB) cout << c << " ";  // 输出: B C
    cout << endl;

    return 0;
}

JavaScript 实现（基于BFS） #

function findReachableNodes(adjMatrix, startNode, nodeNames) {
    const startIndex = nodeNames.indexOf(startNode);
    const visited = new Array(nodeNames.length).fill(false);
    const reachable = [];
    const queue = [startIndex];

    visited[startIndex] = true;

    while (queue.length > 0) {
        const current = queue.shift();
        reachable.push(nodeNames[current]);

        for (let i = 0; i < adjMatrix[current].length; i++) {
            if (adjMatrix[current][i] === 1 && !visited[i]) {
                visited[i] = true;
                queue.push(i);
            }
        }
    }

    return reachable;
}

// 示例使用
const adjMatrix = [
    [0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 0, 1, 0]
];
const nodeNames = ['A', 'B', 'C', 'D', 'E'];

console.log(findReachableNodes(adjMatrix, 'A', nodeNames));  // 输出: ['A', 'D', 'E']
console.log(findReachableNodes(adjMatrix, 'B', nodeNames));  // 输出: ['B', 'C']

内容的提问来源于stack exchange，提问作者Domo48x