广度优先算法代码示例

using System;
using System.Collections.Generic;
public class DijkstraAlgorithm
{
    // Dijkstra算法主要逻辑
    public static void Dijkstra(Dictionary<int, List<Edge>> graph, int startNode, int endNode)
    {
        // 存储节点到起点的距离
        Dictionary<int, int> distances = new Dictionary<int, int>();
        // 存储节点的父节点，用于构建最短路径
        Dictionary<int, int> parents = new Dictionary<int, int>();
        // 优先队列，用于按照节点距离从小到大的顺序处理
        PriorityQueue priorityQueue = new PriorityQueue();
        // 初始化distances和parents字典
        foreach (int node in graph.Keys)
        {
            distances[node] = int.MaxValue; // 将所有节点的距离初始化为无穷大
            parents[node] = -1; // 将所有节点的父节点初始化为-1
        }
        distances[startNode] = 0; // 将起始节点的距离设置为0
        priorityQueue.Enqueue(new Node(startNode, 0)); // 将起始节点加入优先队列
        // 开始执行Dijkstra算法
        while (priorityQueue.Count > 0) // 当优先队列不为空时
        {
            Node currentNode = priorityQueue.Dequeue();
            
            // 如果当前节点的距离值大于distances中对应节点的距离值，说明当前节点已经被处理过，直接跳过
            if (currentNode.Value > distances[currentNode.Vertex])
                continue;
            // 对当前节点的所有相邻边进行遍历
            foreach (Edge edge in graph[currentNode.Vertex])
            {
                // 计算从起始节点经过当前节点到目标节点的新距离
                int newDistance = distances[currentNode.Vertex] + edge.Weight;
                // 如果新距离小于distances中对应节点的距离值
                if (newDistance < distances[edge.Destination])
                {
                    distances[edge.Destination] = newDistance; // 更新目标节点的距离值
                    parents[edge.Destination] = currentNode.Vertex; // 更新目标节点的父节点
                    priorityQueue.Enqueue(new Node(edge.Destination, newDistance)); // 将目标节点加入优先队列
                }
            }
        }
        // 判断是否存在从起点到终点的路径
        if (distances[endNode] == int.MaxValue)
        {
            Console.WriteLine("There is no path from startNode to endNode.");
        }
        else
        {
            // 获取最短路径
            List<int> shortestPath = GetShortestPath(parents, startNode, endNode);
            Console.WriteLine($"Shortest distance from {startNode} to {endNode}: {distances[endNode]}");
            Console.WriteLine("Shortest path: " + string.Join(" -> ", shortestPath));
        }
    }
    // 构建最短路径
    public static List<int> GetShortestPath(Dictionary<int, int> parents, int startNode, int endNode)
    {
        List<int> path = new List<int>();
        int currentNode = endNode;
        while (currentNode != -1)
        {
            path.Insert(0, currentNode); // 将节点插入到路径列表的开头
            currentNode = parents[currentNode]; // 更新当前节点为父节点
        }
        return path;
    }
    public static void Main(string[] args)
    {
        Dictionary<int, List<Edge>> graph = new Dictionary<int, List<Edge>>();
        // 创建图形
        // 每个键表示一个节点，每个值表示与该节点相连的所有边
        graph[0] = new List<Edge>
        {
            new Edge(1, 2),
            new Edge(2, 5),
            new Edge(3, 9)
        };
        graph[1] = new List<Edge>
        {
            new Edge(4, 12)
        };
        graph[2] = new List<Edge>
        {
            new Edge(4, 5),
            new Edge(5, 6)
        };
        graph[3] = new List<Edge>
        {
            new Edge(5, 10)
        };
        graph[4] = new List<Edge>
        {
            new Edge(6, 6)
        };
        graph[5] = new List<Edge>
        {
            new Edge(6, 5),
            new Edge(7, 4)
        };
        graph[6] = new List<Edge>
        {
            new Edge(8, 8)
        };
        graph[7] = new List<Edge>
        {
            new Edge(8, 5),
            new Edge(9, 7)
        };
        graph[8] = new List<Edge>
        {
            new Edge(9, 8)
        };
        graph[9] = new List<Edge>();
        int startNode = 0;
        int endNode = 9;
        // 执行Dijkstra算法
        Dijkstra(graph, startNode, endNode);
    }
}
// 边类，表示节点之间的连接关系
public class Edge
{
    public int Destination { get; } // 目标节点
    public int Weight { get; } // 边的权重
    public Edge(int destination, int weight)
    {
        Destination = destination;
        Weight = weight;
    }
}
// 节点类，包含节点编号和距离值
public class Node
{
    public int Vertex { get; } // 节点编号
    public int Value { get; } // 节点距离值
    public Node(int vertex, int value)
    {
        Vertex = vertex;
        Value = value;
    }
}
// 优先队列类，用于保存节点，并确保按照节点的距离值从小到大排序
public class PriorityQueue
{
    private List<Node> heap; // 存放节点的列表
    public int Count => heap.Count;
    public PriorityQueue()
    {
        heap = new List<Node>();
    }
    // 入队操作，将节点加入优先队列并保持有序
    public void Enqueue(Node item)
    {
        heap.Add(item);
        int currentIndex = heap.Count - 1;
        while (currentIndex > 0)
        {
            int parentIndex = (currentIndex - 1) / 2;
            if (heap[currentIndex].Value >= heap[parentIndex].Value)
                break;
            Swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
        }
    }
    // 出队操作，取出距离值最小的节点
    public Node Dequeue()
    {
        if (Count == 0)
            throw new InvalidOperationException("PriorityQueue is empty.");
        Node item = heap[0];
        heap[0] = heap[Count - 1];
        heap.RemoveAt(Count - 1);
        int currentIndex = 0;
        while (currentIndex < Count)
        {
            int leftChildIndex = 2 * currentIndex + 1;
            int rightChildIndex = 2 * currentIndex + 2;
            if (leftChildIndex >= Count)
                break;
            int smallerChildIndex = leftChildIndex;
            if (rightChildIndex < Count && heap[rightChildIndex].Value < heap[leftChildIndex].Value)
                smallerChildIndex = rightChildIndex;
            if (heap[currentIndex].Value <= heap[smallerChildIndex].Value)
                break;
            Swap(currentIndex, smallerChildIndex);
            currentIndex = smallerChildIndex;
        }
        return item;
    }
    // 交换两个位置的节点
    private void Swap(int index1, int index2)
    {
        Node temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}