在这篇文章中,我将介绍 .NET 9(.NET 8 的继任者)中引入的最新集合功能。
.NET 中的图形算法刚刚变得很酷! .NET 9 为该类引入了一个新功能:方法。这一新增功能使得使用优先级队列变得更加容易,这对于解决寻路问题和图形遍历(例如 Dijkstra 算法的变体)的软件工程师来说是个好消息。PriorityQueue<TElement, TPriority>Remove(TElement, TElement, TPriority, IEqualityComparer<TElement>)
想象一下,人们不只是在等待轮到他们,而是根据他们的重要性来安排。这就是优先级队列的基本思想。优先级较高的人可以更快地到达队伍的最前面,这使他们非常适合像 Dijkstra 的最短路径算法这样的算法。
然而,传统的优先队列有一个问题:很难改变已经排队的人的重要性。这可能会使使用某些图形算法变得棘手。
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
// Create a priority queue of strings with int priorities
PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
// Enqueue elements with priority
priorityQueue.Enqueue("Niraj", 2); // John has priority 2
priorityQueue.Enqueue("Alice", 1); // Alice has priority 1
priorityQueue.Enqueue("Emily", 3); // Emily has priority 3
priorityQueue.Enqueue("David", 4); // David has priority 4
// Dequeue elements (sorted by priority)
Console.WriteLine("People are being served according to their priority:");
while (priorityQueue.Count > 0)
{
var person = priorityQueue.Dequeue();
Console.WriteLine($"Serving {person}");
}
}
}
在这里,创建了一个优先级队列来保存人们的姓名以及他们各自的优先级。元素将按其分配的优先级排入优先级队列。然后,程序遍历队列,逐个对元素进行排队并将它们打印到控制台。
一般来说,数组堆的一个问题是它们不支持优先级更新,这使得它们在算法(例如 Dijkstra 算法的变体)中使用时令人望而却步。
.NET 9 为类中的方法带来了一个新选项。此方法采用四个参数:RemovePriorityQueue
其工作原理如下:
using System;
using System.Collections.Generic;
using System.Xml.Linq;
class Program
{
static void Main(string[] args)
{
// Create a priority queue of strings with int priorities
PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
// Enqueue elements with priority
priorityQueue.Enqueue("Niraj", 2); // John has priority 2
priorityQueue.Enqueue("Alice", 1); // Alice has priority 1
priorityQueue.Enqueue("Emily", 3); // Emily has priority 3
priorityQueue.Enqueue("David", 4); // David has priority 4
priorityQueue.Enqueue("John", 2); // John has priority 2
// removing the element - "Alice" from priority queue
priorityQueue.Remove("Alice", out _, out _);
// removing the element - "Alice" from priority queue
string removedElement;
int priority;
priorityQueue.Remove("John", out removedElement, out priority);
Console.WriteLine($"Person {removedElement} which had a priority {priority} was removed from the queue.");
// Dequeue elements (sorted by priority)
Console.WriteLine("People are being served according to their priority:");
while (priorityQueue.Count > 0)
{
var person = priorityQueue.Dequeue();
Console.WriteLine($"Serving {person}");
}
}
}
在此示例中,元素以其分配的优先级排队到优先级队列中,然后使用该方法从队列中删除 2 个元素。最后,程序遍历队列,逐个对元素进行排队并将它们打印到控制台。Remove
IGraph 接口:
public interface IGraph<TNode>
{
IEnumerable<TNode> GetNeighbors(TNode node);
int GetEdgeWeight(TNode source, TNode target);
}
此接口定义了表示图形所需的基本功能:
SampleGraph 类:
public class SampleGraph : IGraph<string>
{
private readonly Dictionary<string, List<KeyValuePair<string, int>>> edges = new Dictionary<string, List<KeyValuePair<string, int>>>();
public SampleGraph()
{
// Add edges and their weights to the dictionary here
edges.Add("A", new List<KeyValuePair<string, int>>() { new KeyValuePair<string, int>("B", 4), new KeyValuePair<string, int>("C", 2) });
edges.Add("B", new List<KeyValuePair<string, int>>() { new KeyValuePair<string, int>("D", 2), new KeyValuePair<string, int>("E", 3) });
edges.Add("C", new List<KeyValuePair<string, int>>() { new KeyValuePair<string, int>("D", 5) });
edges.Add("D", new List<KeyValuePair<string, int>>() { new KeyValuePair<string, int>("E", 1) });
}
public IEnumerable<string> GetNeighbors(string node)
{
if (!edges.ContainsKey(node))
{
return Enumerable.Empty<string>();
}
return edges[node].Select(x => x.Key);
}
public int GetEdgeWeight(string source, string target)
{
if (!edges.ContainsKey(source) || !edges[source].Any(x => x.Key == target))
{
throw new ArgumentException("Edge not found in the graph");
}
return edges[source].First(x => x.Key == target).Value;
}
}
此类实现简单内存中图的接口。IGraph
DijkstraWithPriorityQueue 类:
public static class DijkstraWithPriorityQueue
{
public static Dictionary<TNode, int> FindShortestPaths<TNode>(
IGraph<TNode> graph, TNode startNode)
{
var distances = new Dictionary<TNode, int>();
distances[startNode] = 0;
var priorityQueue = new PriorityQueue<TNode, int>();
priorityQueue.Enqueue(startNode, 0);
while (priorityQueue.TryDequeue(out TNode currentNode, out int currentDistance))
{
foreach (var neighbor in graph.GetNeighbors(currentNode))
{
var edgeWeight = graph.GetEdgeWeight(currentNode, neighbor);
var tentativeDistance = currentDistance + edgeWeight;
// Check if relaxation is needed
if (!distances.ContainsKey(neighbor) || tentativeDistance < distances[neighbor])
{
distances[neighbor] = tentativeDistance;
// Simulate priority update using Remove and Enqueue
priorityQueue.Remove(neighbor, out _, out _);
priorityQueue.Enqueue(neighbor, tentativeDistance);
}
}
}
return distances;
}
}
此类使用优先级队列实现 Dijkstra 的最短路径算法。
课程类别:
public class Program
{
public static void Main(string[] args)
{
var graph = new SampleGraph();
var startNode = "A";
var shortestDistances = DijkstraWithPriorityQueue.FindShortestPaths(graph, startNode);
Console.WriteLine("Shortest distances from {0}:", startNode);
foreach (var node in shortestDistances)
{
Console.WriteLine("{0}: {1}", node.Key, node.Value);
}
}
}
此类是程序的入口点。
总的来说,这段代码演示了如何使用类中的新方法(尽管用于模拟更新)来实现 Dijkstra 的算法并找到图中的最短路径。RemovePriorityQueue
新方法提供以下功能:Remove
.NET 9 引入了令人兴奋的新功能和改进,旨在满足软件工程师不断变化的需求。若要详细了解 .NET 9 中的新功能和增强功能,请查看官方文档,并继续关注未来的更新。