C++

Question

我尝试实现此算法，但存在一些逻辑错误。下面给出算法。


DFS(G)

1.  for each vertex u ∈ G.V

2.     u.color = WHITE
3.     u.pi = NIL

4.  time = 0

5.  for each vertex u ∈ G.V
6.     if u.color == WHITE
7.        DFS-VISIT(G,u)


DFS-VISIT(G,u)

1.  time = time + 1
2.  u.d = time
3.  u.color = GRAY

4.  for each v ∈ G.Adj[u]
5.     if v.color == WHITE
6.        v.pi = u

7.        DFS-VISIT(G,v)

8.  u.color = BLACK
9.  time = time + 1
10.  u.f = time

代码：

#include <bits/stdc++.h>
using namespace std;

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define SIZE 100

int Time;

int adj[SIZE][SIZE];
int color[SIZE];
int parent[SIZE];

int d[SIZE];

void dfs_Visit(int G, int u)
{
    Time++;
    d[u] = Time;
    color[u] = GRAY;

    for(int i = 0; i < G; i++)
    {
        if(color[i] == WHITE)
        {
            parent[i] = u;
            dfs_Visit(G, i);
        }
    }
    color[u] = BLACK;

    Time++;
    cout << u << " ";
}


void dfs(int G)
{
    for(int i = 0; i < G; i++)
    {
        color[i] = WHITE;
        parent[i]=NULL;
    }

    Time=0;

    cout << "DFS is ";
    for(int i = 0; i < G; i++)
    {
        if(color[i] == WHITE)
        {
            dfs_Visit(G, i);
        }
    }
}


int main()
{
    int vertex;
    int edge;
    cout << "VERTEX & Edge  : ";
    cin >> vertex >> edge;

    cout << "Vertex is : " << vertex <<endl;
    cout << "Edge is : " << edge <<endl;

    int node1, node2;
    for(int i = 0; i < edge; i++)
    {
        cout << "EDGE " << i << ": ";
        cin >> node1 >> node2;
        adj[node1][node2] = 1;
        adj[node2][node1] = 1;

    }
    dfs(vertex);
}

Output picture

输入：

顶点和边：4 5 顶点是：4 边是：5 边缘 0: 0 1 边 1: 1 2 边缘 2: 2 0 边缘 3：0 3 边缘 4: 2 4

输出：

DFS is 3 2 1 0

接受的结果是2 1 3 0

Answer 1

问题是您没有正确编码 DFS-VISIT 第 4 步

第 4 步说 for each v ∈ G.Adj[u]，但您的代码说 for(int i=0; i<G; i++)。这些根本不是一回事。您应该只访问相邻的顶点。

事实上，如果您查看您的代码，您根本不会使用 adj。这不对。

C++ - DFS 代码错误

C++ - DFS code error

algorithm

depth-first-search