446,389 Members | 1,857 Online Need help? Post your question and get tips & solutions from a community of 446,389 IT Pros & Developers. It's quick & easy.

# defth first search algorithm

 P: 17 hi.... i need code for defth first search alogithm. Mar 12 '07 #1
3 Replies

 Expert 100+ P: 1,510 hi.... i need code for defth first search alogithm. for an algorithm have a look at http://en.wikipedia.org/wiki/Depth-first_search Mar 12 '07 #2

 P: 23 hi u need code in which programming language? i am sending you the pseudocode, you can change this to any programming language easily just by applying the syntax of that particular language. dfs(v) process(v) mark v as visited for all vertices i adjacent to v not visited dfs(i) another version dfs(graph G) { list L = empty tree T = empty choose a starting vertex x search(x) while(L is not empty) remove edge (v, w) from end of L if w not yet visited { add (v, w) to T search(w) } } search(vertex v) { visit v for each edge (v, w) add edge (v, w) to end of L } there is a small version of it in C programming language take a look at it typedef int NODE; int A[MAX][MAX], B[MAX][MAX]; int n, label, val[MAX]; void DFS(NODE v){ NODE w; val[v] = ++label; for (w=1; w<=n; w++){ if (A[v][w] != 0) if (val[w] == 0) { B[v][w] = 1; DFS(w); } } } main(int argc, char *argv[]) { NODE v; getdata(argc,argv); label=0; for (v=1; v<=n; v++) val[v]=0; for (v=1; v<=n; v++) if (val[v] == 0) DFS(v); } Mar 12 '07 #3

 P: 5 hi u need code in which programming language? i am sending you the pseudocode, you can change this to any programming language easily just by applying the syntax of that particular language. dfs(v) process(v) mark v as visited for all vertices i adjacent to v not visited dfs(i) another version dfs(graph G) { list L = empty tree T = empty choose a starting vertex x search(x) while(L is not empty) remove edge (v, w) from end of L if w not yet visited { add (v, w) to T search(w) } } search(vertex v) { visit v for each edge (v, w) add edge (v, w) to end of L } there is a small version of it in C programming language take a look at it typedef int NODE; int A[MAX][MAX], B[MAX][MAX]; int n, label, val[MAX]; void DFS(NODE v){ NODE w; val[v] = ++label; for (w=1; w<=n; w++){ if (A[v][w] != 0) if (val[w] == 0) { B[v][w] = 1; DFS(w); } } } main(int argc, char *argv[]) { NODE v; getdata(argc,argv); label=0; for (v=1; v<=n; v++) val[v]=0; for (v=1; v<=n; v++) if (val[v] == 0) DFS(v); } nice psuedo code Mar 12 '07 #4 