Graphs | CSE205 : DATA STRUCTURES AND ALGORITHMS | B.Tech CSE

Graph | BFS | DFS | Warshall Algorithm | Floyd–Warshall Algorithm

⭐Breadth First Search(BFS)

1) BFS (matrix):

CODE:

#include <iostream>
#include <queue>
using namespace std;
// Define a constant for the maximum number of vertices
#define MAX_VERTICES 100

// Function to add an edge to the adjacency matrix of an undirected graph
void addEdge(int adj[MAX_VERTICES][MAX_VERTICES], int v1, int v2) {
    adj[v1][v2] = 1;  // Mark the edge from v1 to v2
    adj[v2][v1] = 1;  // Since the graph is undirected, also mark the reverse
}

// Function to sort an array using bubble sort
void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            // swap
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// Function to perform Breadth-First Search (BFS)
void BFS(int adj[MAX_VERTICES][MAX_VERTICES], int totalVertices, int startVertex) {
    int visited[MAX_VERTICES] = {0};  // Array to track visited vertices
    int result[MAX_VERTICES];        // Array to store the BFS traversal order
    int count = 0;            // Index for storing BFS order in the result array
    queue<int> q;                  // Queue to manage vertices for BFS

    visited[startVertex] = 1;      // Mark the start vertex as visited
    q.push(startVertex);           // Enqueue the start vertex

    while (!q.empty()) {
        int currentVertex = q.front();    // Get the vertex at the front of the queue
        q.pop();                          // Remove the vertex from the queue
        result[count++] = currentVertex;  // Store the vertex in the BFS order array

        // Explore all adjacent vertices
        for (int i = 0; i < totalVertices; i++) {
            // If the vertex is connected and not yet visited, enqueue it
            if (adj[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;  // Mark the vertex as visited
                q.push(i);  // Enqueue the adjacent vertex
            }
        }
    }

    // Sort the BFS result array in ascending order using bubble sort
    bubbleSort(result, count);

    // Print the BFS order after sorting
    for (int i = 0; i < count; i++) {
        cout << result[i] << " ";  // Output each vertex in the sorted BFS order
    }
    cout << endl;
}

int main() {
    int totalVertices, totalEdges;
    cin >> totalVertices >> totalEdges;  // Input the number of vertices and edges

    // Initialize the adjacency matrix with 0 (no edges initially)
    int adj[MAX_VERTICES][MAX_VERTICES] = {0};

    // Input all the edges and add them to the adjacency matrix
    for (int i = 0; i < totalEdges; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        addEdge(adj, v1, v2);  // Add the edge to the graph
    }

    // Perform BFS starting from vertex 0
    BFS(adj, totalVertices, 0);

    return 0;
}

INPUT:

6 8

0 1

0 2

1 3

2 3

2 4

3 4

4 5

5 0

OUTPUT:

0 1 2 3 4 5 

2) BFS (MATRIX) Shortest path:

CODE:

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

// Function to add an edge to the adjacency matrix (undirected graph)
void addEdge(int adj[][100], int source, int destination){
    adj[source][destination] = 1;  // Mark the edge from source to destination
    adj[destination][source] = 1;  // Since the graph is undirected, mark the reverse edge as well
}

// Function to perform BFS and find the shortest path from source to destination
bool BFS(int adj[][100], int source, int destination, int numVertices, int predecessors[], int distances[]){
    // Initialize the distances and predecessors arrays
    for (int i = 0; i < numVertices; i++){
        distances[i] = INT_MAX;  // Set all distances to infinity initially
        predecessors[i] = -1;    // Set all predecessors to -1 (indicating no predecessor)
    }

    // Create a queue to hold vertices for BFS traversal
    int queue[100];
    int front = 0, rear = 0;
    queue[rear++] = source;  // Enqueue the source vertex
    distances[source] = 0;   // Set the distance of the source to 0

    // Start BFS loop
    while (front < rear){
        int currentVertex = queue[front++];  // Dequeue a vertex from the front of the queue

        // Explore all adjacent vertices of the current vertex
        for (int i = 0; i < numVertices; i++){
            // If there's an edge from currentVertex to i and i is unvisited
            if (adj[currentVertex][i] == 1 && distances[i] == INT_MAX){
                distances[i] = distances[currentVertex] + 1;  // Update the distance to i
                predecessors[i] = currentVertex;  // Set the predecessor of i
                queue[rear++] = i;  // Enqueue vertex i

                // If destination vertex is found, no need to explore further
                if (i == destination){
                    return true;
                }
            }
        }
    }

    return false;  // Return false if no path is found
}

