广度优先搜索:使用Python的最短路径

时间:2022-02-01 10:26:02

I came across the problem Breadth First Search: Shortest Reach in Hackerrank and here was my solution in python. However my code only passed one Test Cases among the 7. Where am I wrong in this implementation ?

我遇到了问题广度优先搜索:Hackerrank中的最短范围,这是我在python中的解决方案。但是我的代码只在7中传递了一个测试用例。我在这个实现中哪里错了?

#Hackerrank
#Topic : Graphs
#Url : https://www.hackerrank.com/challenges/bfsshortreach/problem

def bfs(i, n, E):

    level = [-1] * (n+1)
    queue = []
    level[i] = 0
    queue.append(i)

    while len(queue) > 0:
        head = queue[0]
        queue = queue[1:]
        for j,k in E:
            if j == head:
                if level[k] == -1:
                    level[k] = 1 + level[j]
                    queue.append(k)

    return level


q = int(input())
for case in range(q):
    e = input().split(" ")
    n = int(e[0])
    m = int(e[1])
    E = []

    for edge in range(m):
        e = input().split(" ")
        u = int(e[0])
        v = int(e[1])
        E.append([u,v])

    s = int(input())
    distance = bfs(s, n, E)
    dist = []
    for i in distance[1:]:
        if i > 0:
            dist.append(str(i*6))
        if i < 0:
            dist.append(str(-1))

    print(" ".join(dist))
    print("")

1 个解决方案

#1


1  

The problem states the graph is undirected, yet you make it directed by only adding 1 edge:

问题表明图形是无向的,但是只通过添加1个边来指示它:

E.append([u,v])

You should also add the other way edge

你还应该添加另一种方式边缘

E.append([v,u])

#1


1  

The problem states the graph is undirected, yet you make it directed by only adding 1 edge:

问题表明图形是无向的,但是只通过添加1个边来指示它:

E.append([u,v])

You should also add the other way edge

你还应该添加另一种方式边缘

E.append([v,u])