Depth First search in C C++/Java Style

depth-first-search.c

#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;
}