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

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 в precedent[] вместо узла, с которого вы к нему обратились):

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 имеет квадратичный анализ наихудшего случая.