检查链表<节点<T>>是否包含某个节点

Question

我正在使用 c# 实现一个图形，我想检查我是否插入了两次相同的边缘，以便我可以在执行此操作时抛出异常。

我的类名是图形

这是我的_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);

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

Answer 1

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

您需要类似于以下实现的内容：

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的划分也是没有意义的——更不用说例外了......

Answer 2

原因确实是因为您没有为类 Node 实现 Equals 方法，我在这里也解释原因。

为了理解为什么需要 Equals 方法，您需要了解 LinkedList 类的工作原理，这非常简单，您只需添加并稍后删除其中 Node 类型的对象即可。到目前为止一切顺利，但是当您在此代码块中使用此对象时
if (_adjacencyList[source].Contains(sourceEdge) ...) { throw new InvalidOperationException("addEdge: Edge already exists in Graph.n"); }
您调用该方法Contains。现在，您的 LinkedList 对象必须查看它保存的数据，并尝试比较给定条目是否已经在列表中，不幸的是，没有提到如何执行此操作，因此它不知道该怎么做。好在创建 LinkedList 的人想到了这一点并说：让我们有一种通用的方法来检查任何数据类型的两个对象是否相等，这就是著名的 Equals 方法的诞生方式。
现在你有权说，等一下，每个类不是默认定义了等于吗？好吧，你是绝对正确的，它是，但也有点错误，Equals 方法的 dafault 实现对我们没有好处，因为它检查对象引用并比较它们。即使您使用相同的数据创建 2 个对象，它们也会有不同的引用，并且对它们的 Equals 方法也会失败(显然)。

继续链表故事，链表将使用失败的 Equals 方法的默认实现，这就是为什么您将错过多边缘情况的原因。