Graph

Graph Representation

Adjacency Matrix

• A 2D V×V array (matrix[i][j]) where:
  • 1 (or weight) → edge exists between vertex i and j.
  • 0 → no edge.
• Works for directed/undirected, weighted/unweighted graphs.

    A                  |   | A | B | C | D |
   / \                 | - | - | - | - | - |
  B---C                | A | 0 | 1 | 1 | 0 |
       \      =>       | B | 1 | 0 | 1 | 0 |
        D              | C | 1 | 1 | 0 | 1 |
                       | D | 0 | 0 | 1 | 0 |

Pros:

1. Fast edge check: O(1) to check if edge (u, v) exists.
2. Simple implementation: Very straightforward.
3. Good for dense graphs: When number of edges E ≈ V^2.

Cons:

1. Memory heavy: Requires O(V²) space, even if sparse.
2. Inefficient for sparse graphs: Most of the matrix might be zeros.
3. Slow to iterate neighbors: Takes O(V) to find all neighbors of a vertex.

When to use: Small graphs or dense graphs where checking edge existence quickly is needed.

Adjacency List

• Each vertex has a list of neighbors.
• Usually implemented as an array of lists or vectors.
• Can store weights if needed.

    A
   / \                 A → B, C
  B---C                B → A, C
       \      =>       C → A, B, D
        D              D → C

Pros:

1. Space efficient: Uses O(V+E) space, good for sparse graphs.
2. Easy to iterate neighbors: Only iterate over actual edges, not empty slots.
3. Flexible: Can store weights easily.

Cons:

1. Edge existence check is slower: Need to search the list → O(k), where k = degree of vertex.
2. Slightly more complex implementation than a matrix.

When to use: Large sparse graphs, most real-world networks (social networks, maps).

Edge List

A list of all edges. Each edge is stored as a pair (u, v) or (u, v, w) if weighted.

    A
   / \                 (A, B)
  B---C                (A, C)
       \      =>       (B, C)
        D              (C, D)

Pros:

1. Simple and compact: Good for storing edges only.
2. Easy to implement algorithms like Kruskal’s (MST).

Cons:

1. Slow to check edge existence: O(E) search needed.
2. Hard to iterate neighbors of a vertex efficiently.

When to use: Algorithms that process edges directly, e.g., Kruskal’s MST, or input/output of edges.

Adjacency Set / Map

• Similar to adjacency list but uses hash sets/maps instead of lists.
• Example: unordered_map<int, unordered_set<int>> in C++.

Pros:

• Fast edge check: O(1) average for set/map.
• Space efficient for sparse graphs.

Cons:

• More memory overhead than simple lists.
• Slightly slower iteration than plain arrays/lists.

When to use: Sparse graphs when you need fast existence checks for edges.

Incidence Matrix

• A V×E matrix: matrix[i][j] = 1 if vertex i is incident to edge j.
• Rarely used except in special graph algorithms.

Pros:

• Mathematically elegant; good for theoretical analysis.
• Can represent multi-graphs easily.

Cons:

1. Memory heavy: O(V×E)
2. Not practical for most programming problems.
3. Edge iteration and neighbor finding is slower.

When to use: Academic or theoretical problems, multi-graphs, or algorithms needing incidence info.

Quick Comparison

Representation	Space Complexity	Edge Check	Neighbor Iteration	Best For
Adjacency Matrix	O(V²)	O(1)	O(V)	Dense graph, fast edge check
Adjacency List	O(V+E)	O(k)	O(k)	Sparse graph, iterate neighbors
Edge List	O(E)	O(E)	O(E)	Edge-centric algorithms
Adjacency Set/Map	O(V+E)	O(1) avg	O(k)	Sparse graph, fast edge check
Incidence Matrix	O(V*E)	O(V)	O(E)	Multi-graphs, theoretical work

Graph Implementation

C Programming

struct Node {
    int vertex;
    struct Node* next;
};

// Graph structure
struct Graph {
    int numVertices;
    struct Node** adjLists;
    bool* visited;
};

// Create a node
struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct Node*));
    graph->visited = malloc(vertices * sizeof(bool));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = false;
    }
    return graph;
}

