Graphs

A graph is a non-linear data structure consisting of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles and multiple paths between vertices. Graphs are essential for modeling relationships, networks, and many real-world problems.

Common applications include social networks, transportation systems, computer networks, web page linking, and pathfinding algorithms like GPS navigation.

Graph Representations

Adjacency Matrix

An adjacency matrix uses a 2D array where matrix[i][j] indicates if there is an edge between vertex i and vertex j:

Graph using Adjacency Matrix

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

class GraphMatrix {
private:
    int vertices;
    vector<vector<int>> adjMatrix;

public:
    GraphMatrix(int v) : vertices(v) {
        adjMatrix.resize(v, vector<int>(v, 0));
    }
    
    void addEdge(int src, int dest, bool isDirected = false) {
        if (src >= 0 && src < vertices && dest >= 0 && dest < vertices) {
            adjMatrix[src][dest] = 1;
            if (!isDirected) {
                adjMatrix[dest][src] = 1; // For undirected graph
            }
        }
    }
    
    void removeEdge(int src, int dest, bool isDirected = false) {
        if (src >= 0 && src < vertices && dest >= 0 && dest < vertices) {
            adjMatrix[src][dest] = 0;
            if (!isDirected) {
                adjMatrix[dest][src] = 0;
            }
        }
    }
    
    bool hasEdge(int src, int dest) {
        if (src >= 0 && src < vertices && dest >= 0 && dest < vertices) {
            return adjMatrix[src][dest] == 1;
        }
        return false;
    }
    
