广度优先算法代码示例

简介: 广度优先算法代码示例

广度优先算法代码示例:

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;
    }
}

注释很详细!

目录
打赏
0
0
0
0
25
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
138 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
101 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
68 3
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
本研究基于MATLAB 2022a,使用GRU网络对QAM调制信号进行检测。QAM是一种高效调制技术,广泛应用于现代通信系统。传统方法在复杂环境下性能下降,而GRU通过门控机制有效提取时间序列特征,实现16QAM、32QAM、64QAM、128QAM的准确检测。仿真结果显示,GRU在低SNR下表现优异,且训练速度快,参数少。核心程序包括模型预测、误检率和漏检率计算,并绘制准确率图。
77 65
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等