Graphs

Graphs are fundamental data structures in computer science and discrete mathematics. They are used to represent pairwise relations between objects. Understanding the theoretical underpinnings of graphs is essential for leveraging their full potential in various applications.

What is a Graph?

A graph G consists of a set of vertices V and a set of edges E connecting pairs of vertices. Formally, a graph is defined as G = (V, E).

Types of Graphs

• Undirected Graphs: In an undirected graph, edges have no direction. If there is an edge between vertices u and v, it can be traversed in both directions.
• Directed Graphs (Digraphs): In a directed graph, edges have a direction. An edge from vertex u to vertex v is denoted as (u, v), indicating the direction from u to v.

Graph Terminology

• Vertex (Node): A fundamental unit of a graph.
• Edge (Link): A connection between two vertices.
• Degree: The number of edges incident to a vertex.
• Path: A sequence of vertices where each adjacent pair is connected by an edge.

Graph Representations

• Adjacency Matrix: A 2D array where matrix[i][j] = 1 if there is an edge from vertex i to vertex j, otherwise 0.
  • Pros: Simple, quick edge existence check.
  • Cons: Memory-intensive for sparse graphs.
• Adjacency List: An array of lists. Each index i contains a list of vertices that are adjacent to vertex i.
  • Pros: Space-efficient for sparse graphs, faster traversal.
  • Cons: Slower edge existence check compared to adjacency matrix.

Graph Implementation Using Adjacency Matrix in C++

Graph implementation using an adjacency matrix in C++ provides a compact and straightforward way to represent graphs. Adjacency matrices are suitable for dense graphs where most vertices are connected, as they offer constant-time edge existence checks.

Creation of the Graph

To create a graph using an adjacency matrix in C++, we define a class that contains the basic attributes and methods required to manage the graph. Below is the initial part of the class definition, including the basic attributes and the constructor.

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

class Graph {
private:
    int V;  // Number of vertices
    vector<vector<int>> adj;  // Adjacency matrix

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V, vector<int>(V, 0)); // Initialize adjacency matrix with all zeros
    }

    // Other methods for graph operations will be added here
};

Attributes Explanation

1. V: This integer variable stores the number of vertices in the graph.

2. adj: This 2D vector serves as the adjacency matrix to represent the connections between vertices. Each element adj[i][j] indicates whether there is an edge from vertex i to vertex j. Initialized with all zeros in the constructor.

Constructor Explanation

The constructor Graph(int vertices) initializes the graph with a specified number of vertices:

• V = vertices: Sets the number of vertices in the graph to the specified value.
• adj.resize(V, vector(V, 0)): Resizes the adjacency matrix to V x V size and initializes all elements to 0, indicating no edges initially.

This setup provides the basic framework for the graph, allowing us to build upon it with additional methods for operations such as adding edges, traversing the graph, and finding shortest paths. The constructor ensures that the graph is properly initialized with the specified number of vertices and is ready for further operations.

Operations on Graph

Operations on graphs involve various tasks such as adding or removing edges, traversing the graph, finding shortest paths, and detecting cycles. Each operation serves a specific purpose in graph manipulation and analysis.

Fundamental operations on graphs include adding and removing edges, which modify the connectivity between vertices.

Adding Edge

Adding an edge to a graph establishes a connection between two vertices, creating a relationship between them.

void addEdge(int u, int v) {
    adj[u][v] = 1;
    // For undirected graphs, uncomment the line below
    // adj[v][u] = 1;
}

Time Complexity: O(1)

Removing Edge

Removing an edge from a graph disconnects two vertices, removing the relationship between them.

void removeEdge(int u, int v) {
    adj[u][v] = 0;
    // For undirected graphs, uncomment the line below
    // adj[v][u] = 0;
}

Time Complexity: O(1)

These fundamental operations allow us to modify the structure of the graph by adding or removing connections between vertices. They are essential building blocks for more complex graph algorithms and operations.

Graph Traversal

Graph traversal involves visiting all the vertices of a graph in a systematic way. Traversal algorithms help explore the structure of the graph and can be used to perform various tasks such as finding paths, detecting cycles, and discovering connected components.

Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a chosen vertex and explores as far as possible along each branch before backtracking.

#include <stack>

void DFS(int start) {
    vector<bool> visited(V, false);
    stack<int> stk;

    stk.push(start);
    visited[start] = true;

    while (!stk.empty()) {
        int v = stk.top();
        stk.pop();
        cout << v << " ";

        for (int i = 0; i < V; ++i) {
            if (adj[v][i] && !visited[i]) {
                visited[i] = true;
                stk.push(i);
            }
        }
    }
}

