DFS graf skierowany

Cześć, powtarzam sobie ćwiczenia z algorytmów i mam problem z implementacją dfs-a dla grafu skierowanego, tak aby poszukiwania zaczynały się od zadanego wierzchołka.

Znalazlem algorytm:

dfsVertices(G){
color all vertices white;
time = 0;
for( each v V)
if (color[v] == “white”) DFS(v);
}

DFS(v){
color[v] = “gray”;
d[v] = ++time;
[previsit(v)]
for (each w adjacent to v){
if(w is white) edge(v, w).Type = “treeEdge”;
else if(w is gray) edge(v, w).Type = “backEdge”;
else if(d[v] < d[w]) edge(v, w).Type = “forwardEdge”;
else edge(v, w).Type = “crossEdge”;

       if (color[w] == “white”){
         [ Add edge (v, w) to DFS tree]
         DFS(w)
      }
   }
  f[v] = ++time;
  [postvisit(v)]
  color[v] = “black”;

}

I wszystko działa, tylko chciałbym zamienić algorytm żeby zaczynał od podanego wierzchołka.

void DFS(node* array, int vertexs, int start) {
int i;
  for(i=0;i<vertexs;i++) {
     array[i].color=WHITE;
     array[i].p=0;
  }
  for (i = 0; i < vertexs; i++) {
     if (array[i].color == WHITE) {
     DFSVisit(array, i);
}

void DFS(node* array, int vertexs, int start) {
int i;
  for(i=0;i<vertexs;i++) {
     array[i].color=WHITE;
     array[i].p=0;
  }
DFSVisit(array,start);
}

Ale to nie jest dobre rozwiazanie, jak powinienem to poprawic ?

Pozdrawiam,

Poważnie? Rekurencyjny DFS? Przepisz to po ludzku na wersje iteracyjną z listą i problem sam sie rozwiąże...

Nie powinieneś nić poprawiać.
Sens tej odpowiedzi dasz rady zrozumieć, kiedy zrozumiesz mniej więcej co się dzieje w tym kodzie.

Hm, ok sprawdzmy czy rozmumiem sens.

for (i = 0; i < vertexes; i++) {
     if (array[i].color == WHITE) {
     DFSVisit(array, i);
}

Zaczynam przeszukiwania od 0, wszystkie wierzcholki sa w kolorze białym - przegladam wszystkich sasiadow wierzcholka i sasiadow sasiadow zmieniajac ich kolor - w sytacji jezeli brakuje sasiadow wracam do petli i sprawdzam od 1 czy wierzcholki sa juz odwiedzone (kolor inny niz bialy) - jezeli znajde bialy wierzcholek to rozpoczynam dalej poszukiwania ? Ok, jeżeli to jest ok to rozważmy inna sytuację z grafem startowym:

Mam graf:

0->1
0->4
1->2
2->3
3->4
4->1

Graf skierowany.

Rozpoczynam od wierzcholka 3. Odwiedzam wierzcholek 3, 4, 1, 2 - wszystkie zamkniete - kolor czarny. Wychodze z petli i biore nastepny wierzcholek po startowym czyli 4. Zamykam wierzcholek 4. Potem moge sprawdzac wierzcholki mniejsze od startowego do 0 i znajde to 0 ktore nie jest odwiedzone i zamkne go -> kolor czarny - i tak beda zamkniete wszystkie wierzcholki... Przy okazji wypisuje tez rodzaje krawedzi miedzy wierzcholkami.
Ale cos mi samemu nie pasuje w takim rozwiazaniu...

i =start; 
       for (;start<vertexes;start++) 
        DFSVisit(array,start); 

      for (;i>=0;i--) 
        DFSVisit(array,i)

Hm...

void DFS(node* array, int vertexes, int start) {
 int i = start; 
      
 for (;start<vertexes;start++) {
     if (array[start].color == WHITE) 
        DFSVisit(array, start);
 }

 for (;i>=0;i--) {
     if (array[i].color == WHITE) 
        DFSVisit(array, i);
 }
}

Oczywiście źle skopiowałem... Miałeś na myśli ten błąd ?

Stosuj zasadę DRY.

void DFS(node* array,int vertexes,int start)
  {
   for(int i=0;i<vertexes;++i)
     {
      if(array[start].color==WHITE)  DFSVisit(array,start);
      if(++start>=vertexes) start=0;
     }
  }