Кодирование глубины первого поиска (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); 
} 

Что посещает [j] в условии if? Я понимаю, что как только вы посещаете любой узел, вы должны сделать бит узла в массиве равным 1, но как мы применим условие not для любого массива?

Answer 1

Здесь побывали [], работающие как флаг. Надеюсь, вы поняли, как работает алгоритм (если не попытаться понять его в первую очередь). Вы знаете, что DFS всегда идет с глубиной. То есть, если он получает 3 в виде листа 2, тогда он перейдет на узел 3 и будет искать листья из 3. Поэтому рассмотрим график, где узел 1 связан с 2, 2 связан с 3 и 3 связано с 1. Если мы запустим DFS из узла 1, он будет выглядеть следующим образом: 1-> 2-> 3-> 1-> 2-> 3 и т. д., которые никогда не прекратятся. Чтобы избежать такого цикла, мы отмечаем текущий узел как посещенный и посещаем только те узлы, которые ранее не были посещены.

С посещением [j] это означает, что j-й узел ранее не был посещен.

Answer 2

В глубине первого поиска идея состоит в том, чтобы путешествовать как можно глубже от соседа до соседа перед возвратом назад. То, что определяет глубину, заключается в том, что вы должны следовать за краями, , и вы не посещаете какую-либо вершину дважды (! Visit [j])