    void printGraph() {
        cout << "Adjacency Matrix:" << endl;
        cout << "   ";
        for (int i = 0; i < vertices; i++) {
            cout << i << " ";
        }
        cout << endl;
        
        for (int i = 0; i < vertices; i++) {
            cout << i << ": ";
            for (int j = 0; j < vertices; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
    
    void dfs(int start, vector<bool>& visited) {
        visited[start] = true;
        cout << start << " ";
        
        for (int i = 0; i < vertices; i++) {
            if (adjMatrix[start][i] == 1 && !visited[i]) {
                dfs(i, visited);
            }
        }
    }
    
    void dfsTraversal(int start) {
        vector<bool> visited(vertices, false);
        cout << "DFS Traversal starting from " << start << ": ";
        dfs(start, visited);
        cout << endl;
    }
};

int main() {
    GraphMatrix graph(5);
    
    // Add edges
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    
    graph.printGraph();
    
    cout << "\nEdge (0,1) exists: " << (graph.hasEdge(0, 1) ? "Yes" : "No") << endl;
    cout << "Edge (0,3) exists: " << (graph.hasEdge(0, 3) ? "Yes" : "No") << endl;
    
    graph.dfsTraversal(0);
    
    return 0;
}

Adjacency List

An adjacency list uses an array of lists where each list contains the neighbors of a vertex:

Graph using Adjacency List

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

class GraphList {
private:
    int vertices;
    vector<list<int>> adjList;

public:
    GraphList(int v) : vertices(v) {
        adjList.resize(v);
    }
    
    void addEdge(int src, int dest, bool isDirected = false) {
        adjList[src].push_back(dest);
        if (!isDirected) {
            adjList[dest].push_back(src);
        }
    }
    
    void removeEdge(int src, int dest, bool isDirected = false) {
        adjList[src].remove(dest);
        if (!isDirected) {
            adjList[dest].remove(src);
        }
    }
    
    void printGraph() {
        cout << "Adjacency List:" << endl;
        for (int i = 0; i < vertices; i++) {
            cout << i << ": ";
            for (int neighbor : adjList[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
    
    void bfsTraversal(int start) {
        vector<bool> visited(vertices, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        cout << "BFS Traversal starting from " << start << ": ";
        
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            cout << current << " ";
            
            for (int neighbor : adjList[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
    
    void dfs(int start, vector<bool>& visited) {
        visited[start] = true;
        cout << start << " ";
        
        for (int neighbor : adjList[start]) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }
    
    void dfsTraversal(int start) {
        vector<bool> visited(vertices, false);
        cout << "DFS Traversal starting from " << start << ": ";
        dfs(start, visited);
        cout << endl;
    }
    
    bool hasPath(int src, int dest) {
        if (src == dest) return true;
        
        vector<bool> visited(vertices, false);
        queue<int> q;
        
        visited[src] = true;
        q.push(src);
        
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            
            for (int neighbor : adjList[current]) {
                if (neighbor == dest) return true;
                
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        
        return false;
    }
};

int main() {
    GraphList graph(6);
    
    // Add edges
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(4, 5);
    
    graph.printGraph();
    
    cout << endl;
    graph.bfsTraversal(0);
    graph.dfsTraversal(0);
    
    cout << "\nPath from 0 to 5: " << (graph.hasPath(0, 5) ? "Exists" : "Doesn't exist") << endl;
    cout << "Path from 1 to 4: " << (graph.hasPath(1, 4) ? "Exists" : "Doesn't exist") << endl;
    
    return 0;
}

Graph Algorithms

Shortest Path (Dijkstra's Algorithm)

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph:

Dijkstra's Shortest Path Algorithm

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

class WeightedGraph {
private:
    int vertices;
    vector<vector<pair<int, int>>> adjList; // pair<destination, weight>

public:
    WeightedGraph(int v) : vertices(v) {
        adjList.resize(v);
    }
    
    void addEdge(int src, int dest, int weight) {
        adjList[src].push_back({dest, weight});
        adjList[dest].push_back({src, weight}); // For undirected graph
    }
    
    vector<int> dijkstra(int start) {
        vector<int> dist(vertices, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        dist[start] = 0;
        pq.push({0, start}); // {distance, vertex}
        
        while (!pq.empty()) {
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;
                
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
        
        return dist;
    }
    
    void printShortestPaths(int start) {
        vector<int> distances = dijkstra(start);
        
        cout << "Shortest distances from vertex " << start << ":" << endl;
        for (int i = 0; i < vertices; i++) {
            if (distances[i] == INT_MAX) {
                cout << "Vertex " << i << ": No path" << endl;
            } else {
                cout << "Vertex " << i << ": " << distances[i] << endl;
            }
        }
    }
};

int main() {
    WeightedGraph graph(6);
    
    // Add weighted edges
    graph.addEdge(0, 1, 4);
    graph.addEdge(0, 2, 2);
    graph.addEdge(1, 2, 1);
    graph.addEdge(1, 3, 5);
    graph.addEdge(2, 3, 8);
    graph.addEdge(2, 4, 10);
    graph.addEdge(3, 4, 2);
    graph.addEdge(3, 5, 6);
    graph.addEdge(4, 5, 3);
    
    graph.printShortestPaths(0);
    
    return 0;
}

Graph Applications

Cycle Detection

Detecting cycles in graphs is important for many applications. Here's cycle detection for undirected graphs:

Cycle Detection in Undirected Graph

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

class CycleDetection {
private:
    int vertices;
    vector<vector<int>> adjList;
    
    bool dfsHasCycle(int v, vector<bool>& visited, int parent) {
        visited[v] = true;
        
        for (int neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                if (dfsHasCycle(neighbor, visited, v)) {
                    return true;
                }
            } else if (neighbor != parent) {
                // Back edge found (cycle detected)
                return true;
            }
        }
        
        return false;
    }

public:
    CycleDetection(int v) : vertices(v) {
        adjList.resize(v);
    }
    
    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src);
    }
    
    bool hasCycle() {
        vector<bool> visited(vertices, false);
        
        // Check each component
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                if (dfsHasCycle(i, visited, -1)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    void printGraph() {
        cout << "Graph:" << endl;
        for (int i = 0; i < vertices; i++) {
            cout << i << ": ";
            for (int neighbor : adjList[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    // Test with a graph that has a cycle
    CycleDetection graph1(5);
    graph1.addEdge(0, 1);
    graph1.addEdge(1, 2);
    graph1.addEdge(2, 3);
    graph1.addEdge(3, 4);
    graph1.addEdge(4, 1); // Creates a cycle
    
    graph1.printGraph();
    cout << "Has cycle: " << (graph1.hasCycle() ? "Yes" : "No") << endl;
    
    cout << "\n" << string(30, '-') << "\n" << endl;
    
    // Test with a graph without cycle (tree)
    CycleDetection graph2(4);
    graph2.addEdge(0, 1);
    graph2.addEdge(1, 2);
    graph2.addEdge(2, 3);
    
    graph2.printGraph();
    cout << "Has cycle: " << (graph2.hasCycle() ? "Yes" : "No") << endl;
    
    return 0;
}