DFS по сложности неориентированного графа

Предположим, у меня есть неориентированный граф с V-узлами и ребрами E. Если я представляю граф с списками смежности, если у меня есть представление ребра между x и y, я должен также иметь представление края между y и x в списке смежности.DFS по сложности неориентированного графа

Я знаю, что DFS для ориентированных графов имеет сложность V + E. Для неориентированных графов не имеет сложности v + 2 * e, потому что вы посещаете каждый край 2 раза? Извините, если это вопрос noobish .. Я действительно хотят, чтобы это понять think.Thank вас,

источник

2013-10-06 Emil Grigore

См ответить здесь http://stackoverflow.com/questions/11468621/why-is-the-time-complexity-of-both-dfs-and-bfs-ove – superk

Если граф ациклический, то стоимость является Theta (| V |). Можно иначе заявить, что для обнаружения цикла в неориентированном графе требуется время O (| V |). – shuva

сложность обычно выражается O (| V | + | E |), и это не влияет на коэффициент 2.

но фактор 2 является на самом деле там. Один неориентированный ребро ведет только к ориентированным ребрам линии 2. Например. алгоритм (для подключенного неориентированного графа) является

visit(v) { 
    mark(v) 
    for each unmarked w adjacent to v, visit(w) 
}

для цикла будет рассматривать каждое ребро случай к каждой вершине один раз. Так как каждый неориентированный ребро инцидентен двум вершинам, то это, очевидно, будет рассмотрено дважды!

Обратите внимание, что ненаправленная DFS не должна беспокоиться о перезапуске из всех источников. Вы можете выбрать любую вершину.

источник

2013-10-06 23:22:01 Gene

DFS по сложности неориентированного графа

ответ

Смежные вопросы