时间戳

首页 > 解决方案 > 检查链表是否> 包含某个节点

c# - 检查链表是否> 包含某个节点

问题描述

我正在使用 c# 实现一个 Graph 并且我想检查我是否两次插入了相同的边缘，以便我可以在这样做时抛出异常。

我的班级名称是 Graph

这是我的 _adjacencyList 声明

 protected virtual Dictionary<T, LinkedList<Node<T>>> _adjacencyList { get; set; }

这是我的节点类

 class Node<T> where T : IComparable<T>
{
    public double speed { get; set; }
    public double time { get; set; }
    public double distance { get; set; }
    public T source { get; set; }
    public T destenation { get; set; }

    public Node() { }
    public Node(T SOURCE, T DESTENATION, double SPEED, double DISTANCE)
    {
        this.source = SOURCE;
        this.destenation = DESTENATION;
        this.speed = SPEED;
        this.distance = DISTANCE;
        this.time = this.distance / this.speed;
    }
}

这是我的 addEdge 函数，它采用源顶点和目标顶点以及边缘的值“权重”

public void addEdge(T source, T Destenation, double speed, double Distance)
    {
        if (_adjacencyList.Count <= 0)
        {
            throw new InvalidOperationException("addEdge: There are no Vertices in Graph.\n");
        }
        else
        {
            if (_adjacencyList.ContainsKey(source) && _adjacencyList.ContainsKey(Destenation))
            {
                var sourceEdge = new Node<T>(source, Destenation, speed, Distance);
                var destenationEdge = new Node<T>(Destenation, source, speed, Distance);

                if (_adjacencyList[source].Contains(sourceEdge) || _adjacencyList[Destenation].Contains(destenationEdge))
                {
                    throw new InvalidOperationException("addEdge: Edge already exists in Graph.\n");
                }
                else
                {
                    _adjacencyList[source].AddLast(sourceEdge);
                    _adjacencyList[Destenation].AddLast(destenationEdge);

                    ++_edgeCount;
                }


            }
            else
            {
                throw new NullReferenceException("addEdge : Source or Destenation Vetrtex Don't Exist in Graph.\n");
            }
        }

    }

当我在 main 中编写此代码时，它不会抛出“Edge 已存在于 Graph 中”的异常。

   Graph<int> g = new Graph<int>();
        g.addVertex(1);
        g.addVertex(2);
        g.addVertex(3);
        g.addVertex(4);
        g.addEdge(1,2,15.0,60.0);//Multiple Edge
        g.addEdge(1, 2, 15.0, 60.0);//Multiple Edge
        g.addEdge(1, 3, 5.0, 40.0);
        g.addEdge(2,3,1.0,10.0);
        g.addEdge(4,1,2.0,8.0);

我的实施有什么问题以及如何解决？

标签： c#graphlinked-list

解决方案

发生这种情况是因为您忘记覆盖Equalsclass 的方法Node。

您需要以下实现：

public class Edge<T> 
{
    public double Speed { get; }
    public double Time { get; }
    public double Distance { get; }
    public T Source { get; }
    public T Destination { get; }

    public Edge(T source, T destination, double speed, double distance)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        if (destination == null) throw new ArgumentNullException(nameof(destination));
        if (Math.Abs(speed) < 1E-9) throw new ArgumentException("speed must greater than zero", nameof(speed));
        if (Math.Abs(distance) < 1E-9) throw new ArgumentException("distance must greater than zero", nameof(speed));

        Source = source;
        Destination = destination;
        Speed = speed;
        Distance = distance;
        Time = Distance / Speed;
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Edge<T> objAsEdgeT))
        {
            return false;
        }

        return Math.Abs(Speed - objAsNodeT.Speed) < 1E-9
               && Math.Abs(Time - objAsNodeT.Time) < 1E-9
               && Source.Equals(objAsNodeT.Source)
               && Destination.Equals(objAsNodeT.Destination);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 13;
            hash = (hash*7) + Speed.GetHashCode();
            hash = (hash*7) + Time.GetHashCode();
            hash = (hash*7) + Source.GetHashCode();
            hash = (hash*7) + Destination.GetHashCode();
            return hash;
        }
    }
}

一些注意事项：

  • 命名至关重要。类Node本质上代表一条边。所以这Edge将是一个更合适的类名。反过来想想，对于一个人来说，阅读并真正理解一段与图节点相关的代码会有多困难，而我们选择的名称是边。
  • 尝试使用常见的编码样式，以使您的代码更具可读性。例如，对于我们使用Pascal Case的属性。
  • 在这种情况下，您不需要公共设置器。
  • 您不需要默认构造函数。有人打电话是什么意思new Edge<int>()？更不用说你会得到一个例外，因为所有属性都会获得相应的默认值（双 -> 0），并且除法距离/速度将导致除法为零......
  • 在构造函数内部，我们必须验证我们得到的值是否有意义。否则，我们最多只会有一个处于无意义状态的对象。没有节点我们就没有边！因此null对于源和目标都不是有效值。此外distance，并且speed应该大于零。即使speed有一些意义，和的划分distance也speed将毫无意义——更不用说例外了……

推荐阅读