Graph- DFS

 

What is a Graph?

• A Graph is a collection of nodes (called vertices) connected by edges.

• Graphs can be:

  • Undirected (edges have no direction) or

  • Directed (Digraph) (edges have a direction).

• Graphs can be weighted (edges have weights/costs) or unweighted.

How to Represent a Graph in Computers?

Main ways to represent:

1. Adjacency Matrix:

• A 2D array G[V][V] where V = number of vertices.

• G[i][j] = 1 if there is an edge between vertex i and j, else 0.

• Good for dense graphs.

1. Adjacency List:

• An array of lists.

• Each element (vertex) points to a list of vertices it is connected to.

• Good for sparse graphs (uses less memory).

Algorithms for Graph Traversal

Two popular traversals:

Traversal	Meaning	Method
BFS (Breadth-First Search)	Visit neighbors level by level	Queue
DFS (Depth-First Search)	Explore as deep as possible before backtracking	Stack or Recursion

DFS (Depth-First Search) Algorithm

Idea / Intuition

• DFS explores a graph as deeply as possible along each branch before backtracking.

• Works like going into a maze: you follow a path until you hit a dead end, then backtrack and try another path.

Input: Graph, Starting Vertex
Output: Traverse graph deeply

Algorithm (Recursive way):

1. Mark the starting vertex as visited.

2. Process (visit) the vertex.

3. For each adjacent (unvisited) vertex:

• Recursively apply DFS.

Pseudo code:

DFS(v)

    mark v as visited

    for each neighbor u of v:

        if u is not visited:

            DFS(u)

Non-Recursive DFS Algorithm (using Stack)

Input: Graph G (adjacency matrix or list), starting vertex v
Output: Order of traversal

---

Algorithm:

1. Create an empty stack.

2. Push the starting vertex v onto the stack.

3. Mark v as visited.

4. While the stack is not empty:

• Pop a vertex u from the stack.

• Process (visit) vertex u.

• For each adjacent vertex w of u (in reverse order if you want normal DFS order):

• If w is not visited:

• Push w onto the stack.

• Mark w as visited.

Example:

There can be multiple DFS traversals of a graph according to the order in which we pick adjacent vertices. Here we pick vertices as per the insertion order.

Output: [0 1 2 3 4]
Explanation: The source vertex s is 0. We visit it first, then we visit an adjacent.
Start at 0: Mark as visited. Output: 0
Move to 1: Mark as visited. Output: 1
Move to 2: Mark as visited. Output: 2
Move to 3: Mark as visited. Output: 3 (backtrack to 2)
Move to 4: Mark as visited. Output: 4 (backtrack to 2, then backtrack to 1, then to 0)

Not that there can be more than one DFS Traversals of a Graph.

Time Complexity Analysis

Let:

• $V$ = number of vertices

• $E$ = number of edges

Case 1: Adjacency Matrix Representation

• For each vertex, we scan all other vertices in its row → $O(V)$
  

• For $V$ vertices → $O(V^2)$
  

Case 2: Adjacency List Representation

• Each vertex explored once → $O(V)$
  

• Each edge explored once (in undirected, twice) → $O(E)$
  

• Total complexity → $O(V + E)$
  

👉 Adjacency List is preferred for sparse graphs.

---

Space Complexity

• Space for visited array: $O(V)$
  

• Space for recursion/stack: worst-case $O(V)$
  

• Total: $O(V)$
  

C Implementation - Recursive DFS

#include<stdio.h>

int visited[100];

// DFS function (recursive)

void dfs(int adj[10][10], int start, int n) {

    int i;

    printf("%d ", start);

    visited[start] = 1;

    

    for (i = 0; i < n; i++) {

        if (adj[start][i] == 1 && !visited[i])

            dfs(adj, i, n);

    }

}

int main() {

    int n, adj[10][10], i, j, start;

    printf("Enter number of vertices: ");

    scanf("%d", &n);

    

    printf("Enter adjacency matrix:\n");

    for (i=0; i<n; i++)

        for (j=0; j<n; j++)

            scanf("%d", &adj[i][j]);

            

    printf("Enter starting vertex (0 to %d): ", n-1);

    scanf("%d", &start);

    

    printf("DFS Traversal: ");

    dfs(adj, start, n);

    

    return 0;

}

C Implementation - Non Recursive DFS

#include<stdio.h>

int stack[100], top = -1;

int visited[100];

// Push operation

void push(int value) {

    stack[++top] = value;

}

// Pop operation

int pop() {

    if (top == -1)

        return -1;

    else

        return stack[top--];

}

// DFS without recursion

void dfs_non_recursive(int adj[10][10], int start, int n) {

    int i;

    push(start);

    visited[start] = 1;

    printf("DFS Traversal (non-recursive): ");

    

    while (top != -1) {

        int current = pop();

        printf("%d ", current);

        

        for (i = n-1; i >= 0; i--) {  // Traverse neighbors in reverse order

            if (adj[current][i] == 1 && !visited[i]) {

                push(i);

                visited[i] = 1;

            }

        }

    }

}

int main() {

    int n, adj[10][10], i, j, start;

    printf("Enter number of vertices: ");

    scanf("%d", &n);

    

    printf("Enter adjacency matrix:\n");

    for (i=0; i<n; i++)

        for (j=0; j<n; j++)

            scanf("%d", &adj[i][j]);

            

    printf("Enter starting vertex (0 to %d): ", n-1);

    scanf("%d", &start);

    

    dfs_non_recursive(adj, start, n);

    

    return 0;

}

✅ C Program: DFS Traversal in a Graph (Adjacency List)

#include <stdio.h>

#include <stdlib.h>

// Node structure for adjacency list

typedef struct Node {

    int vertex;

    struct Node* next;

} Node;

// Graph structure

typedef struct Graph {

    int numVertices;

    Node** adjLists;

    int* visited;

} Graph;

// Function to create a node

Node* createNode(int v) {

    Node* newNode = (Node*)malloc(sizeof(Node));

    newNode->vertex = v;

    newNode->next = NULL;

    return newNode;

}

// Function to create a graph with V vertices

Graph* createGraph(int vertices) {

    Graph* graph = (Graph*)malloc(sizeof(Graph));

    graph->numVertices = vertices;

    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));

    graph->visited = (int*)malloc(vertices * sizeof(int));

    for (int i = 0; i < vertices; i++) {

        graph->adjLists[i] = NULL;

        graph->visited[i] = 0;

    }

    return graph;

}

// Add an edge (undirected graph)

void addEdge(Graph* graph, int src, int dest) {

    // Add edge src → dest

    Node* newNode = createNode(dest);

    newNode->next = graph->adjLists[src];

    graph->adjLists[src] = newNode;

    // Add edge dest → src

    newNode = createNode(src);

    newNode->next = graph->adjLists[dest];

    graph->adjLists[dest] = newNode;

}

// DFS recursive function

void DFS(Graph* graph, int vertex) {

    Node* temp = graph->adjLists[vertex];

    graph->visited[vertex] = 1;

    printf("%d ", vertex);

    while (temp != NULL) {

        int adjVertex = temp->vertex;

        if (graph->visited[adjVertex] == 0) {

            DFS(graph, adjVertex);

        }

        temp = temp->next;

    }

}

// Driver program

int main() {

    int vertices = 6;

    Graph* graph = createGraph(vertices);

    // Add edges (graph with cycles)

    addEdge(graph, 0, 2);

    addEdge(graph, 0, 1);

    addEdge(graph, 1, 4);

    addEdge(graph, 1, 3);

    addEdge(graph, 2, 4);

    addEdge(graph, 3, 5);

    addEdge(graph, 4, 5);

    printf("DFS Traversal starting from vertex 0:\n");

    DFS(graph, 0);

    return 0;

}

DFS Traversal starting from vertex 0:

0 1 3 5 4 2