邻接表构造

Question

我很难理解最后的输出

for i in edgeList:
    adjacencyList[i[0]].append(i[0])

在下面的代码中。我试着在每一行打印语句，试图理解，但仍然感到困惑。

    vertexList = ["0","1","2","3","4","5","6"]
    edgeList = [(0,1), (0,2),(1,0), (1,3), (2,0), (2,4), (2,5), (3,1), (4,2), (4,6), (5,2), (6,4)]

    adjacencyList = [[] for vertex in vertexList]

    for i in edgeList:
        adjacencyList[i[0]].append(i[1])

    print(adjacencyList)

Output: [[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]

这是否被认为是因为列表理解而出现在for循环中的for循环？如果有人能说出这里发生了什么，我很感激。(这与图论中的BFS有关)

Answer 1

图形问题可视化的一个好工具是graphviz，它附带了一个dot命令。首先创建包含来自您的edgelist.dot变量的所有边缘的edgeList：

digraph G {
    0 -> 1
    0 -> 2
    1 -> 0
    1 -> 3
    2 -> 0
    2 -> 4
    2 -> 5
    3 -> 1
    4 -> 2
    4 -> 6
    5 -> 2
    6 -> 4
}

(有一些较短的方法可供您查阅)。然后通过dot提供

c:\srv\tmp> dot -Tsvg -o edgelist.svg edgelist.dot

然后打开创建的edgelist.svg文件：

​

​

邻接列表是可以从特定节点到达的节点列表，例如对于节点0，有指向节点1和2的箭头，因此adjacencyList[0]，即节点0的邻接列表应该是[1, 2]。

类似地，节点2的输出箭头到达节点0、4和5，因此adjacencyList[2]应该是[0, 4, 5]。

按顺序手动遍历每个节点，邻接列表以以下方式结束：

            [[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]
             ^       ^       ^          ^    ^       ^    ^
item/index:  0       1       2          3    4       5    6

在您的代码中，这一行：

adjacencyList = [[] for vertex in vertexList]

只需将adjacencyList创建为长度等于顶点数的空列表([])。

然后这个for循环：

for i in edgeList:
    adjacencyList[i[0]].append(i[0])

试图把它填入。为了了解出了什么问题，我们可以重写for-循环，这样它就可以解压edgeList中的边。

for (start, end) in edgeList:
    adjacencyList[start].append(..?..)

显然，..?..应该是end，而不是start：

for start, end in edgeList:
    adjacencyList[start].append(end)

现在，您可以看到for -循环正在执行我们在上面手动执行的操作，对于每个边缘(start, end)，它将end添加到start的邻接列表中。

增编:在顶点(0、1等)的情况下，您的代码运行良好。具有与数组中的索引相同的值。虽然它是有效的，但在教学上可能并不可取(或者，我不知道;-)在任何情况下，如果我们将顶点重命名为"A"，1变为"B"等，则需要对邻接列表使用不同的数据结构，例如：

from collections import defaultdict

edgeList = [("A", "B"),
            ("A", "C"),
            ("B","A"), ("B","D"),
            ("C","A"), ("C","E"), ("C","F"),
            ("D","B"),
            ("E","C"), ("E","G"),
            ("F","C"),
            ("G","E")]

adjacencyList = defaultdict(list)

for start, end in edgeList:
    adjacencyList[start].append(end)

print(sorted(adjacencyList.items()))

其中的指纹：

[('A', ['B', 'C']), ('B', ['A', 'D']), ('C', ['A', 'E', 'F']), ('D', ['B']), ('E', ['C', 'G']), ('F', ['C']), ('G', ['E'])]

表示'A'的邻接列表是['B', 'C']等。

将此版本转换为第一个版本(尤其是在比Python更静态的语言中)是可能的(也可能有益于运行时间)。

Answer 2

您的adjacencyList结构是错误的。

将adjacencyList[i[0]].append(i[0])替换为adjacencyList[i[0]].append(i[1])。我在另一个里面没有看到任何的循环。您的时间复杂性是O(n)。

adjacencyList的目的是存储给定节点的所有相邻节点，在您的情况下，它是列表的索引。

更改之后，您的输出应该是

[1，2，0，3，0，4，5，1，2，6，2，4]

由此，您可以将0有1和2解释为邻居。2有0和3个邻居，3有0,4和5作为邻居等等。

请注意，如果有{2、60、1000、4}等节点，则此方法将失败。在这种情况下，最好使用节点字典和邻居列表。