Как найти более 1 последовательных кратчайших путей между двумя вершинами в невзвешенном и ненаправленном графе, используя BFS? - PullRequest
Новая
       85

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

0 голосов
/ 13 апреля 2020

Я попытался найти и напечатать 3 кратчайших пути между двумя вершинами в неориентированном графе, используя BFS, поскольку DFS в этом случае не будет оптимальным, поскольку он может go глубоко в стек.

Написал эта функция, но не получила правильного ответа, а также пыталась найти помощь по StackOverflow и другим платформам, но не нашла решения для ненаправленного графика. Эта ниже функция находит все пути, но я могу отфильтровать до 3 или любого числа.

Я взял ссылку, я нашел одно решение - https://www.geeksforgeeks.org/print-paths-given-source-destination-using-bfs, но оно не работает для меня , но, оказывается, у меня это не работает. 

func BFS(s, d *Vertex) [][]*Vertex {
    routes := make([][]*Vertex, 0)

    queue := NewFIFO()

    path := make([]*Vertex, 0)
    path = append(path, s)

    queue.Push(path)

    for queue.Len() != 0 {
        p := queue.Pop()
        path = p.([]*Vertex)

        last := path[len(path)-1]

        if last == d {
            routes = append(routes, path)
        }

        for _, as := range last.AdjStations {
            if !isVisited(as, path) {
                newPath := make([]*Vertex, 0)
                newPath = append(newPath, as)
                queue.Push(newPath)
            }
        }

    }

    return routes
}

func isVisited(vertex *Vertex, path []*Vertex) bool {
    for _, v := range path {
        if v == vertex {
            return true
        }
    }

    return false
}
...