Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Performs a Depth First Search on a Graph
/**
Code for https://journaldev.com article
Purpose: A Depth First Search Implementation
@author: Vijay Ramachandran
@date: 14-02-2020
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Graph Graph;
typedef struct Node Node;
struct Node {
// To represent the linked list node.
// Contains the vertex index
int vertex;
// Vertex Key
int key;
// And a pointer to the next element in the linked list
Node* next;
};
struct Graph {
// Key List
int* key_list;
// Number of vertices
int v;
// Array of Adjacency Lists
Node** adj_lists;
};
// Define the Stack here
typedef struct StackNode StackNode;
struct StackNode{
// Stack of integers
int data;
StackNode* next;
};
int is_empty(StackNode* stack) {
// Check if stack is empty
if (!stack)
return 1;
return 0;
}
StackNode* push(StackNode* stack, int data) {
// Pushes the data into the stack
StackNode* node = (StackNode*) malloc (sizeof(StackNode));
StackNode* temp = stack;
node->data = data;
node->next = temp;
stack = node;
return stack;
}
StackNode* pop(StackNode* stack) {
// Pops the head of the stack
if (!stack)
return NULL;
StackNode* temp = stack;
stack = stack->next;
temp->next = NULL;
free(temp);
return stack;
}
int top(StackNode* stack) {
// Return the top of the stack
if (!stack)
return INT_MIN;
return stack->data;
}
StackNode* init_stack(int data) {
// Initializes the stack
StackNode* stack = (StackNode*) malloc (sizeof(StackNode));
stack->data = data;
stack->next = NULL;
return stack;
}
void free_stack(StackNode* stack) {
// Free the stack
if (!stack)
return;
StackNode* temp = stack;
stack = stack->next;
temp->next = NULL;
free(temp);
free_stack(stack);
}
void print_stack(StackNode* stack) {
if (!stack)
return;
StackNode* temp = stack;
printf("Stack: \n");
while(temp) {
printf("Data: %d -> ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Adjacency Lists for the Graph
Node** init_adjacency_lists(Graph g) {
// Initializes an adjacency matrix for the graph
if (g.adj_lists)
return g.adj_lists;
// Allocates memory for the lists
// There is a list for every vertex in the graph
// which means there are g.v adjacent lists
Node** adj_lists = (Node**) calloc (g.v, sizeof(Node*));
// Set them to NULL initially
for (int i = 0; i < g.v; i++)
adj_lists[i] = NULL;
printf("Initialized Adjacency Lists!\n");
return adj_lists;
}
void free_list(Node* list) {
// Frees all nodes in the list, headed by 'list'
Node* temp = list;
while(temp) {
Node* rm_node = temp;
temp = rm_node->next;
rm_node->next = NULL;
free(rm_node);
}
}
void free_adj_lists(Graph g) {
// Free the adjacency matrix
if (!g.adj_lists)
return;
for (int i=0; i<g.v; i++)
free_list(g.adj_lists[i]);
free(g.adj_lists);
}
void print_list(Node* list) {
// Prints the linked list
Node* temp = list;
while(temp) {
printf("Node: %d, Key: %d -> ", temp->vertex, temp->key);
temp = temp->next;
}
printf("\n");
}
Node* create_node(int vertex, int key) {
// Creates a LinkedList node to hold the vertex
Node* node = (Node*) calloc (1, sizeof(Node));
node->next = NULL;
node->vertex = vertex;
node->key = key;
return node;
}
void add_edge(Graph g, int i, int j) {
// Adds an edge connecting two vertices i and j
if (!g.adj_lists) {
fprintf(stderr, "Adjacency Lists not initialized!\n");
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Number\n");
exit(1);
}
// Create the new node in the souce vertex
// adjacency list and add the destination
// vertex to it
// Create a node containing the dst vertex index
Node* node = create_node(j, g.key_list[j-1]);
// Insert at the source list
// Let's insert at the top, since it doesn't
// matter whether we insert at the head or not
node->next = g.adj_lists[i-1];
// Make the new node as the head
g.adj_lists[i-1] = node;
}
void remove_edge(Graph g, int i, int j) {
// Sets the edge from i to j as zero
if (!g.adj_lists) {
fprintf(stderr, "Adjacency Lists not initialized!\n");
exit(1);
}
// Search for vertex j in i's adjacency list
Node* temp = g.adj_lists[i-1];
if (!temp) {
return;
}
if (!(temp->next)) {
if (temp->vertex == j) {
free(temp);
g.adj_lists[i-1] = NULL;
}
return;
}
while (temp->next) {
if (temp->vertex == j) {
// We have found an edge! Remove this element.
Node* rm_node = temp;
temp->next = rm_node->next;
rm_node->next = NULL;
free(rm_node);
return;
}
temp = temp->next;
}
// No element found :(
return;
}
int check_if_exists(Graph g, int i, int j) {
// Checks if there is an edge from vertex i to j
if (!g.adj_lists) {
fprintf(stderr, "Adjacency Lists not initialized!\n");
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Number\n");
return 0;
}
// Search for vertex j in i's adjacency list
Node* temp = g.adj_lists[i-1];
if (!temp) {
return 0;
}
if (!(temp->next)) {
if (temp->vertex == j) {
return 1;
}
return 0;
}
while (temp->next) {
if (temp->vertex == j) {
// We have found an edge! Remove this element.
return 1;
}
temp = temp->next;
}
// No element found :(
return 0;
}
int DFS_recursive(Graph g, int start_vertex, int key, StackNode** stack, int* visited_list, int start) {
// Recursive DFS function that is used to perform DFS()
if (start)
*stack = push(*stack, g.key_list[start_vertex-1]);
printf("Current Node: key: %d\n", g.key_list[start_vertex - 1]);
// Mark the current node as visited
visited_list[start_vertex - 1] = 1;
// While the stack is not empty
while (!is_empty(*stack)) {
if (g.key_list[start_vertex - 1] == key) {
return 1;
}
else {
// Not found. Go to the next node
Node* node = g.adj_lists[start_vertex - 1];
if (!node) {
// Dead End. Go back after popping current node
*stack = pop(*stack);
}
while (node) {
// If any of it's neighbours are not visited
if(visited_list[node->vertex - 1] == 0) {
// Go to that node and do a DFS from that node
if (DFS_recursive(g, node->vertex, key, stack, visited_list, 1) == 1)
return 1;
else {
// Pop the recently visited neighbour from the stack
*stack = pop(*stack);
}
}
node = node->next;
}
}
}
return 0;
}
int DFS(Graph g, int start_vertex, int key) {
// Performs a DFS on the Graph from start_vertex
// and returns 1 if the destination key is found
printf("Start Vertex: %d, Key: %d\n", start_vertex, g.key_list[start_vertex - 1]);
if (g.key_list[start_vertex-1] == key) {
return 1;
}
// Keep a visited list of nodes
int* visited_list = (int*) calloc (g.v, sizeof(int));
// Initialize the Stack
StackNode* stack = init_stack(g.key_list[start_vertex-1]);
// Perform the DFS
int ret_val = DFS_recursive(g, start_vertex, key, &stack, visited_list, 0);
// Free Stuff and exit
free_stack(stack);
free(visited_list);
return ret_val;
}
void dfs_print(Graph g, int src, int dst) {
// Find the vertex for the src key
int start = -1;
for (int i=0; i<g.v; i++) {
if (g.key_list[i] == src)
start = i + 1;
}
if (start == -1) {
fprintf(stderr, "Error: Key %d not found\n", src);
return;
}
printf("Performing DFS on the Graph...\n");
int ret_val = DFS(g, start, dst);
if (ret_val == 1)
printf("Key: %d is found!\n", dst);
else
printf("Key: %d is not found.\n", dst);
}
int main() {
// Graph with 6 vertices
int vertex_list[] = {6, 2, 5, 14, 7, 1};
Graph g = {vertex_list, 6, NULL};
printf("Created a Graph Structure with %d vertices\n", g.v);
g.adj_lists = init_adjacency_lists(g);
// Let's connect the 6 vertices using edges
add_edge(g, 1, 2);
add_edge(g, 1, 3);
add_edge(g, 2, 4);
add_edge(g, 2, 5);
add_edge(g, 3, 6);
add_edge(g, 6, 5);
// Print the Adjacency Lists
for (int i=0; i<g.v; i++) {
printf("Vertex: %d , Key: %d => ", i+1, g.key_list[i]);
print_list(g.adj_lists[i]);
}
// Print a Depth First Search from 6 to 14
printf("\n");
dfs_print(g, 6, 7);
printf("\n");
dfs_print(g, 6, 8);
printf("\n");
dfs_print(g, 6, 14);
printf("\n");
free_adj_lists(g);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment