Graphs

Graphs in C++

A graph is a collection of nodes (also called vertices) and edges that connect pairs of nodes. It is a more general structure than trees because it can have cycles and allow for multiple connections between nodes. Graphs are used to represent various real-world problems like social networks, web pages, transportation systems, etc.

Key Terminology in Graphs

1. Vertex (Node): A point in the graph that contains data.
2. Edge (Arc): A connection between two vertices.
3. Adjacent Vertices: Two vertices are adjacent if they are connected by an edge.
4. Degree of a Vertex: The number of edges connected to a vertex. For a directed graph, this can be split into in-degree (edges coming into the vertex) and out-degree (edges going out of the vertex).
5. Path: A sequence of vertices where each adjacent pair is connected by an edge.
6. Cycle: A path that starts and ends at the same vertex.
7. Connected Graph: A graph in which there is a path between every pair of vertices.
8. Directed Graph (Digraph): A graph where edges have a direction (from one vertex to another).
9. Undirected Graph: A graph where edges do not have direction (the edge between two vertices is bidirectional).
10. Weighted Graph: A graph where edges have weights or costs associated with them.
11. Directed Acyclic Graph (DAG): A directed graph with no cycles.
12. Subgraph: A graph formed by a subset of the vertices and edges of the original graph.

Graph Representations

There are two main ways to represent a graph in memory:

1. Adjacency Matrix: A 2D matrix where each cell (i, j) represents whether there is an edge between vertex i and vertex j.
2. Adjacency List: A collection of lists or arrays where each vertex has a list of adjacent vertices (i.e., its neighbors).

1. Graph Implementation Using Adjacency List

In this example, we will implement a graph using an adjacency list. The graph will be undirected and unweighted.

Graph Implementation Using Adjacency List

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

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

public:
    // Constructor to initialize graph with given number of vertices
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    // Add an edge to the graph (undirected graph)
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // Since the graph is undirected
    }

    // Depth First Search (DFS)
    void DFS(int start) {
        vector<bool> visited(V, false);
        stack<int> s;
        s.push(start);
        
        while (!s.empty()) {
            int node = s.top();
            s.pop();
            
            if (!visited[node]) {
                visited[node] = true;
                cout << node << " ";
            }
            
            // Traverse all the adjacent vertices
            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    s.push(neighbor);
                }
            }
        }
        cout << endl;
    }

    // Breadth First Search (BFS)
    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        q.push(start);
        visited[start] = true;

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

            // Visit all unvisited adjacent vertices
            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }

    // Print the adjacency list
    void printGraph() {
        for (int i = 0; i < V; ++i) {
            cout << i << ": ";
            for (int neighbor : adj[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

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

    // Add edges to the graph
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(3, 4);

    // Print the adjacency list of the graph
    cout << "Adjacency List of the Graph:" << endl;
    g.printGraph();

    // Perform DFS starting from vertex 0
    cout << "DFS starting from vertex 0: ";
    g.DFS(0);  // Output: 0 1 2 3 4

    // Perform BFS starting from vertex 0
    cout << "BFS starting from vertex 0: ";
    g.BFS(0);  // Output: 0 1 4 2 3

    return 0;
}

Explanation of the Code:

1. Graph Constructor: Initializes a graph with V vertices and creates an adjacency list (adj), which is a vector of lists. Each list holds the neighbors of the corresponding vertex.

2. addEdge(): Adds an edge between two vertices u and v. Since it's an undirected graph, it adds both v to the adjacency list of u and u to the adjacency list of v.

3. DFS (Depth First Search):

   • A stack is used for DFS traversal.
   • It starts from the start vertex, marks it as visited, and then explores all its neighbors.
   • It continues visiting neighbors in depth before backtracking.

4. BFS (Breadth First Search):

   • A queue is used for BFS traversal.
   • It starts from the start vertex, marks it as visited, and explores all its neighbors in breadth.
   • It proceeds level by level.

5. printGraph(): Displays the adjacency list of the graph.

Output of the Program:

Adjacency List of the Graph:
0: 1 4
1: 0 2 3 4
2: 1
3: 1 4
4: 0 1 3

DFS starting from vertex 0: 0 1 2 3 4 
BFS starting from vertex 0: 0 1 4 2 3 

2. Graph Implementation Using Adjacency Matrix

In this representation, a 2D array (matrix) is used to represent the graph. The element at position (i, j) in the matrix is 1 if there is an edge between vertex i and vertex j, otherwise it's 0.

Graph Implementation Using Adjacency Matrix

#include <iostream>
using namespace std;

class Graph {
private:
    int V;  // Number of vertices
    int** adjMatrix;  // Adjacency matrix

public:
    // Constructor to initialize the graph
    Graph(int vertices) {
        V = vertices;
        adjMatrix = new int*[V];
        for (int i = 0; i < V; i++) {
            adjMatrix[i] = new int[V];
            for (int j = 0; j < V; j++) {
                adjMatrix[i][j] = 0;  // Initialize all edges to 0
            }
        }
    }

    // Add an edge to the graph (undirected graph)
    void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1;  // Since the graph is undirected
    }

    // Print the adjacency matrix
    void printGraph() {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }

    // Destructor to clean up dynamically allocated memory
    ~Graph() {
        for (int i = 0; i < V; i++) {
            delete[] adjMatrix[i];
        }
        delete[] adjMatrix;
    }
};

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

    // Add edges to the graph
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    // Print the adjacency matrix
    cout << "Adjacency Matrix of the Graph:" << endl;
    g.printGraph();

    return 0;
}

Output of the Program:

Adjacency Matrix of the Graph:
0 1 1 0 
1 0 1 0 
1 1 0 1 
0 0 1 0 

Conclusion

Graphs are a powerful data structure for modeling