算法实现错误（DFS）

Question

我正在尝试实现 dfs 以从起始节点打印路径。我遵循 Coremen 书中的算法。这是我的代码： DFS

#include<iostream>
#include<stack>
using namespace std;

int vertex,edge,source,time,adjacency_matrix[100][100],parent[100],Distance[100],Finishing_time[100];
string color[100];
stack<int> result;
void inputGraph();
void initialize();
void doDFS();
void doDFSvisit(int);
void printPath();
//void printAll();
//void printAdjacencyMatrix();
//void printColor();
//void printDistance();
//void printParent();

int main(void)
{
    inputGraph();
    //initialize();
    doDFS();
    printPath();
    //printAll();
    return 0;
}
void inputGraph()
{
    cout<<"Total vertex : ";
    cin>>vertex;
    cout<<"Total edge   : ";
    cin>>edge;
    int i,j;
    for(i=1; i<=edge; i++)
    {
        int start,finish;
        cout<<"Enter start and end node for edge "<<i<<" : ";
        cin>>start;
        cin>>finish;
        adjacency_matrix[start][finish]=1;
    }
    cout<<"The adjacency matrix is : "<<endl;
    for(i=1; i<=vertex; i++)
    {
        for(j=1; j<=vertex; j++)
        {
            cout<<adjacency_matrix[i][j]<<" ";
        }
        cout<<endl;
    }
}
void initialize()
{
    cout<<"Enter source node : ";
    cin>>source;
}
void doDFS()
{
    int i,j;
    for(i=1;i<=vertex;i++)
    {
        color[i]="white";
        parent[i]=0;
    }
    time=0;
    for(i=1;i<=vertex;i++)
    {
        if(color[i]=="white")
        {
            doDFSvisit(i);
        }
    }
}
void doDFSvisit(int node)
{
    int i;
    time=time+1;
    Distance[node]=time;
    color[node]="grey";
    for(i=1;i<=vertex;i++)
    {
        if(adjacency_matrix[node][i]==1)
        {
            if(color[i]=="white")
            {
                parent[i]=node;
                doDFSvisit(i);
           }
        }
    }
    color[node]="black";
    //extra line for result
    result.push(node);
    //
    time=time+1;
    Finishing_time[node]=time;
}
void printPath()
{
    cout<<"Path :"<<endl;
    int i;
    for(i=0;i<=result.size();i++)
    {
        cout<<result.top()<<" -> ";
        result.pop();
    }
    cout<<" End"<<endl;
}

我的问题：

输入：

6

6

1 2

1 4

2 3

3 4

5 3

5 6

我的输出应该是：

5 6 1 2 3 4 end

但我的输出是：

5 6 1 2 end

似乎从堆栈打印值会产生问题。请纠正我的错误，在此先感谢。

[P.S。 : 我用于输入的有向图的图片，http://imgur.com/fYsICiQ ]

Answer 1

以下是我将如何在 C++ 中实现 DFS。首先是一些观察：

我将使用邻接表 (std::vectors) 而不是邻接矩阵。
Node 不属于他们的邻居。它们被假定为父 Graph 对象所有。

所以，事不宜迟：

struct Node {
    std::vector<Node *> neighbors;
    // Other fields may go here.
}

void process(Node * node)
{
    // Actual logic for processing a single node.
}

// Of course, in idiomatic C++, this would be a template
// parameterized by a function object, rather than contain
// a hard-coded call to a fixed `process` function.
void depth_first(Node * start)
{
    std::stack        <Node *> pending = { start };
    std::unordered_set<Node *> visited;

    while (!pending.empty()) {
        Node * current = pending.pop();
        process(current);
        for (Node * neighbor : current->neighbors)
            if (visited.find(neighbor) == visited.end()) {
                pending.push  (neighbor);
                visited.insert(neighbor);
            }
    }
}

此实现的一个好处是，为了获得 BFS，您只需将 std::stack 替换为 std::queue，其余代码保持原样。

Answer 2

print_path函数有错误。您的 for 循环终止条件检查结果（堆栈）的大小，它通过 pop 调用递减每个循环迭代。

您的 print_path 函数应如下所示：

void printPath(){
    cout<<"Path :"<<endl;
    int i;
    while(!result.empty()){
        cout << result.top() << " -> ";
        result.pop();
    }
    cout<<" End"<<endl;
}

另外考虑这个 DFS 实现：

list<size_t> l[N];
bool used[N];
void DFS(size_t s){
    if (used[s])
        return;
    used[s] = true;
    for(auto i = l[s].begin(); i != l[s].end(); i++)
        if(!used[*i]){
            DFS(*i);
        }
}

used 是全局 bool 数组，指示是否访问了第 i 个顶点。我们不需要为顶点着色。我们必须知道它是否已经访问过。

l 是邻接表（参见 http://www.geeksforgeeks.org/graph-and-its-representations/）

我们运行在某些顶点上进行 DFS。如果它被访问，我们什么都不做。否则我们将这个顶点标记为已访问。然后在与当前顶点相邻的每个顶点上更深入运行ning DFS。

有关 DFS 的详细信息，请参阅 https://en.wikipedia.org/wiki/Depth-first_search

算法实现错误（DFS）

algorithm implementation error (DFS)

c++

algorithm

depth-first-search