Dfs

Z RNO-Wiki
(Przekierowano z DFS)

Przeglądanie grafu w głąb

Zakładamy, że wszystkie wierzchołki mają kolor biały.

 for each vertex u do
   color[u] := 0;

Algorytm DFS można zapisać w następujący sposób rekurencyjny:

  • DFS(u)
    • color[u] := 1
    • for each v adjacent of u do
      • if color[v]=0 then DFS(v)
    • color[u] := 2

Implementacja algorytmu w C++

#include <cstdio>
#include <vector>
 
using namespace std;
 
const int n=1000,    // liczba wierzchołków w grafie <= 10^6
          m=100000;  // liczba krawędzi w grafie
vector <int> adj[n]; // tablicw sąsiadów każdego wierzchołka
 
 
vector<int>  toporder;  // kolejne wierzchołkie zaznaczane na czarno   
vector<char> color;     // oznacza, czy dany wierzchołek jest odwiedzony:
                        // 0=nieodwiedzony, 1=odwiedzony, 2=odwiedzono wszystkich jego synów
 
void dfs(int u)   // DFS - przeglądanie grafu w głąb
{
  color[u]=1;     // markujemy wierzchołek, czyli odwiedzamy go
  int v,s=adj[u].size();
  for(int i=0;i<s;i++) // sprwadzamy wszystkich sąsiadów
  {
    v = adj[u][i];     // syn wierzchołka u; moznaby ustawic prev[v]=u
    if(color[v]==0) dfs(v); // rekurencja :-)
    // else if (color[v]==1) // ZNALEZLISMY CYKL W GRAFIE :-)  --- nawet skierowanym 
  }
  // np. tu można dostawić listowanie "przerobionych" wierzcholkow 
  color[u]=2;
  toporder.push_back(u);
};
 
void load(void)  //Funkcja wczytująca GRAF SKIEROWANY
{
  int a,b;  //roboczo konce krawedzi
  scanf("%d %d", &n, &m);
  for(int i=0;i<m;i++)
  {
    scanf("%d %d", &a, &b);
    adj[a].push_back(b);  //Jesli graf ma być nieskierowany, odkomentuj następną linię:
    // adj[b].push_back(a);
  }
};
 
int main(void)
{
  load(); //gdzieś tu można użyć DSF(x), gdzie x to początek algorytmu
 
  color.clear(); color.resize(n,0); // przed dfs-em nalezy wszystkie wierzcholki "nieodwiedzić"
  dfs(5); // rozpoczynamy DFS-a w wierzchołku u-5 (a czemu nie?)
  return 0;
}

Osobiste