Depth First Search algorithm in general terms


************************************************

Input :
     Un weighted graph
     Beginning vertex -v
Output :
     The visited vertices.
Data structures used :Stack to store the vertices
************************************************

ALGORITHM:

1)Lable vertex v as reached.
2)Initialize S to be a stack with only v in it.
3)while S is not empty repeate through steps 4 , 5 & 6.
4)Delete a vertex w from the stack.
5)for all vertices u adjacent from w repeate through steps 6.
6)if u has not been labeled add u to the stack S , lable u as reached.

3 thoughts on “Depth First Search algorithm in general terms”

  1. /****************************************
    APPLICATION : Depth First Search (DFS)
    CODED BY : Ankit Pokhrel
    COMPILED ON : Borland C++ Ver 5.02
    DATE : 2010 – October – 12
    ****************************************/

    #include
    #include

    struct Node //Structure to represent a Node or Vertices of a Graph
    {
    int status;
    char data;
    struct Node *next,*head; //Pointers to next node and Start
    struct Adjacent *adj; //Pointer to Adjacent node
    };

    struct Adjacent //Structure to represent Adjacent node of a Graph
    {
    struct Node *next;
    struct Adjacent *adj; //Pointer for next Adjacent
    };

    Node *New,*top; //Global Variables for New node and Pointer to Top
    void create()
    {
    New = new Node; //Create a node
    New -> status = false;
    New -> next = NULL;
    New -> adj = NULL;
    }

    void CreateVertices(Node *&n,char Item) //Function to Create a Vertices of a Graph
    {
    if(n == NULL) //if first node
    {
    n = new Node; //Create a node
    n -> data = Item; //Insert Data
    n -> status = false;
    n -> next = NULL;
    n -> adj = NULL;
    n -> head = n; //Initialize head
    top = n; //Update top
    return;
    }

    create(); //Create a node
    New -> data = Item; //Insert Item
    top -> next = New; //Assign new node to next of top
    top = New; //Update top
    }

    void LinkVertices(Node *&n)
    {
    Adjacent *a,*ptr;
    cout < head,*tmp;
    while(temp != NULL) //Until last
    {
    cout << "\nEnter Adjacents of " < data <> ch; //Scan Adjacent
    a = new Adjacent; //Create an Adjacent
    a -> adj = NULL;
    a -> next = NULL;
    if(flag == 0) //if first Adjacent
    {
    temp -> adj = a;
    ptr = a;
    flag++; //Increase flag
    }

    else
    {
    ptr -> adj = a;
    ptr = a;
    }

    tmp = n -> head; //from start
    while(tmp != NULL) //Until end
    {
    if(tmp -> data == ch) //if node found
    a -> next = tmp; //Link adjacent
    tmp = tmp -> next;
    }
    }while(ch != ‘0’);
    temp = temp -> next;
    }
    }

    void DFS(Node *n,char Item)
    {
    int top = -1;
    char stack[30]; //Create a Stack
    stack[++top] = Item; //Push starting Item
    cout << Item <= 0) //until stack is empty
    {
    temp = n;
    while(temp -> data != ch) //goto starting node
    temp = temp -> next;
    temp -> status = true; //update status

    Adjacent *a = temp -> adj;
    while(a -> adj != NULL)
    {
    tmp = a -> next;
    if(tmp -> status == false)
    {
    stack[++top] = tmp -> data; //save adjacents to stack
    tmp -> status = true; //update status
    }
    a = a -> adj; //goto next adjacent
    }

    ch = stack[top];
    if(top != 0)
    cout << stack[top] << ' '; //output top of stack
    –top;
    }
    }

    int main()
    {
    int m;
    char ch;
    Node *nd = NULL;
    cout <> m;

    cout << "\nEnter Vertices Name : "; //Input the name of Vertices
    for(int i = 0;i > ch;
    CreateVertices(nd,ch); //Create Vertices of a Graph
    }

    LinkVertices(nd); //Link the Vertices of a Graph
    cout <> ch;
    cout << "\nThe nodes reachable from " << ch << " : ";
    DFS(nd,ch); //Depth First Traversal
    getch();
    }

    OUTPUT
    ———
    How Many Vertices? 9

    Enter Vertices Name : A B C D E F G J K

    Enter Link for each Vertices (0 as Last Input):
    Enter Adjacents of A : F C B 0
    Enter Adjacents of B : G C 0
    Enter Adjacents of C : F 0
    Enter Adjacents of D : C 0
    Enter Adjacents of E : D C J 0
    Enter Adjacents of F : D 0
    Enter Adjacents of G : C E 0
    Enter Adjacents of J : D K 0
    Enter Adjacents of K : E G 0

    Find nodes reachable from : J

    The nodes reachable from J : J K G C F E D

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s