Graphs

Understanding graphs as a data structure.

What are Graphs?

A graph is a non-linear data structure consisting of vertices (nodes) and edges that connect these vertices. Unlike trees, which have a strict hierarchical structure, graphs can represent more complex relationships where connections can form cycles and nodes can have multiple paths between them.

Types of Graphs

  1. Directed vs Undirected

    • Directed (Digraph): Edges have a direction (one-way connection)
    • Undirected: Edges have no direction (two-way connection)

  2. Weighted vs Unweighted

    • Weighted: Edges have associated costs or weights
    • Unweighted: All edges have equal importance

  3. Special Types

    • Complete Graph: Every vertex is connected to every other vertex
    • Bipartite Graph: Vertices can be divided into two sets with edges only between sets
    • Tree: Connected graph with no cycles
    • DAG (Directed Acyclic Graph): Directed graph with no cycles

Graph Representations

  1. Adjacency Matrix

    • 2D array where matrix[i][j] represents edge between vertices i and j
    • Space Complexity: O(V²)
    • Good for dense graphs

  2. Adjacency List

    • Array/List of lists where each index stores connected vertices
    • Space Complexity: O(V + E)
    • Better for sparse graphs

Common Graph Operations

  • Basic Operations

    • Add vertex: O(1)
    • Add edge: O(1) for adjacency list, O(1) for matrix
    • Remove vertex: O(V + E) for list, O(V²) for matrix
    • Remove edge: O(E) for list, O(1) for matrix
    • Check if edge exists: O(V) for list, O(1) for matrix

  • Traversal Operations

    • Depth First Search (DFS): O(V + E)
    • Breadth First Search (BFS): O(V + E)

Code Examples

Here's how you implement a basic graph in different languages:

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);  // For undirected graph
    }

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

        visited[s] = true;
        queue.push(s);

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

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

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

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

    cout << "BFS starting from vertex 0: ";
    g.BFS(0); // Perform BFS starting from vertex 0

    return 0;
}

Common Graph Algorithms

  • Depth-First Search (DFS)

  • Breadth-First Search (BFS)

Problems to Solve

Important Problems on Graphs

Resources