11月 14, 2010

DFS and BFS

DFS(x)   /* O(n+e) , O(n^2) */
{
node *ptr;
visit[x] = true;
ptr = A[x]->next;

while (ptr != NULL)
{
if (visit[ptr->data] == false)
{ DFS(ptr->data); }

ptr=ptr->next;
}
}

BFS(x) /* O(n+e) , O(n^2) */
{
visit[ ]=false; /* init */

visit[x]= true;
ENQUEUE(x);

while (Q != empty)
{
v = DEQUEUE(Q);

for (w, each neighbor of v)
{ if (visit[w] != true)
{ ENQUEUE(w); visit[w]=true; }
}
}
}

沒有留言:

張貼留言