hanyeah

问题描述

在电路分析中，通常以图论为数学工具，进行建模，求解。我们只研究二端元件，可以将电路中的每一个元件用一条边来表示，元件的端点用顶点来表示。

元件的端点和端点是可以连接在一起的，比如导线的端点连接器材的接线柱，当两个端点连接在一起时，我们怎么来存储端点之间的关系，如何执行连接和断开操作。

方法1

每个顶点维护一个数组，与该点连接的顶点存到数组里。

连接一个顶点的时间复杂度是O(n)。

断开一个顶点的时间复杂度是O(n²)。(数组删除一个元素本身的时间复杂度是O(n))

存储所有顶点需要的空间是n²。

循环双向链表

循环双向链表可以自行搜索学习。

连接一个顶点的时间复杂度是O(1)。

断开一个顶点的时间复杂度是O(1)。

存储所有顶点需要的空间是n。

总结

显然使用循环双向链表无论是在时间上还是空间上都是最好的。

在后续的计算中，循环双向链表完全能够胜任。