// Function to print the shortest path and its length from source to destination
void printShortestPath(int adj[][100], int source, int destination, int numVertices, int predecessors[], int distances[]){
    // If no path exists to the destination
    if (distances[destination] == INT_MAX){
        cout << "No path exists between the source and destination." << endl;
        return;
    }

    // Print the shortest path length
    cout << "Shortest path length: " << distances[destination] << endl;

    // Reconstruct the path from destination to source using the predecessors array
    int path[100];
    int pathLength = 0;

    // Backtrack from the destination to the source
    for (int vertex = destination; vertex != -1; vertex = predecessors[vertex]){
        path[pathLength++] = vertex;
    }

    // Print the path in reverse (from source to destination)
    cout << "Path: ";
    for (int i = pathLength - 1; i >= 0; i--){
        cout << path[i];
        if (i > 0){
            cout << " ";
        }
    }
    cout << endl;
}

int main(){
    int numVertices, numEdges;

    // Read the number of vertices and edges
    cin >> numVertices;
    cin >> numEdges;

    // Initialize the adjacency matrix to zero (no edges initially)
    int adj[100][100] = {0};

    // Read all edges and add them to the adjacency matrix
    for (int i = 0; i < numEdges; i++){
        int v1, v2;
        cin >> v1 >> v2;
        addEdge(adj, v1, v2);  // Add the edge to the graph
    }

    // Read the source and destination vertices
    int source, destination;
    cin >> source >> destination;

    // Arrays to store the predecessors and distances for BFS
    int predecessors[numVertices], distances[numVertices];

    // Perform BFS to find the shortest path
    if (BFS(adj, source, destination, numVertices, predecessors, distances)){
        printShortestPath(adj, source, destination, numVertices, predecessors, distances);
    }
    else{
        cout << "No path exists between the source and destination." << endl;
    }

    return 0;
}

INPUT:

6 7

0 1

0 2

1 3

1 4

2 5

3 5 

4 5

0 5

OUTPUT:

Shortest path length: 2

Path: 0 2 5

⭐Depth First Search(DFS)

1) DFS (matrix):

CODE:

#include <iostream>
using namespace std;

#define MAX_VERTICES 100  // Define maximum number of vertices in the graph

// Function to add a directed edge between vertex 'from' and vertex 'to'
void addEdge(int adj[MAX_VERTICES][MAX_VERTICES], int from, int to) {
    adj[from][to] = 1;  // Mark the presence of an edge from 'from' to 'to'
}

// Recursive function to perform Depth First Search (DFS) traversal
void DFS(int adj[MAX_VERTICES][MAX_VERTICES], int visited[MAX_VERTICES], int totalVertices, int currentVertex) {
    cout << currentVertex << " ";  // Print the current vertex as part of the DFS traversal
    visited[currentVertex] = 1;    // Mark the current vertex as visited

    // Explore all adjacent vertices to the current vertex
    for (int i = 0; i < totalVertices; ++i) {
        // If there is an edge to vertex 'i' and 'i' hasn't been visited yet
        if (adj[currentVertex][i] == 1 && !visited[i]) {
            DFS(adj, visited, totalVertices, i);  // Recursively visit the adjacent vertex
        }
    }
}

