Вопрос

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 на графике, хранящемся в виде матрицы смежности, я прошу подсказать, какие изменения я должен внести, чтобы узнать, связан ли сгенерированный граф или нет.

Это было полезно?

Решение

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

Ваша 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;
    }
}

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

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

Другие советы

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top