Graph Traversal Depth First Traversal using c program

Data Structures using C Language / Graph Traversal Depth First Traversal using c program

Program

#include <stdio.h>
#include <stdlib.h>
struct node {
int vertex;
struct node* next;
};
struct node* create_Node(int v);

struct Graph {
int Verticescount;
int* visited;
struct node** adjacentLists;
};

void DFS(struct Graph* graph, int vertex) {
struct node* adjList = graph->adjacentLists[vertex];
struct node* temp = adjList;

graph->visited[vertex] = 1;
printf("Visited %d \n", vertex);

while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) 
DFS(graph, connectedVertex);
temp = temp->next;
}
}

struct node* create_Node(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->Verticescount = vertices;
graph->adjacentLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));

int i;
for (i = 0; i < vertices; i++) {
graph->adjacentLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
void addEdge(struct Graph* graph, int src, int dest) {
struct node* newNode = create_Node(dest);
newNode->next = graph->adjacentLists[src];
graph->adjacentLists[src] = newNode;
newNode = create_Node(src);
newNode->next = graph->adjacentLists[dest];
graph->adjacentLists[dest] = newNode;
}

void showGraph(struct Graph* graph) {
int v;
for (v = 0; v < graph->Verticescount; v++) {
struct node* temp = graph->adjacentLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}printf("\n");
}
}

int main() {
struct Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
showGraph(graph);
DFS(graph, 2);
return 0;
}

Output

Adjacency list of vertex 0
2 -> 1 -> 
Adjacency list of vertex 1
2 -> 0 -> 
Adjacency list of vertex 2
3 -> 1 -> 0 -> 
Adjacency list of vertex 3
2 -> 
Visited 2 
Visited 3 
Visited 1

Home Back