int main() {
    int totalVertices, totalEdges;
    
    // Input the number of vertices and edges
    cin >> totalVertices >> totalEdges;

    // Initialize adjacency matrix to store graph (0 for no edge, 1 for edge)
    int adj[MAX_VERTICES][MAX_VERTICES] = {0};
    
    // Array to track visited vertices during DFS
    int visited[MAX_VERTICES] = {0};

    // Input edges and populate the adjacency matrix
    for (int i = 0; i < totalEdges; ++i) {
        int fromVertex, toVertex;
        cin >> fromVertex >> toVertex;
        addEdge(adj, fromVertex, toVertex);  // Add edge from 'fromVertex' to 'toVertex'
    }

    // Input the starting vertex for DFS traversal
    int startVertex;
    cin >> startVertex;

    // Display the DFS traversal starting from the given vertex
    cout << "Depth First Traversal starting from vertex " << startVertex << ":\n";
    DFS(adj, visited, totalVertices, startVertex);

    return 0;
}

INPUT:

4 4

0 1

1 2

2 3

3 0

2

OUTPUT:

Depth First Traversal starting from vertex 2:

2 3 0 1 

⭐Warshall Algorithm

1) Warshall (matrix):

CODE:

#include <iostream>
using namespace std;

#define MAX_NODES 100

bool hasChainOfConnections(int n, int connections[MAX_NODES][MAX_NODES], int source, int target) {
    // Applying Warshall's Algorithm to calculate the transitive closure
    int graph[MAX_NODES][MAX_NODES];
    
    // Initialize graph with the given connections matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            graph[i][j] = connections[i][j];
        }
    }
    
    // Warshall's Algorithm to compute transitive closure
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                // If there's a path from i to k and from k to j, then there is a path from i to j
                graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);
            }
        }
    }
    
    // After Warshall's algorithm, check if there's a path from source to target
    return graph[source][target] == 1;
}

int main() {
    int n; // Number of nodes
    cin >> n;

    int connections[MAX_NODES][MAX_NODES] = {0};

    // Taking input for direct connections
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> connections[i][j];
        }
    }

    int source, target;
    cin >> source >> target;

    // Decrement to adjust for 0-based indexing
    source--;
    target--;

    // Check if there's a chain of connections from source to target
    if (hasChainOfConnections(n, connections, source, target)) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    return 0;
}

INPUT:

4

0 1 0 0

0 0 0 1

0 0 0 1

0 0 0 0

2 1

OUTPUT:

No

2)Warshall (graph):

CODE:

#include <iostream>
using namespace std;

// Function to compute the reachability matrix using Warshall's Algorithm
void warshall(int **graph, int n) {
    // Apply Warshall's Algorithm
    for (int k = 0; k < n; ++k) {       // For each intermediate vertex
        for (int i = 0; i < n; ++i) {   // For each source vertex
            for (int j = 0; j < n; ++j) { // For each destination vertex
                if (graph[i][k] == 1 && graph[k][j] == 1) {
                    graph[i][j] = 1; // If there's a path from i to j via k, mark it as reachable
                }
            }
        }
    }
}

int main() {
    int n;
    cin >> n;  // Read the number of vertices in the graph
    int **graph = new int *[n];  // Create an adjacency matrix dynamically
    for (int i = 0; i < n; ++i) {
        graph[i] = new int[n];
    }
    
    // Read the adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];  // Input edges (0 or 1)
        }
    }
    
    // Compute the reachability matrix using Warshall's Algorithm
    warshall(graph, n);
    
    // Output the reachability matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << graph[i][j] << " ";  // Print the reachability matrix
        }
        cout << endl;
    }

    // Clean up dynamically allocated memory
    for (int i = 0; i < n; ++i) {
        delete[] graph[i];
    }
    delete[] graph;

    return 0;
}

INPUT:

4

0 1 0 0

0 0 1 0

0 0 0 1

0 0 0 0

OUTPUT:

0 1 1 1 

0 0 1 1 

0 0 0 1 

0 0 0 0 

⭐Floyd–Warshall Algorithm

1) floydWarshall (matrix):

CODE:

#include <iostream>
using namespace std;

#define INF 1e7
#define MAXN 100

