Thread: C program

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    1
    Rep Power
    0

    C program


    Hi, guys
    I really wanna understand how this code works

    ----------------
    it's a program to implement depth first search


    #include<stdio.h>
    #define MAX 5

    int dfs(int adj[][MAX], int visited[], int start)
    {
    int stack[MAX];
    int top=-1,i;
    printf("%c-",start+65);
    visited[start]=1;
    stack[++top]=start;

    while(top!=-1)
    {

    start=stack[top];
    for(i=0;i<MAX;i++)
    {
    if(adj[start][i]&&visited[i]==0)
    {
    stack[++top]=i;
    printf("%c-",i+65);
    visited[i]=1;
    break;
    }
    }
    if(i==MAX)
    top--;
    }
    return 0;
    }

    int main()
    {
    Int adj[MAX][MAX]={{0,0,1,1,0},{0,0,0,0,0},{0,1,0,1,1},{0,0,0,0,1},{0,0,0,1,0}};
    int visited[MAX]={0};
    printf("DFS Traversal : ");
    dfs(adj,visited,0);
    printf("\n");
    return 0;
    }

    I would be grateful if you helped me!!!
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,703
    Rep Power
    480
    The adjacency matrix stores the graph.
    Code:
            To
          a b c d e
         +---------
        a|0 0 1 1 0
     f  b|0 0 0 0 0
     r  c|0 1 0 1 1
     o  d|0 0 0 0 1
     m  e|0 0 0 1 0
    where a 1 indicates a directed connection of nodes. The matrix isn't symmetric.

    The stack holds the frontier---the list of the nodes accessible from nodes visited. But because of the break statement the stack gets only the next node on the frontier. And continues with the new start position. Eventually the stack pops back when the code can continue to look for additional nodes on the frontier of a previous start node.
    Last edited by b49P23TIvg; March 26th, 2013 at 12:13 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,074
    Rep Power
    1802
    Originally Posted by fun girl
    I really wanna understand how this code works
    The best way to do that is to single-step the code in your debugger.

    You could learn the fundamentals of the debugger - stepping, watching, and breakpoints in about the time you spent posting this question and reading the answers, but the lesson will pay back many times over in code debugging, testing and comprehension. The return on investment will easily break-even the first time you use it on this code in that say it took you an hour to figure it out manually, with half an hour debugger familiarisation, it will then take you less than half an hour to achieve the same level of comprehension with the debugger, and next time you already know how to use the debugger.

IMN logo majestic logo threadwatch logo seochat tools logo