Time Complexity: O(V + E)

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the neighboring vertices of a chosen vertex before moving to the next level of vertices.

#include <queue>

void BFS(int start) {
    vector<bool> visited(V, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << v << " ";

        for (int i = 0; i < V; ++i) {
            if (adj[v][i] && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

Time Complexity: O(V + E)

Graph traversal algorithms provide essential mechanisms for exploring the structure of graphs and discovering their properties. They are foundational in graph analysis and play a crucial role in various graph-based algorithms and applications.

Full Code Implementation of Graphs Using Adjacency Matrix in C++

Graph implementation using an adjacency matrix in C++ provides a compact and straightforward way to represent graphs. Adjacency matrices are suitable for dense graphs where most vertices are connected, as they offer constant-time edge existence checks.

This implementation includes the creation of a graph class with methods for adding and removing edges, as well as traversal algorithms such as depth-first search (DFS) and breadth-first search (BFS).

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

class Graph {
private:
    int V;  // Number of vertices
    vector<vector<int>> adj;  // Adjacency matrix

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V, vector<int>(V, 0)); // Initialize adjacency matrix with all zeros
    }

    void addEdge(int u, int v) {
        adj[u][v] = 1;
        // For undirected graphs, uncomment the line below
        // adj[v][u] = 1;
    }

    void removeEdge(int u, int v) {
        adj[u][v] = 0;
        // For undirected graphs, uncomment the line below
        // adj[v][u] = 0;
    }

    void DFS(int start) {
        vector<bool> visited(V, false);
        stack<int> stk;

        stk.push(start);
        visited[start] = true;

        while (!stk.empty()) {
            int v = stk.top();
            stk.pop();
            cout << v << " ";

            for (int i = 0; i < V; ++i) {
                if (adj[v][i] && !visited[i]) {
                    visited[i] = true;
                    stk.push(i);
                }
            }
        }
    }

    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;

        q.push(start);
        visited[start] = true;

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cout << v << " ";

            for (int i = 0; i < V; ++i) {
                if (adj[v][i] && !visited[i]) {
                    visited[i] = true;
                    q.push(i);
                }
            }
        }
    }
};

int main() {
    // Create a graph with 5 vertices
    Graph graph(5);

    // Add some edges
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);

    cout << "Depth-First Search (DFS): ";
    graph.DFS(0);
    cout << endl;

    cout << "Breadth-First Search (BFS): ";
    graph.BFS(0);
    cout << endl;

    return 0;
}

This code demonstrates the creation of a graph class using an adjacency matrix representation in C++. It includes methods for adding and removing edges, as well as depth-first search (DFS) and breadth-first search (BFS) traversal algorithms.

Graph Implementation Using Adjacency List in C++

Graph implementation using an adjacency list in C++ provides a flexible and memory-efficient way to represent graphs. Adjacency lists are suitable for sparse graphs where only a few vertices are connected, as they offer efficient memory usage and traversal.

Creation of the Graph

To create a graph using an adjacency list in C++, we define a class that contains the basic attributes and methods required to manage the graph. Below is the initial part of the class definition, including the basic attributes and the constructor.

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

class Graph {
private:
    int V;  // Number of vertices
    vector<vector<int>> adj;  // Adjacency list

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V); // Initialize adjacency list
    }

    // Other methods for graph operations will be added here
};

Attributes Explanation

1. V: This integer variable stores the number of vertices in the graph.

2. adj: This vector of vectors serves as the adjacency list to represent the connections between vertices. Each vector adj[i] contains the indices of vertices adjacent to vertex i.

Constructor Explanation

The constructor Graph(int vertices) initializes the graph with a specified number of vertices:

• V = vertices: Sets the number of vertices in the graph to the specified value.
• adj.resize(V): Resizes the adjacency list to V size, initializing it with empty vectors for each vertex.

This setup provides the basic framework for the graph, allowing us to build upon it with additional methods for operations such as adding edges, traversing the graph, and finding shortest paths. The constructor ensures that the graph is properly initialized with the specified number of vertices and is ready for further operations.

Operations on Graph

Operations on graphs involve various tasks such as adding or removing edges, traversing the graph, finding shortest paths, and detecting cycles. Each operation serves a specific purpose in graph manipulation and analysis.

Fundamental operations on graphs include adding and removing edges, which modify the connectivity between vertices.

Adding Edge

