Поиск в ширину на невзвешенном двунаправленном графике - PullRequest
Новая
       47

Поиск в ширину на невзвешенном двунаправленном графике

0 голосов
/ 13 октября 2018

Я пытался использовать BFS, чтобы найти кратчайший путь между 2 узлами.Я пытался смотреть учебники и онлайн-чтения, но ни одно из них не было достаточно ясным для меня.В настоящее время я могу только проходить через график, но я не совсем уверен, какие проверки мне нужны, чтобы найти минимальный путь между 2 узлами в графике.График невзвешенный и двунаправленный.Это мой код для обхода всех узлов графа с использованием BFS. 

def bredthfirstsearch(start, end, graph):
    queue = [start]
    visited = [False]*(roads+1) #marks if a node has been visited
    visited[start] = True
    while len(queue) != 0:
        # source node popped and later used to find neighboring nodes
        node = queue.pop(0)

        for item in graph[node]:
            # if the node has not been found previously
            if visited[item[0]] == False:
                queue.append(item[0]) # it is added to the queue for future checking on its neighbors 
                visited[item[0]] = True #node then set to true

Теперь мне может понадобиться дополнительный массив для хранения кратчайшего пути, но я не уверен, как это сделать.Большое вам спасибо.

1 Ответ

0 голосов
/ 13 октября 2018

BFS поможет вам найти все кратчайшие пути от определенного узла .Если вы хотите использовать BFS, чтобы найти минимальный путь между каждой парой узлов в графе, вам нужно будет запускать BFS практически из каждого узла (почти из каждого узла, потому что у вас уже будут рассчитываться некоторые листы).

Вот как найти расстояние между двумя узлами.Используя BFS на вершине a (произвольной вершине), вы сможете найти все кратчайшие пути (расстояния) до других вершин.Для расчета расстояния вам понадобится «счетчик уровня».Вот псевдокод, который поможет вам сделать это: 

q = new Queue()
dist_array = new Array(N) //and Set each value to infinity
distance=0
q.enqueue(a) //a is the selected node
dist_array[a] = 0
while q not empty:
    v = q.dequeue()
    ++distance
    for each neighbor x of v:
        if distance_array[x] < infinity:
             continue
        d[x] = distance
        q.enqueue(x)

скажем, что ваш график имеет вид G = (V, E), когда:

  • V = {a, b, c, d, e, f}, | V |= N = 6
  • E = {(a, b), (a, c), (a, e), (b, d), (b, e), (d, f)},| E |= M = 6

Если мы запустим этот код на нашем графике, мы получим следующий результат 

dist=1: a->b, a->c, a->e
dist=2: a->d
dist=3: a->f
...