C#如何基于邻接矩阵实现字符串类型顶点的BFS与DFS算法

核心思路 #

首先解决邻接矩阵依赖整数下标的问题，增加两层映射做转换即可，BFS、DFS的核心遍历逻辑和整数顶点场景完全一致：

• 初始化时建立字符串顶点名→整数下标的哈希映射，同时维护整数下标→字符串顶点名的反向数组，用于遍历结果还原
• 邻接矩阵大小等于顶点总数，matrix[i][j]存储下标i对应顶点到下标j对应顶点的连通状态
• 输入起始顶点时先转成对应下标，遍历输出时再通过反向数组转回字符串名称即可

注意：初始化顶点列表时需要提前去重，避免哈希映射冲突。

完整代码实现（C++） #

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
using namespace std;

class StringGraph {
private:
    unordered_map<string, int> name2idx;
    vector<string> idx2name;
    vector<vector<int>> adjMatrix;
    int vertexCount;

    // DFS递归辅助函数
    void dfsInner(int currIdx, vector<bool>& visited) {
        visited[currIdx] = true;
        cout << idx2name[currIdx] << " ";
        for (int nextIdx = 0; nextIdx < vertexCount; nextIdx++) {
            if (adjMatrix[currIdx][nextIdx] == 1 && !visited[nextIdx]) {
                dfsInner(nextIdx, visited);
            }
        }
    }

public:
    // 构造函数：传入所有字符串顶点初始化
    StringGraph(vector<string> vertices) {
        vertexCount = vertices.size();
        idx2name = vertices;
        for (int i = 0; i < vertexCount; i++) {
            name2idx[vertices[i]] = i;
        }
        adjMatrix.resize(vertexCount, vector<int>(vertexCount, 0));
    }

    // 添加边，默认无向图
    void addEdge(string fromVertex, string toVertex, bool isDirected = false) {
        int fromIdx = name2idx[fromVertex];
        int toIdx = name2idx[toVertex];
        adjMatrix[fromIdx][toIdx] = 1;
        if (!isDirected) {
            adjMatrix[toIdx][fromIdx] = 1;
        }
    }

    // BFS广度优先遍历
    void bfs(string startVertex) {
        vector<bool> visited(vertexCount, false);
        queue<int> q;
        int startIdx = name2idx[startVertex];
        q.push(startIdx);
        visited[startIdx] = true;

        while (!q.empty()) {
            int currIdx = q.front();
            q.pop();
            cout << idx2name[currIdx] << " ";

            for (int nextIdx = 0; nextIdx < vertexCount; nextIdx++) {
                if (adjMatrix[currIdx][nextIdx] == 1 && !visited[nextIdx]) {
                    visited[nextIdx] = true;
                    q.push(nextIdx);
                }
            }
        }
        cout << endl;
    }

    // 递归版本DFS深度优先遍历
    void dfsRecursive(string startVertex) {
        vector<bool> visited(vertexCount, false);
        dfsInner(name2idx[startVertex], visited);
        cout << endl;
    }

    // 迭代版本DFS深度优先遍历
    void dfsIterative(string startVertex) {
        vector<bool> visited(vertexCount, false);
        stack<int> stk;
        int startIdx = name2idx[startVertex];
        stk.push(startIdx);
        visited[startIdx] = true;

        while (!stk.empty()) {
            int currIdx = stk.top();
            stk.pop();
            cout << idx2name[currIdx] << " ";

            // 倒序遍历保证和递归遍历顺序一致，无需一致可直接正序遍历
            for (int nextIdx = vertexCount - 1; nextIdx >= 0; nextIdx--) {
                if (adjMatrix[currIdx][nextIdx] == 1 && !visited[nextIdx]) {
                    visited[nextIdx] = true;
                    stk.push(nextIdx);
                }
            }
        }
        cout << endl;
    }
};

测试示例 #

int main() {
    // 顶点为城市名称的测试用例
    vector<string> cities = {"Beijing", "Shanghai", "Guangzhou", "Shenzhen", "Chengdu"};
    StringGraph graph(cities);
    // 添加城市间连通边
    graph.addEdge("Beijing", "Shanghai");
    graph.addEdge("Beijing", "Chengdu");
    graph.addEdge("Shanghai", "Guangzhou");
    graph.addEdge("Guangzhou", "Shenzhen");
    graph.addEdge("Chengdu", "Shenzhen");

    cout << "BFS遍历（起点Beijing）：";
    graph.bfs("Beijing");
    cout << "递归DFS遍历（起点Beijing）：";
    graph.dfsRecursive("Beijing");
    cout << "迭代DFS遍历（起点Beijing）：";
    graph.dfsIterative("Beijing");
    return 0;
}

输出结果 #

BFS遍历（起点Beijing）：Beijing Shanghai Chengdu Guangzhou Shenzhen 
递归DFS遍历（起点Beijing）：Beijing Shanghai Guangzhou Shenzhen Chengdu 
迭代DFS遍历（起点Beijing）：Beijing Shanghai Guangzhou Shenzhen Chengdu 

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