C# 无向图寻路：广度优先搜索 (BFS) 算法寻找最短路径

可以使用广度优先搜索算法（BFS）来寻找无向图中的最短路径。BFS从起始节点开始，依次遍历其相邻节点，将它们加入队列中，并标记为已访问。然后对队列中的下一个节点进行相同的操作，直到找到目标节点或者遍历完所有节点。

在BFS过程中，可以使用一个数组（如dist）来记录每个节点与起始节点的距离，初始值为无穷大。当遍历到一个节点时，如果它的距离比之前计算的距离更短，就更新dist数组。最后dist数组中的值就是起始节点到各个节点的最短距离。

代码示例：

using System;
using System.Collections.Generic;

class Graph {
    private int V; //节点数
    private List<int>[] adj; //邻接表

    public Graph(int v) {
        V = v;
        adj = new List<int>[V];
        for(int i=0; i<V; i++) {
            adj[i] = new List<int>();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    public void BFS(int s, int t) {
        bool[] visited = new bool[V];
        int[] dist = new int[V];
        int[] prev = new int[V];
        for(int i=0; i<V; i++) {
            dist[i] = int.MaxValue;
        }
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(s);
        visited[s] = true;
        dist[s] = 0;
        while(queue.Count != 0) {
            int v = queue.Dequeue();
            foreach(int i in adj[v]) {
                if(!visited[i]) {
                    dist[i] = dist[v] + 1;
                    prev[i] = v;
                    if(i == t) { //找到目标节点
                        printPath(prev, s, t);
                        return;
                    }
                    visited[i] = true;
                    queue.Enqueue(i);
                }
            }
        }
    }

    private void printPath(int[] prev, int s, int t) {
        if(prev[t] != 0 && t != s) {
            printPath(prev, s, prev[t]);
        }
        Console.Write(t + " ");
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.BFS(0, 4);
    }
}

输出结果为：0 1 3 4