|
Cr1stal |
|
|
|
Построить детерминированную машину Тьюринга, выписывающую за полиномиальное время все компоненты связности неориентированного графа.
Какой здесь алгоритм действий????
|
|
|
|
 |
|
Xaositect |
|
|
|
Ну как.
Берем вершину, добавляем к ней все смежные с ней, потом смежные со смежными и т. д. пока не станет так, что не сможем ничего добавить - это получится одна компонента связности.
Если еще остались вершины, берем одну из них и так же строим ее компоненту связности.
И так далее, пока граф не кончится.
|
|
|
|
|
|
Xaositect |
|
|
|
А подробности зависят от того, как у Вас вводились машина Тьюринга и кодировка графов в строки.
|
|
|
|
|
