Связность графа

Question

int dfs(int graph[MAXNODES][MAXNODES],int visited[],int start) {
int stack[MAXNODES];
    int top=-1,i;
    visited[start]=1;
    stack[++top]=start;
    while(top!=-1)
    {
  start=stack[top];
        for(i=0;i<MAXNODES;i++) {
   if(graph[start][i]&&visited[i]==0) {
                stack[++top]=i;
                printf("%d-",i);
                visited[i]=1;
                break;
            }
        }
  if(i==MAXNODES)
            top--;
    }
    return 0;
}

Приведенный выше код реализует DFS на графике, хранящемся в виде матрицы смежности. Я прошу предложить, какое изменение я должен сделать, чтобы узнать, связан ли сгенерированный граф или нет.

Answer 1

См. Мой ответ на предыдущий вопрос о сильно связанных компонентах.

Ваши dfs также очень неэффективны, как написано, потому что вы начинаете повторное сканирование при i = 0; ваш стек должен помнить, где вы остановились и продолжать оттуда. Рекурсия более естественна, но если у вас ограниченный размер стека вызовов, лучше использовать явный стек (только для огромных деревьев).

Вот рекурсивные DFS. Если вы не заинтересованы в сохранении дерева dfs, вы можете просто сохранить 1 в предшественнике [] вместо узла, с которого вы его достигли):

const unsigned MAXNODES=100;

/* predecessor must be 0-initialized by the caller; nodes graph[n] that are
 reached from start will have predecessor[n]=p+1, where graph[pred] is the
 predecessor via which n was reached from graph[start].
 predecessor[start]=MAXNODES+1 (this is the root of the tree; there is NO
 predecessor, but instead of 0, I put a positive value to show that it's
 reached).

 graph[a][b] is true iff there is a directed arc from a->b

 */

void dfs(bool graph[MAXNODES][MAXNODES],unsigned predecessor[]
         ,unsigned start,unsigned pred=MAXNODES) 
{
    if (predecessor[start]) return;
    predecessor[start]=pred+1;
    for (unsigned i=0;i<MAXNODES;++i)
        if (graph[start][i])
            dfs(graph,predecessor,i,start);
}

Вот нерекурсивный dfs, созданный по шаблону выше, но использующий одну и ту же переменную стека для pred и i (в общем случае у вас будет переменная стека для каждой локальной переменной и параметра, которые могут измениться в вашей рекурсии ):

void dfs_iter(bool graph[MAXNODES][MAXNODES],unsigned predecessor[]
              ,unsigned start)
{
    unsigned stack[MAXNODES]; // node indices
    unsigned n,pred;
    int top=0;
    stack[top]=start;
    for(;;) {
    recurse:
        // invariant: stack[top] is the next (maybe reached) node
        n=stack[top];
        if (!predecessor[n]) { // not started yet
            pred=top>0?stack[top-1]:MAXNODES;
            //show(n,pred);
            predecessor[n]=pred+1;
            // the first thing we can reach from n
            for (unsigned i=0;i<MAXNODES;++i)
                if (graph[n][i] && !predecessor[i]) {
                    stack[++top]=i; goto recurse; // push
                }
        }
        if (top>0) {
            pred=stack[top-1];
            // the next thing we can reach from pred after n
            for (unsigned i=n+1;i<MAXNODES;++i)
                if (graph[pred][i]) {
                    stack[top]=i; goto recurse; // replace top
                }
            --top;
        } else
            return;
    }
}

Это может быть структурировано без перехода (это просто именованное продолжение в самый дальний цикл), но без какой-либо дополнительной ясности, на мой взгляд.

В любом случае, рекурсивные вызовы намного проще. Существует рекурсивный псевдокод для Алгоритма сильно связанных компонентов Тарьяна , который вы можете транскрибировать довольно напрямую. Если вам нужна помощь, чтобы сделать его нерекурсивным (явный стек), спросите.

Answer 2

Вам нужно сохранить ребра, сгенерированные при перемещении от одного узла к другому. Тогда вы можете убедиться, что все узлы графа соединены ребрами.

Answer 3

Запустить алгоритм Дейкстры. Если в конце ваша очередь пуста и некоторые вершины не окрашены, ваш график не подключен. Это гарантированное линейное время, метод dfs имеет наихудший случай квадратичного анализа