Почему DFS с использованием стека не дает правильный результат

graph stack depth-first-search

55 просмотра

1 ответ

335 Репутация автора

Смотрите изображение DFS здесь

Я использую стек, чтобы напечатать последовательность DFS. В зависимости от ввода и этого изображения графика, последовательность составляет 1 2 4 8 5 6 3 7. Но мой код выводит как 1 2 4 8 7 6 5 3. Может кто-нибудь объяснить, как я могу это исправить ??

Входные данные:
8 10
1 3
1 2
2 5
2 4
3 7
3 6
4 8
5 8
6 8
7 8


Правильный вывод:

Последовательность: 1 2 4 8 5 6 3 7

Мой код:

#include <bits/stdc++.h>
using namespace std;
vector<int>edges[100];
stack<int>q;
vector<int>item;
int level[100],parent[100],visited[100],tn;



void dfs(int s)
{
    int j,k,fr;
    q.push(s);
    level[s]=0;
    for(j=1;j<=tn;j++)
    {
        visited[j]=0;
    }
    visited[s]=1;
    while(!q.empty())
    {
        fr=q.top();
        q.pop();
        item.push_back(fr);
        for(k=0;k<edges[fr].size();k++)
        {
            if(visited[edges[fr][k]]==0)
            {
                 q.push(edges[fr][k]);
                 //cout<<"Pushed="<<fr<<"="<<edges[fr][k];
                 visited[edges[fr][k]]=1;
            }


        }

        //cout<<endl;



    }
}


int main()
{
    int i,e,p,n,u,v,f,m;
    cin>>tn>>e;
    for(i=1;i<=e;i++)
    {
        cin>>u>>v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs(1);
    cout<<"Sequence="<<endl;
    for(m=0;m<item.size();m++)
    {
        cout<<item[m];
    }
    return 0;
}

Мой код показывает этот вывод: 1 2 4 8 7 6 5 3

Автор: shawon Источник Размещён: 18.07.2016 07:02

Ответы (1)


1 плюс

15990 Репутация автора

Решение

Маркировка узлов как посещенных в реализации содержит ошибку; функция может быть переписана следующим образом.

void dfs(int s)
{
    int j, k, fr;
    q.push(s);
    level[s] = 0;
    for (j = 1; j <= tn; j++)
    {
        visited[j] = 0;
    }
    while (!q.empty())
    {
        fr = q.top();
        q.pop();
        if (0 == visited[fr])
        {
            visited[fr] = 1;
            item.push_back(fr);
            for (k = 0; k < edges[fr].size(); k++)
            {
                q.push(edges[fr][k]);
            }
        }
    }
}

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

1 2 4 8 7 3 6 5

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

1 2 4 8 5 6 3 7

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

Автор: Codor Размещён: 18.07.2016 08:38
Вопросы из категории :
32x32