int dis[MAXN][MAXN];   // Distance matrix
int Next[MAXN][MAXN];  // Next matrix to reconstruct the path

// Initializing the distance and Next matrices
void initialise(int V, int graph[MAXN][MAXN]) {
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (graph[i][j] != INF) {
                dis[i][j] = graph[i][j];
                Next[i][j] = j; // Direct path exists, so next to j is j
            } else {
                dis[i][j] = INF;
                Next[i][j] = -1; // No path
            }
        }
    }
    
    // Distance to itself is 0
    for (int i = 0; i < V; ++i) {
        dis[i][i] = 0;
        Next[i][i] = i;
    }
}

// Floyd-Warshall algorithm to compute shortest paths
void floydWarshall(int V) {
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dis[i][j] > dis[i][k] + dis[k][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    Next[i][j] = Next[i][k];  // Update the next vertex in the path
                }
            }
        }
    }
}

// Print the reconstructed path from Earth (source) to the destination
void printPath(int path[], int n) {
    for (int i = 0; i < n; ++i) {
        cout << path[i];
        if (i != n - 1) cout << " -> ";
    }
    cout << endl;
}

int main() {
    int V;  // Number of planets
    cin >> V;

    int graph[MAXN][MAXN];
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cin >> graph[i][j];
        }
    }

    initialise(V, graph);
    floydWarshall(V);

    int source, dest;
    cin >> source >> dest;

    // Reconstruct the path from Earth (source) to destination (dest)
    int path[MAXN];
    path[0] = source;
    int index = 1;
    
    // If no path exists from Earth to the destination
    if (Next[source][dest] == -1) {
        cout << "No path exists from " << source << " to " << dest << endl;
        return 0;
    }
    
    // Reconstruct the path by following the 'Next' matrix
    while (source != dest) {
        source = Next[source][dest];
        path[index++] = source;
    }

    cout << "Shortest path from " << path[0] << " to " << path[index - 1] << ": ";
    printPath(path, index);

    return 0;
}

INPUT:

4

0 3 10000000 7

8 0 2 10000000

5 10000000 0 1

2 10000000 10000000 0

0

2

OUTPUT:

Shortest path from 0 to 2: 0 -> 1 -> 2

2) floydWarshall (graph):

CODE:

#include <iostream>

// Floyd-Warshall algorithm to compute the shortest paths
void floydWarshall(int **graph, int n){
    // Applying the Floyd-Warshall algorithm
    for (int k = 0; k < n; ++k) {  // Intermediate node
        for (int i = 0; i < n; ++i) {  // Source node
            for (int j = 0; j < n; ++j) {  // Destination node
                // Check if the path from i to j can be shortened by going through k
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

int main(void){
    int n, i, j;
    std::cin >> n;
    
    // Dynamically allocate a 2D array to represent the graph
    int **graph = (int **)std::malloc((long unsigned)n * sizeof(int *));
    for (i = 0; i < n; i++){
        graph[i] = (int *)std::malloc((long unsigned)n * sizeof(int));
    }
    
    // Initialize the graph with large values (representing no direct path) and 0s for diagonal (no self-loops)
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            if (i == j){
                graph[i][j] = 0;
            }
            else{
                graph[i][j] = 100;
            }
        }
    }
    
    // Input the graph's edges
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            std::cin >> graph[i][j];
        }
    }

    floydWarshall(graph, n);
    
    // Output the resulting shortest path distances
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            std::cout << graph[i][j] << " ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}

INPUT:

4

0 3 999 4

8 0 2 999

5 999 0 1

2 999 999 0

OUTPUT:

0 3 5 4 

5 0 2 3 

3 6 0 1 

2 5 7 0

---

🚨Thanks for visiting classpdfindia✨

Welcome to a hub for 😇Nerds and knowledge seekers! Here, you'll find everything you need to stay updated on education, notes, books, and daily trends.

💗 Bookmark our site to stay connected and never miss an update!

💌 Have suggestions or need more content? Drop a comment below, and let us know what topics you'd like to see next! Your support means the world to us. 😍