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,