Adding an edge to a graph establishes a connection between two vertices, creating a relationship between them.

void addEdge(int u, int v) {
    adj[u].push_back(v);
    // For undirected graphs, uncomment the line below
    // adj[v].push_back(u);
}

Time Complexity: O(1)

Removing Edge

Removing an edge from a graph disconnects two vertices, removing the relationship between them.

void removeEdge(int u, int v) {
    for (int i = 0; i < adj[u].size(); ++i) {
        if (adj[u][i] == v) {
            adj[u].erase(adj[u].begin() + i);
            break;
        }
    }
    // For undirected graphs, uncomment the lines below
    // for (int i = 0; i < adj[v].size(); ++i) {
    //     if (adj[v][i] == u) {
    //         adj[v].erase(adj[v].begin() + i);
    //         break;
    //     }
    // }
}

Time Complexity: O(V), where V is the number of vertices in the graph.

These fundamental operations allow us to modify the structure of the graph by adding or removing connections between vertices. They are essential building blocks for more complex graph algorithms and operations.

Graph Traversal

Graph traversal involves visiting all the vertices of a graph in a systematic way. Traversal algorithms help explore the structure of the graph and can be used to perform various tasks such as finding paths, detecting cycles, and discovering connected components.

Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a chosen vertex and explores as far as possible along each branch before backtracking.

#include <stack>

void DFS(int start) {
    vector<bool> visited(V, false);
    stack<int> stk;

    stk.push(start);
    visited[start] = true;

    while (!stk.empty()) {
        int v = stk.top();
        stk.pop();
        cout << v << " ";

        for (int i = 0; i < adj[v].size(); ++i) {
            int u = adj[v][i];
            if (!visited[u]) {
                visited[u] = true;
                stk.push(u);
            }
        }
    }
}

Time Complexity: O(V + E)

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the neighboring vertices of a chosen vertex before moving to the next level of vertices.

#include <queue>

void BFS(int start) {
    vector<bool> visited(V, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << v << " ";

        for (int i = 0; i < adj[v].size(); ++i) {
            int u = adj[v][i];
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}

Time Complexity: O(V + E)

Graph traversal algorithms provide essential mechanisms for exploring the structure of graphs and discovering their properties. They are foundational in graph analysis and play a crucial role in various graph-based algorithms and applications.

Full Code Implementation of Graphs Using Adjacency List in C++

Graph implementation using an adjacency list in C++ provides a flexible and memory-efficient way to represent graphs. Adjacency lists are suitable for sparse graphs where few vertices are connected, as they offer efficient memory usage and traversal operations.

This implementation includes the creation of a graph class with methods for adding and removing edges, as well as traversal algorithms such as depth-first search (DFS) and breadth-first search (BFS).

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

class Graph {
private:
    int V;  // Number of vertices
    vector<vector<int>> adj;  // Adjacency list

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V); // Initialize adjacency list
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        // For undirected graphs, uncomment the line below
        // adj[v].push_back(u);
    }

    void removeEdge(int u, int v) {
        for (auto it = adj[u].begin(); it != adj[u].end(); ++it) {
            if (*it == v) {
                adj[u].erase(it);
                break;
            }
        }
        // For undirected graphs, uncomment the line below
        // for (auto it = adj[v].begin(); it != adj[v].end(); ++it) {
        //     if (*it == u) {
        //         adj[v].erase(it);
        //         break;
        //     }
        // }
    }

    void DFS(int start) {
        vector<bool> visited(V, false);
        stack<int> stk;

        stk.push(start);
        visited[start] = true;

        while (!stk.empty()) {
            int v = stk.top();
            stk.pop();
            cout << v << " ";

            for (int u : adj[v]) {
                if (!visited[u]) {
                    visited[u] = true;
                    stk.push(u);
                }
            }
        }
    }

    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;

        q.push(start);
        visited[start] = true;

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cout << v << " ";

            for (int u : adj[v]) {
                if (!visited[u]) {
                    visited[u] = true;
                    q.push(u);
                }
            }
        }
    }
};

int main() {
    // Create a graph with 5 vertices
    Graph graph(5);

    // Add some edges
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);

    cout << "Depth-First Search (DFS): ";
    graph.DFS(0);
    cout << endl;

    cout << "Breadth-First Search (BFS): ";
    graph.BFS(0);
    cout << endl;

    return 0;
}

This code demonstrates the creation of a graph class using an adjacency list representation in C++. It includes methods for adding and removing edges, as well as depth-first search (DFS) and breadth-first search (BFS) traversal algorithms.