Пространственно-временная сложность BFS и DFS, на графике в AdjacencyMatrix и AdjacencyList - PullRequest
Новая
       72

Пространственно-временная сложность BFS и DFS, на графике в AdjacencyMatrix и AdjacencyList

1 голос
/ 23 мая 2019

Я выполнил BFS и DFS (для печати графиков) -> с несколькими реализациями.Но меня смущает их временная сложность, и, читая онлайн, некоторые говорят, что это O (V ^ 2).некоторые говорят, что это O (| V + E |), я действительно запутался сейчас.

Я прилагаю свои различные реализации.[Присоединение в качестве ссылки для лучшей подсветки синтаксиса] 1. Graph_AdjMat -> график с реализацией матрицы

Graph_AdjList -> график с реализацией списка

График Graph_AdjList_Weighted_Map для взвешенного сценария, взвешивает imipllements с использованием Map, чтобыузел карты -> node_weight

График Graph_AdjList_Weighted_Vertex для взвешенного сценария, взвешивает изменения с использованием класса Vertex

Преимущественновам нужно проверить код (1) (2) & (3) 

as in code (1) : implementation using matrix.       [[[ CONSTANT time  for checking if two node's are connected ]]]
in code(2) . : implementation using List of Lists     [[[ --> here it takes O(N) for checking if two node's are connected ]]]
in code(3) . : implementation using List of Maps     [[[ --> CONSTANT time  for checking if two node's are connected ]]]

Так что, если я буду применять dfs & bfs во всех них, какова будет сложность времени и пространства в DFS и BFS? 

               TIME (DFS)         TIME (BFS)      SPACE (DFS)     SPACE (BFS)
--------------------------------------------------------------------------------
Code 1  :   |                  |                  |             |              |
------------|------------------|------------------|-------------|--------------|
Code 2  :   |                  |                  |             |              |
------------|------------------|------------------|-------------|--------------|
Code 3  :   |                  |                  |             |              |
--------------------------------------------------------------------------------
...