c++ - 深度优先搜索(DFS)编码

Question

#include<iostream>

void DFS(int);
int G[10][10], visited[10], n;

//G->Adjacency Matrix, n->no of vertices

void main()
{
int i,j;
cout<<"Enter vertices";
cin>>n
cout<<"Enter adjacency matrix";
for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        cin>>G[j][i];

for(i=0;i<n;i++)
    visited[i]=0

DFS(0);

void DFS(int i)
{
int j;
cout<<"\n"<<i;
visited[i]=1;
for(j=0;j<n;j++)
    if(!visited[j] && G[i][j]==1)
            DFS(j);
}

if 条件中的 !visited[j] 是什么意思？我知道一旦访问任何节点，就必须使数组中的节点位为 1，但是我们如何对任何数组应用 not 条件？

Answer 1

这里访问[] 像一面旗帜一样工作。我希望您了解该算法的工作原理(如果不先尝试了解它)。你知道 DFS 总是有深度的。也就是说，如果它得到 3 作为叶子 2，那么它会去节点 3 并搜索 3 的叶子。所以考虑一个图，其中节点 1 与 2 相连，2 与 3 和 3 相连与 1 相连。如果我们从节点 1 运行 DFS，它将按如下方式运行:1->2->3->1->2->3 等等，永远不会终止。为了避免这样的循环，我们将当前节点标记为已访问，并且只访问之前未访问过的节点。

使用 !visited[j] 表示之前未访问过第 j 个节点。