为图实现邻接表

Question

我得到了这样的图表字符串

graph_string = """\
D 3
0 1
1 0
0 2
"""

我的函数需要将该图输出为这样的邻接列表

[[(1, None), (2, None)], [(0, None)], []]

但是我的函数只是这样输出的

[[(2, None)], [], []]

我不知道为什么？

def adjacency_list(graph_str):
    """Takes a graph string and returns the adjacency list"""

    lines = graph_str.splitlines()
    header = lines[0].split()

    if len(header) > 2:
        graph_type, vertices, weight = header[0], header[1], header[2]
    else:
        graph_type, vertices = header[0], header[1]
        weight = None

    edges = lines[1:]
    adj_list = [[] for _ in range(int(vertices))]

    if len(edges) > 0:
        for edge in edges:
            if weight == 'W':
                v1, v2, w = edge.split()
                v1, v2, w = int(v1), int(v2), int(w)
            else:
                v1, v2 = edge.split()
                v1, v2 = int(v1), int(v2)
                w = None
    if graph_type == 'U':
        adj_list[v1] += [(v2, w)]
        adj_list[v2] += [(v1, w)]
    else:
        adj_list[v1] += [(v2, w)]
    return adj_list
    
graph_string = """\
D 3
0 1
1 0
0 2
"""
print(adjacency_list(graph_string))

Answer 1

代码很好，除了最后的 if-else 的缩进。处理边后需要立即添加邻接列表项，因此应该在 for 循环内部（而不是外部）。

下面的代码是固定的。

def adjacency_list(graph_str):
    """Takes a graph string and returns the adjacency list"""

    lines = graph_str.splitlines()
    header = lines[0].split()

    if len(header) > 2:
        graph_type, vertices, weight = header[0], header[1], header[2]
    else:
        graph_type, vertices = header[0], header[1]
        weight = None

    edges = lines[1:]
    adj_list = [[] for _ in range(int(vertices))]

    if len(edges) > 0:
        for edge in edges:
            if weight == 'W':
                v1, v2, w = edge.split()
                v1, v2, w = int(v1), int(v2), int(w)
            else:
                v1, v2 = edge.split()
                v1, v2 = int(v1), int(v2)
                w = None
                
            if graph_type == 'U':
                adj_list[v1] += [(v2, w)]
                adj_list[v2] += [(v1, w)]
            else:
                adj_list[v1] += [(v2, w)]
    return adj_list
    
graph_string = """\
D 3
0 1
1 0
0 2
"""
print(adjacency_list(graph_string))

为图实现邻接表

implementing adjacency list for graph

python

adjacency-list