C# 宽度优先遍历 最短路径 代码

宽度优先遍历（Breadth-First Search，简称BFS）是一种用于图论中搜索所有节点或者找到最短路径的算法。在C#中，可以使用队列数据结构来实现宽度优先遍历。如果目标是寻找最短路径，比如在无权图或有权图中寻找两点之间的最短距离，BFS通常是最合适的选择，因为它总是先探索离起点最近的节点。

下面是一个简单的C#代码示例，展示了如何使用BFS计算无权图中最短路径：

using System;
using System.Collections.Generic;

class Node {
    public int Value { get; set; }
    public List<Node> Neighbors { get; set; }

    // Constructor and other methods...
}

public class ShortestPath BFSShortestPath(Node startNode, Node endNode) {
    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(startNode);
    startNode.Dist = 0; // 初始化起始点的距离为0

    while (queue.Count > 0) {
        Node current = queue.Dequeue();
        foreach (Node neighbor in current.Neighbors) {
            if (neighbor.Dist == -1) { // 如果邻居还没访问过
                neighbor.Dist = current.Dist + 1; // 更新邻居的距离
                queue.Enqueue(neighbor); // 将邻居加入队列
            }
        }
        if (current == endNode) { // 找到了终点
            break;
        }
    }

    return endNode.Dist != -1 ? endNode.Dist : null; // 返回最短距离，若未到达则返回null
}

在这个例子中，`Node`类代表图中的一个顶点，包含值和邻接列表。`BFSShortestPath`函数使用队列存储待访问的节点，并在每个步骤中检查是否有到达终点的路径。