The Royal Coding
Binary Search Bubble Sort Build A Max Heap Build A Min Heap Graph Traversal Heap Sort Implementing A Basic Hash Table Implementing A Binary Search Tree Implementing A Queue Implementing A Stack Insertion Sort Length Of Linked List Linear Search Linked Lists Merge A Two Sorted Linked List Merge Sort Quick Sort Redix Sort Reverse A Linked List Selection Sort Ternary Search Suffix Automata Construction

Python/C/C++/JAVA

Advanced Practice Programs with Code and Concept

By D.S

Graph Traversals

In programming, graph traversals refer to the process of visiting and exploring every vertex or node in a graph data structure. C is a highly efficient and popular programming language that provides numerous methods for implementing graph traversals, including depth-first search (DFS) and breadth-first search (BFS). DFS involves examining each neighboring vertex recursively until all vertices have been explored, while BFS visits every neighbor of a given vertex before moving on to its neighbors' neighbors. Graph traversals by C require careful planning and implementation since they are intricate algorithms that can consume significant time and resources.

(a.) C Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

struct Graph {
    int adj[MAX][MAX];
    int visited[MAX];
    int n;
};

void DFS(struct Graph* graph, int start) {
    printf("%d ", start);
    graph->visited[start] = 1;
    for (int i = 0; i < graph->n; i++) {
        if (graph->adj[start][i] == 1 && !graph->visited[i]) {
            DFS(graph, i);
        }
    }
}

void BFS(struct Graph* graph, int start) {
    int queue[MAX], front = -1, rear = -1;
    printf("%d ", start);
    graph->visited[start] = 1;
    queue[++rear] = start;

    while (front != rear) {
        start = queue[++front];
        for (int i = 0; i < graph->n; i++) {
            if (graph->adj[start][i] == 1 && !graph->visited[i]) {
                printf("%d ", i);
                graph->visited[i] = 1;
                queue[++rear] = i;
            }
        }
    }
}

int main() {
    struct Graph graph;
    graph.n = 4;
    int adjacency_matrix[4][4] = {{0, 1, 1, 0},
                                  {1, 0, 1, 1},
                                  {1, 1, 0, 0},
                                  {0, 1, 0, 0}};
    for (int i = 0; i < graph.n; i++) {
        for (int j = 0; j < graph.n; j++) {
            graph.adj[i][j] = adjacency_matrix[i][j];
        }
        graph.visited[i] = 0;
    }

    printf("Depth First Traversal (DFS): ");
    DFS(&graph, 2);
    printf("\n");

    for (int i = 0; i < graph.n; i++) {
        graph.visited[i] = 0;
    }

    printf("Breadth First Traversal (BFS): ");
    BFS(&graph, 2);
    printf("\n");

    return 0;
}
Output:-
Depth First Traversal (DFS): 2 0 1 3
Breadth First Traversal (BFS): 2 0 3 1

(b.) C++ Code

#include <iostream>
#include <list>
using namespace std;

class Graph {
    int V;
    list<int>* adj; // Correct: specify type
    void DFSUtil(int v, bool visited[]);
public:
    Graph(int V);
    void addEdge(int v, int w);
    void DFS(int v);
    void BFS(int s);
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V]; // Correct: list<int>
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::DFSUtil(int v, bool visited[]) {
    visited[v] = true;
    cout << v << " ";
    list<int>::iterator i; // Correct: list<int>
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

void Graph::DFS(int v) {
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
    DFSUtil(v, visited);
    delete[] visited;
}

void Graph::BFS(int s) {
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    list<int> queue; // Correct: list<int>
    visited[s] = true;
    queue.push_back(s);

    while (!queue.empty()) {
        s = queue.front();
        cout << s << " ";
        queue.pop_front();

        for (int adjacent : adj[s]) {
            if (!visited[adjacent]) {
                visited[adjacent] = true;
                queue.push_back(adjacent);
            }
        }
    }
    delete[] visited;
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    cout << "Depth First Traversal (DFS): ";
    g.DFS(2);
    cout << endl;

    cout << "Breadth First Traversal (BFS): ";
    g.BFS(2);
    cout << endl;

    return 0;
}
Output:-
Depth First Traversal (DFS): 2 0 1 3
Breadth First Traversal (BFS): 2 0 3 1

(c.) Python Code

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def DFSUtil(self, v, visited):
        visited.add(v)
        print(v, end=' ')
        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self.DFSUtil(neighbour, visited)

    def DFS(self, v):
        visited = set()
        self.DFSUtil(v, visited)

    def BFS(self, s):
        visited = [False] * (max(self.graph) + 1)
        queue = []
        queue.append(s)
        visited[s] = True
        while queue:
            s = queue.pop(0)
            print(s, end=' ')
            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

# Driver code
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print("Depth First Traversal (DFS): ", end='')
g.DFS(2)

print("\nBreadth First Traversal (BFS): ", end='')
g.BFS(2)
Output:-
Depth First Traversal (DFS): 2 0 1 3
Breadth First Traversal (BFS): 2 0 3 1

(d.) Java Code

import java.util.*;

class Graph {
    private int V;
    private LinkedList[] adj;

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");
        Iterator i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    void DFS(int v) {
        boolean[] visited = new boolean[V];
        DFSUtil(v, visited);
    }

    void BFS(int s) {
        boolean[] visited = new boolean[V];
        LinkedList queue = new LinkedList<>();
        visited[s] = true;
        queue.add(s);

        while (!queue.isEmpty()) {
            s = queue.poll();
            System.out.print(s + " ");
            Iterator i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.print("Depth First Traversal (DFS): ");
        g.DFS(2);
        System.out.println();
        System.out.print("Breadth First Traversal (BFS): ");
        g.BFS(2);
    }
}
Output:-
Depth First Traversal (DFS): 2 0 1 3
Breadth First Traversal (BFS): 2 0 3 1

How did you feel about this post?

😍 🙂 😐 😕 😡

Was this helpful?

👍 👎