Найти сложность для переписанного DFS - PullRequest
Новая
       27

Найти сложность для переписанного DFS

0 голосов
/ 30 декабря 2018

По следующему вопросу:

По заданным N станциям, исходной станции, станции назначения, структуре данных, которая представляет все возможные пути между каждыми 2 станциями (пути ненаправлены) и длину каждогопуть от одной станции к другой - Найти самый длинный путь от исходной станции до станции назначения

Я написал следующий псевдокод: 

Vertex
    String key
    boolean visited
    LinkedList<Edge>nextEdges


Edge
    Vertext nextVertex
    int length

    tempSum=0
    stack
    maxSum=0
    maxPath
    maxPathByDFS(src,dst)

1        stack.push(src)
2        src.visited=true
3        if (!src.nextEdges.isEmpty)
4            for (currEdge∶src.nextEdges)

5                if (currEdge.nextVertex==dst)
6                    tempSum+=currEdge.lenght
7                    stack.push(dst)
8                    if(tempSum>maxSum)
9                        maxSum=tempSum
10                        stack.toArray(maxPath)
11                    stack.pop
12                    tempSum-=currEdge.lenght
13                else if (!currEdge.nextVertex.visited)
14                    tempSum+=currEdge.lenght
15                    maxPathByDFS(currEdge.nextVertex,dst)
16                    tempSum-=currEdge.lenght
17        stack.pop
18        src.visited=false
19        return

Не могли бы вы помочь мне найтисложность выполнения моего решения во время выполнения?

...