如何在Python中为BFS创建混合图？

Question

这是我有史以来的第一个问题，所以如果有任何问题，我很抱歉。 任务是：创建一个可以通过使用边缘列表包含方向边缘和无定向边缘的图形（需要BFS搜索）。例如：混合图。在此图中，边缘列表将是此格式（edge_number：start_vertex end_vertex）：

• 0：0：0 1
• 1：0 3
• 2：1 2
• 3：1 3
• 4：2 1
• 5：3 0
• 6：3 2

这是与此处的代码输出：

print("First number is nodes, second number is edges: ")
N, M = map(int, input().split()) #N is nodes and M is edges
print(f"Now graph has {N} nodes and {M} edges")

print("\nNow input all neighbours: ")
graph = {i: set() for i in range(N)} #store as a dictionary
for i in range(M): #in the cycle add all of the M edges 
    v1, v2 = map(int, input().split()) #inputting start_vertex and end_vertex
    graph[v1].add(v2) #adding adjacency of two nodes 
    print(f"graph v1 is {graph[v1]}")
    graph[v2].add(v1)
    print(f"graph v2 is {graph[v2]}")
        
    print("\nNow you'll see all nodes: {their neighbours}: ------------HERE YOU SHOULD SEE POSSIBLE ROUTES LIKE NODE: {POSSIBLE_ROUTE_TO}")
    for key, value in graph.items():
        print("{0}: {1}".format(key,value))

和输出：

First number is nodes, second number is edges:
4 7
Now graph has 4 nodes and 7 edges

Now input all neighbours:
0 1
graph v1 is {1}
graph v2 is {0}
0 3
graph v1 is {1, 3}
graph v2 is {0}
1 2
graph v1 is {0, 2}
graph v2 is {1}
1 3
graph v1 is {0, 2, 3}
graph v2 is {0, 1}
2 1
graph v1 is {1}
graph v2 is {0, 2, 3}
3 0
graph v1 is {0, 1}
graph v2 is {1, 3}
3 2
graph v1 is {0, 1, 2}
graph v2 is {1, 3}

Now you'll see all nodes: {their neighbours}: ------------HERE YOU SHOULD SEE POSSIBLE ROUTES LIKE NODE: {POSSIBLE_ROUTE_TO}
0: {1, 3}
1: {0, 2, 3}
2: {1, 3}
3: {0, 1, 2}

关键点是，控制台说Node_3具有箭头（方向边）到Node_0，node_1和node_2。显然（在控制台i从图片中重复图）node_3应该只有一个方向的边缘（pic上的数字5）到node_2，而一个无方向的边缘（pic上的数字6）到node_0，但控制台说它具有另一种连接 - 带有node_1 （这就是问题）。

换句话说，我上面列出的代码找到了当前节点的所有邻居，但是它应该仅向我们显示可能的路由，即最后的控制台字符串应为“ 3：{0，2}”。 我该如何修复？我对集合的方法（例如set.update（x）或set.difference（x））有一些猜测，但老实说不知道。

非常感谢您的时间和可能的解决方案。

PS如果您想知道完整代码：

from collections import deque
print("First number is nodes, second number is edges: ")
N, M = map(int, input().split()) #N is nodes and M is edges
print(f"Now graph has {N} nodes and {M} edges")
    
print("\nNow input all neighbours: ")
graph = {i: set() for i in range(N)} #store as a dictionary
for i in range(M): #in the cycle add all of the M edges 
    v1, v2 = map(int, input().split()) #inputting start_vertex and end_vertex
    graph[v1].add(v2) #adding adjacency of two nodes 
    print(f"graph v1 is {graph[v1]}")
    graph[v2].add(v1)
    print(f"graph v2 is {graph[v2]}")
            
        print("\nNow you'll see all nodes: {their neighbours}: ------------HERE YOU SHOULD SEE POSSIBLE ROUTES LIKE NODE: {POSSIBLE_ROUTE_TO}")
        for key, value in graph.items():
            print("{0}: {1}".format(key,value))

for start_vertex in range(N):
    print(f"\n------------------------------------------START VERTEX IS {start_vertex} NOW----------------------------------------")

    distances = [None] * N 
    distances[start_vertex] = 0 #distance to ourself = 0
    queue = deque([start_vertex]) # init queue as a deque 
    parents = [None] * N

    while queue: #until queue is empty
        current_vertex = queue.popleft() #take 1st elem
        for neighbours_vertex in graph[current_vertex]: #going through its neighbours
            if distances[neighbours_vertex] is None: #if neigh hasn't been visited (distance = none)
                distances[neighbours_vertex] = distances[current_vertex] + 1 #now counting distance
                parents[neighbours_vertex] = current_vertex
                queue.append(neighbours_vertex) #add to queue for we'll check neighbours later
    print("Now you'll see the distances from start_vertex to all of them nodes in 0...N format: ", distances)   
    
    for end_vertex in range(N):
        print(f"END VERTEX IS {end_vertex} NOW")
        parent = parents[end_vertex]
        path = [end_vertex] 

        while not parent is None: 
            path.append(parent)
            parent = parents[parent]
        print(f"Optimal path from start_vertex {start_vertex} to end_vertex {end_vertex}", path[::-1])

Answer 1

指示您称之为目标的正确术语。

您不能在一个图中混合定向和无向链接。

您可以拥有一个无方向的图，每个链接都朝着两个方向传达。

或

您可以有一个有向图，每个链接都朝一个方向朝一个方向进行，如果您想指定可以从A到B和B，则需要节点之间的两个链接一个向每个方向沿着。

在您的输入代码中，

graph[v1].add(v2) 
graph[v2].add(v1)

您每次输入一对节点时，都会始终添加两个有针对性的边缘。您在想要一种单程连接的节点对之间没有区别，并且您想要一个链接朝一个方向延伸。最好的猜测：您应该删除第二行代码。