By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,389 Members | 1,857 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
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

sangeetha jagannathan
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

Post your reply

Sign in to post your reply or Sign up for a free account.