Advertisement
AsimKPrasad

DFS using linked lists in C

Nov 23rd, 2014
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.14 KB | None | 0 0
  1. /*
  2.  
  3.     Author :    Asim Krishna Prasad
  4.  
  5.     Program to implement DFS using linked lists in C..
  6.  
  7. */
  8.  
  9. #include<stdio.h>
  10. #include<stdlib.h>
  11.  
  12. #define scan(a)     scanf("%d", &a)
  13. #define print(a)    printf("%d", a)
  14. #define nline       printf("\n")
  15. #define fl(i,a,b)   for(i=a; i<b; i++)
  16. #define rev(i,a,b)  for(i=a; i>=b; i--)
  17. #define sspace      printf(" ")
  18.  
  19. typedef struct listnode
  20. {
  21.     int data;
  22.     struct listnode* next;
  23. }listnode;
  24.  
  25. typedef struct list
  26. {
  27.     listnode *head;
  28. }list;
  29.  
  30. typedef struct graph
  31. {
  32.     int vertices;
  33.     list* array;
  34. }graph;
  35.  
  36. int visited[1000];
  37.  
  38. graph* creategraph(int n)
  39. {
  40.     int i;
  41.     graph* G=(graph *)(malloc(sizeof(graph)));
  42.     G->vertices = n;
  43.    
  44.     G->array = (list *)malloc(n * sizeof(struct list));
  45.    
  46.     fl(i,0,n)
  47.         G->array[i].head = NULL;
  48.     return G;
  49. }
  50.  
  51. void addedge(graph* G, int src, int dest)
  52. {
  53.     listnode* newnode;
  54.     newnode=(listnode *)(malloc(sizeof(listnode)));
  55.     newnode->data=dest;
  56.     newnode->next=G->array[src].head;
  57.     G->array[src].head=newnode;
  58. }
  59.  
  60. void traverse(graph* G, int n)
  61. {
  62.     graph* temp=G;
  63.     int i;
  64.     list* temp_list;
  65.     listnode* temp_node;
  66.     fl(i,0,n)
  67.     {
  68.         temp_node=temp->array[i].head;
  69.         while(temp_node!=NULL)
  70.         {
  71.             printf("%d -> %d\t", i, temp_node->data);
  72.             temp_node=temp_node->next;
  73.         }
  74.         nline;
  75.     }
  76.     return;
  77. }
  78.  
  79. void dfs(graph* G, int v)
  80. {
  81.     int i, j;
  82.     printf("%d ", v);
  83.     visited[v]=1;
  84.     listnode* temp_node=G->array[v].head;
  85.     while(temp_node!=NULL)
  86.     {
  87.         if(!visited[temp_node->data])
  88.         {
  89.             //Uncomment the line below to understand the DFS traversal
  90.             //printf("\tMoving from %d to %d", v, temp_node->data);nline;
  91.             dfs(G,temp_node->data);
  92.         }
  93.            
  94.         temp_node=temp_node->next;
  95.     }
  96.     return;
  97. }
  98.  
  99. int main()
  100. {
  101.     int n, i, j, k, temp, m, a, b;
  102.     printf("Enter the number of nodes : ");
  103.     scan(n);
  104.     printf("Enter the number of edges : ");
  105.     scan(m);
  106.     printf("Enter the edges : "); nline;
  107.     int ini=n+1;
  108.     graph* G=creategraph(n+1);
  109.     fl(i,0,m)
  110.     {
  111.         scan(a); scan(b);
  112.         addedge(G,a,b);
  113.         if(a<ini)
  114.             ini=a;
  115.     }
  116.     printf("Traversing the adjacency list : ");
  117.     nline;
  118.     traverse(G,n);
  119.     nline;
  120.  
  121.     printf("DFS traversal starting with %d : ", ini);nline;
  122.     dfs(G,ini);
  123.     nline;
  124.     return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement