Skip to content

Instantly share code, notes, and snippets.

@djassie
Created March 18, 2024 12:15
Show Gist options
  • Save djassie/563c4dfdacd3ab656f8432b829b3f6f7 to your computer and use it in GitHub Desktop.
Save djassie/563c4dfdacd3ab656f8432b829b3f6f7 to your computer and use it in GitHub Desktop.
Depth First search in C C++/Java Style
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node node;
struct node {
int data;
node *next;
};
typedef struct {
node *head;
node *tail;
} list;
typedef struct {
int vertices;
list *arr;
} graph;
node *createNode(int d) {
node *nNode = (node *)malloc(sizeof(node));
nNode->data = d;
return nNode;
}
graph *createGraph(int vertices) {
graph *gGraph = (graph *)malloc(sizeof(graph));
gGraph->vertices = vertices;
gGraph->arr = (list *)malloc(vertices * sizeof(list));
for (int i = 0; i < vertices; i++) {
gGraph->arr[i].head = NULL;
gGraph->arr[i].tail = NULL;
}
return gGraph;
}
void addEdge(graph *gGraph, int src, int dest) {
if (gGraph->arr[src].head == NULL) {
node *newNode = createNode(dest);
gGraph->arr[src].head = newNode;
gGraph->arr[src].tail = newNode;
} else {
node *newNode = createNode(dest);
node *lastNode = gGraph->arr[src].tail;
lastNode->next = newNode;
gGraph->arr[src].tail = newNode;
}
}
void DFS(graph *gGraph, int vertex, int visited[]) {
visited[vertex] = 1;
printf("%d\n", vertex);
node *currentNode = gGraph->arr[vertex].head;
while (currentNode) {
int adjacentVertex = currentNode->data;
if (visited[adjacentVertex] != 1) {
DFS(gGraph, adjacentVertex, visited);
}
currentNode = currentNode->next;
}
}
void DFSTraversal(graph *graph, int origin) {
int *visited = (int *)malloc(graph->vertices * sizeof(int));
for (int i = 0; i < graph->vertices; i++) {
visited[i] = 0;
}
DFS(graph, origin, visited);
}
int main() {
int vertices = 4;
graph *gg = createGraph(vertices);
addEdge(gg, 2, 0);
addEdge(gg, 0, 2);
addEdge(gg, 1, 2);
addEdge(gg, 0, 1);
addEdge(gg, 3, 3);
addEdge(gg, 1, 3);
//to add additional vertex, update vertices number
// addEdge(gg, 0, 4);
// addEdge(gg, 4, 4);
// addEdge(gg, 0, 5);
// addEdge(gg, 5, 6);
// addEdge(gg, 6, 6);
/**
4←---0
/\↗
/ \\
↙ ↙\
1-----→2----→3
*/
int origin = 2;
DFSTraversal(gg, origin);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment