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:

TraversalMeaningMethod
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

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.

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.

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

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more