Skip to main content

Graph Algorithms

Graph algorithms are fundamental to competitive programming and computer science. They help solve problems involving relationships between objects, networks, and complex data structures.

🎯 What are Graphs?​

A graph is a data structure consisting of:

  • Vertices (Nodes): Points in the graph
  • Edges: Connections between vertices
  • Directed/Undirected: Edges may have direction or be bidirectional
  • Weighted/Unweighted: Edges may have associated weights

📚 Graph Representations​

1. Adjacency Matrix​

int graph[n][n];
// graph[i][j] = weight of edge from i to j (0 if no edge)

2. Adjacency List​

vector<vector<int>> graph(n);
// graph[i] = list of neighbors of vertex i

3. Edge List​

vector<pair<int, int>> edges;
// List of all edges (u, v)

🚀 Essential Graph Algorithms​

1. Graph Traversal​

Depth-First Search (DFS)​

vector<bool> visited(n, false);

void dfs(int v) {
    visited[v] = true;
    for(int u : graph[v]) {
        if(!visited[u]) {
            dfs(u);
        }
    }
}

Breadth-First Search (BFS)​

vector<bool> visited(n, false);
queue<int> q;

void bfs(int start) {
    q.push(start);
    visited[start] = true;
    
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        
        for(int u : graph[v]) {
            if(!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}

2. Shortest Path Algorithms​

Dijkstra's Algorithm​

// For weighted graphs with non-negative weights
priority_queue<pair<int, int>> pq;
vector<int> dist(n, INF);

Bellman-Ford Algorithm​

// For graphs with negative weights (no negative cycles)
vector<int> dist(n, INF);
dist[source] = 0;

3. Minimum Spanning Tree​

Kruskal's Algorithm​

// Sort edges by weight, use Union-Find
sort(edges.begin(), edges.end());

Prim's Algorithm​

// Start with one vertex, add minimum weight edges
priority_queue<pair<int, int>> pq;

4. Strongly Connected Components (SCC)​

// Kosaraju's Algorithm or Tarjan's Algorithm
vector<vector<int>> scc;

📝 Problem List​

Basic Graph Problems​

Shortest Path​

Tree Problems​

Advanced Graph Problems​

💡 Tips for Graph Problems​

  1. Choose the Right Representation: Adjacency list for sparse graphs, matrix for dense graphs
  2. Consider Edge Cases: Disconnected components, cycles, self-loops
  3. Optimize Traversal: Use appropriate data structures (queue for BFS, stack for DFS)
  4. Handle Multiple Components: Check for connectivity
  5. Memory Management: Be careful with large graphs

🔗 Related Resources​

Master graph algorithms and solve complex network problems efficiently! 🌐