Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Author : Asim Krishna Prasad
- Program to implement DFS using linked lists in C..
- */
- #include<stdio.h>
- #include<stdlib.h>
- #define scan(a) scanf("%d", &a)
- #define print(a) printf("%d", a)
- #define nline printf("\n")
- #define fl(i,a,b) for(i=a; i<b; i++)
- #define rev(i,a,b) for(i=a; i>=b; i--)
- #define sspace printf(" ")
- typedef struct listnode
- {
- int data;
- struct listnode* next;
- }listnode;
- typedef struct list
- {
- listnode *head;
- }list;
- typedef struct graph
- {
- int vertices;
- list* array;
- }graph;
- int visited[1000];
- graph* creategraph(int n)
- {
- int i;
- graph* G=(graph *)(malloc(sizeof(graph)));
- G->vertices = n;
- G->array = (list *)malloc(n * sizeof(struct list));
- fl(i,0,n)
- G->array[i].head = NULL;
- return G;
- }
- void addedge(graph* G, int src, int dest)
- {
- listnode* newnode;
- newnode=(listnode *)(malloc(sizeof(listnode)));
- newnode->data=dest;
- newnode->next=G->array[src].head;
- G->array[src].head=newnode;
- }
- void traverse(graph* G, int n)
- {
- graph* temp=G;
- int i;
- list* temp_list;
- listnode* temp_node;
- fl(i,0,n)
- {
- temp_node=temp->array[i].head;
- while(temp_node!=NULL)
- {
- printf("%d -> %d\t", i, temp_node->data);
- temp_node=temp_node->next;
- }
- nline;
- }
- return;
- }
- void dfs(graph* G, int v)
- {
- int i, j;
- printf("%d ", v);
- visited[v]=1;
- listnode* temp_node=G->array[v].head;
- while(temp_node!=NULL)
- {
- if(!visited[temp_node->data])
- {
- //Uncomment the line below to understand the DFS traversal
- //printf("\tMoving from %d to %d", v, temp_node->data);nline;
- dfs(G,temp_node->data);
- }
- temp_node=temp_node->next;
- }
- return;
- }
- int main()
- {
- int n, i, j, k, temp, m, a, b;
- printf("Enter the number of nodes : ");
- scan(n);
- printf("Enter the number of edges : ");
- scan(m);
- printf("Enter the edges : "); nline;
- int ini=n+1;
- graph* G=creategraph(n+1);
- fl(i,0,m)
- {
- scan(a); scan(b);
- addedge(G,a,b);
- if(a<ini)
- ini=a;
- }
- printf("Traversing the adjacency list : ");
- nline;
- traverse(G,n);
- nline;
- printf("DFS traversal starting with %d : ", ini);nline;
- dfs(G,ini);
- nline;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement