Создание алгоритма, который проверяет, связан ли граф или нет - PullRequest
Новая
       13

Создание алгоритма, который проверяет, связан ли граф или нет

0 голосов
/ 18 февраля 2020

Итак, был задан старый экзаменационный вопрос. Мне было интересно, что это значит, потому что график может быть направленным или нет. В ориентированном графе он должен работать так (я думаю): 

Create two Arrays: A[], A_inverse[] //both in size N (N nodes exists), both arrays initalized with NULL
Run depth-first search on Graph G
     save in A[] all Nodes which are visted
         If(A.size < |N|) return false
G' = Reverse all edges of G
Run depth-first search on Graph G'  
     save in A_inverse[] all Nodes which are visted
         If(A_inverse.size < |N|) return false
return true

Для сложности времени это T (N) = 2 * DFS + | E | + c. 2 * DFS, потому что я вызываю его дважды (один раз для G и один раз для G '). | E | потому что мне нужно обратить все края. c - это все условия и инициализации. Мой алгоритм правильный?

1 Ответ

1 голос
/ 02 марта 2020

В сильно связанном графе G должен быть путь от любого узла A к любому (другому) узлу B.

Для начала обратите внимание, что в перевернутом графе есть путь от B до A G 'тогда и только тогда, когда в исходном графе G. есть путь от A к B.

Предположим, что DFS начинается в некотором исходном узле O.

Сначала покажем, что если G сильно подключено, алгоритм возвращает значение true.

  • Первая DFS достигнет всех узлов, поскольку, по предположению, существует путь от O до каждого другого узла.
  • Опять по предположению, есть путь от каждого узла до O. Из этого следует, что в G '(где все ребра перевернуты) есть путь от O до каждого другого узла. Таким образом, вторая DFS также достигнет всех узлов, и алгоритм вернет true.

Теперь рассмотрим граф G, который не является сильно связанным, т. Е. Есть пара узлов (A, B), такая, что не существует пути от A до B. Мы должны показать, что алгоритм возвращает false. Необходимо рассмотреть два случая:

  • Нет пути от A до O . В этом случае перевернутый граф G 'не может содержать путь от O до A. Следовательно, вторая DFS не достигнет A из O, и алгоритм вернет false.
  • Существует путь от A к O : в этом случае не может быть пути от O к B, потому что, если бы он был, наше предположение об отсутствии пути от A к B было бы неверным. Поскольку нет пути от O к B, первая DFS не достигнет B из O, и алгоритм возвращает false.

Мы доказали, что алгоритм возвращает true, если G сильно связан, и false в противном случае. Поэтому это правильно.

...