如何为图中的边实现优先级队列？

Question

我想使用简单的方法在 C# 中实现我自己的优先级队列。我需要对图中的边使用 PQ 来实现 Prims 算法。这是我到目前为止所做的：

public class Edge
        {
            private int v;         // one vertex
            private int w;         // the other vertex
            private int weight;    // edge weight

            public Edge(int v0, int w0, int weight0)
              {
                  v = v0;
                  w = w0;
                  weight = weight0;
              }

           public Edge()
            {
                v = 0;
                w = 0;
                weight = 0;
            } 

            public int get_weight()
            {
                return weight;
            }

            public int either()
            {
                return v;
            }

            public int the_other(int vertex)
            {
                if (vertex == v) return w;
                else return v;
            }

            public int compareTo(Edge that)
            {
                if (this.get_weight() < that.get_weight()) return -1;
                if (this.get_weight() < that.get_weight()) return 1;
                else return 0;
            }

            public string to_str()
            {
                string s = v.ToString() + " " + weight.ToString() + " " + w.ToString() + '\n';
                return s;
            }
        }

 public class MyPriorityQueue_Edge
        {
            private List<Edge> q = new List<Edge>();
            int size;
            public MyPriorityQueue_Edge() 
            {
                size = 0;
            }

            public void insert(Edge e)
            {
                q.Add(e);
                size++;
            }

            Edge Min()
            {
                int min_weight = 1000;
                Edge min_edge = new Edge();
                foreach(Edge e in q)
                    if(e.get_weight()< min_weight)
                        min_edge = e;
                return min_edge;
            }

            public Edge delmin()
            {
                Edge e  = q.Min();
                q.Remove(e);
                size--;
                return e;
            }

          public bool is_empty()
            {
                if (size == 0) return true;
                else return false;
            }
        }

当我编译它时，编译器指向这一行：

Edge e  = q.Min();

并说我没有处理异常 "System.Argument.Exception"。我该如何解决这个问题？

Answer 1

来自 MSDN Enumerable.Min<TSource> Method (IEnumerable<TSource>)

If type TSource implements IComparable<T>, this method uses that implementation to compare values. Otherwise, if type TSource implements IComparable, that implementation is used to compare values.

您需要在 Edge class 中实现 IComparable 接口。

public class Edge : IComparable

然后添加一个 CompareTo() 方法。像

public int CompareTo(object obj)
{
    if (obj is Edge)
    {
        Edge other = (Edge)obj;
        return this.compareTo(other); // you already implemented this in your Edge class
    }
    else
    {
        throw new InvalidOperationException();
    }
}

如何为图中的边实现优先级队列？

How cna I implement a priority queue for edges in a graph?

c#

implementation

graph

priority-queue