// Add edge (undirected)
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge src -> dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge dest -> src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

int main() {
    struct Graph* graph = createGraph(4);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
}

C++ Programming

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

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

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

int main() {
    Graph g(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
}

Traversing

DFS

• Recursive/Iterative: Required 3 parameter(adj list, visited nodes, current node)

  void dfs(int start) {
      vector<bool> visited(V, false);
      stack<int> s;
  
      visited[start] = true;
      s.push(start);
  
      cout << "DFS: ";
      while (!s.empty()) {
          int v = s.top();
          s.pop();
          cout << v << " ";
  
          for (int neighbor : adj[v]) {
              if (!visited[neighbor]) {
                  visited[neighbor] = true;
                  s.push(neighbor);
              }
          }
  
          cout << endl;
      }
  };

• Itertive: In stack which element insert first, pop out at last, which reverse the order. So iterate the list from last and insert into stack, whish will pop out at last as well, this way the order of traversing maintain properly.

  // 1D Array
  void dfs_helper(int v, vector<bool>& visited) {
      visited[v] = true;
      cout << v << " ";
  
      for (int neighbor : adj[v]) {
          if (!visited[neighbor]){
              dfs_helper(neighbor, visited);
          }
      }
  }
  void dfs(int start) {
      vector<bool> visited(V, false);
      cout << "DFS: ";
      dfs_helper(start, visited);
      cout << endl;
  }
  
  // 2D Array
  vector<pair<int,int>> directions = {
    {1, 0},   // down
    {-1, 0},  // up
    {0, 1},   // right
    {0, -1}   // left
   };
  
  void dfs(vector<vector<int>>& grid, int r, int c) {
    // Boundary & validity check
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == 0)
        return;
  
    // Mark as visited
    grid[r][c] = 0;
  
    cout << "(" << r << "," << c << ") ";
  
    // Explore neighbors
    for (auto dir : directions) {
        dfs(grid, r + dir.first, c + dir.second);
    }
  }

Characterstics:

• It is useful for tasks like cycle detection, topological sorting, and maze solving.
• Find path without shortest path requirement

BFS

• Iterative: Just replace stack with queue in dfs, rest is same.

// 1D Array
void bfs(int start) {
    vector<bool> visited(V, false);
    queue<int> q;

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

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

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

        cout << endl;
    }
};

// 2D Array
vector<pair<int,int>> directions = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};

void bfs(vector<vector<int>>& grid, int startR, int startC) {
    int rows = grid.size();
    int cols = grid[0].size();

    queue<pair<int,int>> q;
    q.push({startR, startC});
    grid[startR][startC] = 0;  // mark visited

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        cout << "(" << r << "," << c << ") ";

        for (auto dir : directions) {
            int newR = r + dir.first;
            int newC = c + dir.second;

            if (newR >= 0 && newC >= 0 &&
                newR < rows && newC < cols &&
                grid[newR][newC] == 1) {

                grid[newR][newC] = 0;
                q.push({newR, newC});
            }
        }
    }
}

Characterstics:

• Explores neighbors before children(layer by layer)
• Finds shortest path in an unweighted graph

When to Use BFS vs DFS?

Aspect	BFS	DFS
Shortest Path?	✅ Yes (unweighted graphs)	❌ No
Memory Usage	🟠 High (stores full layer)	🟢 Lower (stores one path)
Graph Type?	🟢 Wide, shallow graphs	🟢 Deep, narrow graphs
Cycle Detection?	🟢 Yes	🟢 Yes
Connected Components?	🟢 Yes	🟢 Yes

Complexity

• V: Number of vertices (nodes)
• E: Number of edges (connections)

Time Complexity: O(V + E)

Space Complexity: O(V)

Shortest path using BFS

• BFS explores all nodes at distance 1 first, then distance 2, and so on.
• The first time you reach a node, you have found the shortest path from the source.
• To extract the path, you need to track the parent of each node.
• Create a visited array to mark visited nodes.
• Create a parent array to store the predecessor of each node.
  • parent[v] = u the node from which you reached v.