🌐 Thuật toán đồ thị (Graph Algorithms)

📖 Giới thiệu

Graph algorithms là foundation của computer science, modeling relationships và connections trong countless applications từ social networks đến GPS navigation, computer networks đến AI pathfinding. Hiểu graph algorithms là essential cho bất kỳ developer nào muốn solve complex real-world problems.

Real-world applications:

• Social Networks: Friend recommendations, influence analysis
• Transportation: GPS routing, traffic optimization
• Computer Networks: Routing protocols, network topology
• Game Development: Pathfinding, AI decision making
• Web Search: PageRank algorithm, link analysis
• Dependency Resolution: Package managers, build systems

Core Graph Concepts:

• Vertices (Nodes): Entities in the graph
• Edges: Connections between vertices
• Directed vs Undirected: One-way vs two-way connections
• Weighted vs Unweighted: Edges có cost/distance hay không

🔧 Cú pháp

Graph Representation

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
using namespace std;

// Adjacency List Representation
class Graph {
private:
    int numVertices;
    vector<vector<int>> adjList;
    bool isDirected;
    
public:
    Graph(int vertices, bool directed = false) 
        : numVertices(vertices), isDirected(directed) {
        adjList.resize(vertices);
    }
    
    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        if (!isDirected) {
            adjList[dest].push_back(src);
        }
    }
    
    void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            cout << "Vertex " << i << ": ";
            for (int neighbor : adjList[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
    
    vector<vector<int>>& getAdjList() { return adjList; }
    int getNumVertices() const { return numVertices; }
};

// Weighted Graph
class WeightedGraph {
private:
    int numVertices;
    vector<vector<pair<int, int>>> adjList; // {destination, weight}
    bool isDirected;
    
public:
    WeightedGraph(int vertices, bool directed = false) 
        : numVertices(vertices), isDirected(directed) {
        adjList.resize(vertices);
    }
    
    void addEdge(int src, int dest, int weight) {
        adjList[src].push_back({dest, weight});
        if (!isDirected) {
            adjList[dest].push_back({src, weight});
        }
    }
    
    vector<vector<pair<int, int>>>& getAdjList() { return adjList; }
    int getNumVertices() const { return numVertices; }
};

Depth-First Search (DFS)

class GraphTraversal {
public:
    // DFS Recursive
    void dfsRecursive(vector<vector<int>>& graph, int vertex, vector<bool>& visited) {
        visited[vertex] = true;
        cout << vertex << " ";
        
        for (int neighbor : graph[vertex]) {
            if (!visited[neighbor]) {
                dfsRecursive(graph, neighbor, visited);
            }
        }
    }
    
    // DFS Iterative
    void dfsIterative(vector<vector<int>>& graph, int start) {
        int n = graph.size();
        vector<bool> visited(n, false);
        stack<int> stack;
        
        stack.push(start);
        
        while (!stack.empty()) {
            int vertex = stack.top();
            stack.pop();
            
            if (!visited[vertex]) {
                visited[vertex] = true;
                cout << vertex << " ";
                
                // Add neighbors to stack (in reverse order for consistent traversal)
                for (int i = graph[vertex].size() - 1; i >= 0; i--) {
                    if (!visited[graph[vertex][i]]) {
                        stack.push(graph[vertex][i]);
                    }
                }
            }
        }
    }
    
    // Check if path exists between two vertices
    bool hasPath(vector<vector<int>>& graph, int start, int end) {
        if (start == end) return true;
        
        int n = graph.size();
        vector<bool> visited(n, false);
        stack<int> stack;
        
        stack.push(start);
        visited[start] = true;
        
        while (!stack.empty()) {
            int vertex = stack.top();
            stack.pop();
            
            for (int neighbor : graph[vertex]) {
                if (neighbor == end) return true;
                
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
        
        return false;
    }
};

Breadth-First Search (BFS)

class BFSAlgorithms {
public:
    // Basic BFS
    void bfs(vector<vector<int>>& graph, int start) {
        int n = graph.size();
        vector<bool> visited(n, false);
        queue<int> queue;
        
        visited[start] = true;
        queue.push(start);
        
        while (!queue.empty()) {
            int vertex = queue.front();
            queue.pop();
            cout << vertex << " ";
            
            for (int neighbor : graph[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }
    }
    
    // BFS to find shortest path (unweighted graph)
    vector<int> shortestPath(vector<vector<int>>& graph, int start, int end) {
        int n = graph.size();
        vector<bool> visited(n, false);
        vector<int> parent(n, -1);
        queue<int> queue;
        
        visited[start] = true;
        queue.push(start);
        
        while (!queue.empty()) {
            int vertex = queue.front();
            queue.pop();
            
            if (vertex == end) break;
            
            for (int neighbor : graph[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = vertex;
                    queue.push(neighbor);
                }
            }
        }
        
        // Reconstruct path
        vector<int> path;
        if (parent[end] != -1 || start == end) {
            int current = end;
            while (current != -1) {
                path.push_back(current);
                current = parent[current];
            }
            reverse(path.begin(), path.end());
        }
        
        return path;
    }
    
    // Multi-source BFS
    vector<int> multiSourceBFS(vector<vector<int>>& graph, vector<int>& sources) {
        int n = graph.size();
        vector<int> distance(n, -1);
        queue<int> queue;
        
        // Initialize all sources
        for (int source : sources) {
            distance[source] = 0;
            queue.push(source);
        }
        
        while (!queue.empty()) {
            int vertex = queue.front();
            queue.pop();
            
            for (int neighbor : graph[vertex]) {
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[vertex] + 1;
                    queue.push(neighbor);
                }
            }
        }
        
        return distance;
    }
};

Shortest Path Algorithms

class ShortestPathAlgorithms {
public:
    // Dijkstra's Algorithm
    vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
        int n = graph.size();
        vector<int> distance(n, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        distance[start] = 0;
        pq.push({0, start});
        
        while (!pq.empty()) {
            int dist = pq.top().first;
            int vertex = pq.top().second;
            pq.pop();
            
            if (dist > distance[vertex]) continue;
            
            for (auto& edge : graph[vertex]) {
                int neighbor = edge.first;
                int weight = edge.second;
                
                if (distance[vertex] + weight < distance[neighbor]) {
                    distance[neighbor] = distance[vertex] + weight;
                    pq.push({distance[neighbor], neighbor});
                }
            }
        }
        
        return distance;
    }
    
    // Bellman-Ford Algorithm (handles negative weights)
    pair<vector<int>, bool> bellmanFord(vector<vector<pair<int, int>>>& graph, int start) {
        int n = graph.size();
        vector<int> distance(n, INT_MAX);
        distance[start] = 0;
        
        // Relax edges n-1 times
        for (int i = 0; i < n - 1; i++) {
            for (int u = 0; u < n; u++) {
                if (distance[u] == INT_MAX) continue;
                
                for (auto& edge : graph[u]) {
                    int v = edge.first;
                    int weight = edge.second;
                    
                    if (distance[u] + weight < distance[v]) {
                        distance[v] = distance[u] + weight;
                    }
                }
            }
        }
        
        // Check for negative cycles
        bool hasNegativeCycle = false;
        for (int u = 0; u < n; u++) {
            if (distance[u] == INT_MAX) continue;
            
            for (auto& edge : graph[u]) {
                int v = edge.first;
                int weight = edge.second;
                
                if (distance[u] + weight < distance[v]) {
                    hasNegativeCycle = true;
                    break;
                }
            }
            if (hasNegativeCycle) break;
        }
        
        return {distance, hasNegativeCycle};
    }
    
    // Floyd-Warshall Algorithm (All pairs shortest path)
    vector<vector<int>> floydWarshall(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> dist = graph;
        
        // Initialize distances
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else if (dist[i][j] == 0) {
                    dist[i][j] = INT_MAX;
                }
            }
        }
        
        // Floyd-Warshall algorithm
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                        dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        return dist;
    }
};

Topological Sort và Cycle Detection

class GraphAnalysis {
public:
    // Topological Sort using DFS
    vector<int> topologicalSort(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<bool> visited(n, false);
        stack<int> stack;
        
        function<void(int)> dfs = [&](int vertex) {
            visited[vertex] = true;
            
            for (int neighbor : graph[vertex]) {
                if (!visited[neighbor]) {
                    dfs(neighbor);
                }
            }
            
            stack.push(vertex);
        };
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        
        vector<int> result;
        while (!stack.empty()) {
            result.push_back(stack.top());
            stack.pop();
        }
        
        return result;
    }
    
    // Kahn's Algorithm for Topological Sort
    vector<int> topologicalSortKahn(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> indegree(n, 0);
        
        // Calculate indegrees
        for (int i = 0; i < n; i++) {
            for (int neighbor : graph[i]) {
                indegree[neighbor]++;
            }
        }
        
        queue<int> queue;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.push(i);
            }
        }
        
        vector<int> result;
        while (!queue.empty()) {
            int vertex = queue.front();
            queue.pop();
            result.push_back(vertex);
            
            for (int neighbor : graph[vertex]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.push(neighbor);
                }
            }
        }
        
        return result.size() == n ? result : vector<int>(); // Empty if cycle exists
    }
    
    // Cycle Detection in Directed Graph
    bool hasCycleDirected(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0); // 0: white, 1: gray, 2: black
        
        function<bool(int)> dfs = [&](int vertex) {
            color[vertex] = 1; // Mark as gray (visiting)
            
            for (int neighbor : graph[vertex]) {
                if (color[neighbor] == 1) { // Back edge found
                    return true;
                }
                if (color[neighbor] == 0 && dfs(neighbor)) {
                    return true;
                }
            }
            
            color[vertex] = 2; // Mark as black (visited)
            return false;
        };
        
        for (int i = 0; i < n; i++) {
            if (color[i] == 0 && dfs(i)) {
                return true;
            }
        }
        
        return false;
    }
    
    // Cycle Detection in Undirected Graph
    bool hasCycleUndirected(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<bool> visited(n, false);
        
        function<bool(int, int)> dfs = [&](int vertex, int parent) {
            visited[vertex] = true;
            
            for (int neighbor : graph[vertex]) {
                if (neighbor == parent) continue;
                
                if (visited[neighbor]) {
                    return true; // Cycle found
                }
                
                if (dfs(neighbor, vertex)) {
                    return true;
                }
            }
            
            return false;
        };
        
        for (int i = 0; i < n; i++) {
            if (!visited[i] && dfs(i, -1)) {
                return true;
            }
        }
        
        return false;
    }
};

🔬 Phân tích & Giải thích chi tiết

Graph Algorithms Complexity

Algorithm	Time Complexity	Space Complexity	Use Case
DFS	O(V + E)	O(V)	Path finding, cycle detection
BFS	O(V + E)	O(V)	Shortest path (unweighted)
Dijkstra	O((V + E) log V)	O(V)	Shortest path (non-negative weights)
Bellman-Ford	O(VE)	O(V)	Shortest path (negative weights)
Floyd-Warshall	O(V³)	O(V²)	All pairs shortest path
Topological Sort	O(V + E)	O(V)	Dependency resolution

Khi nào sử dụng thuật toán nào?

DFS:

• Path existence problems
• Cycle detection
• Topological sorting
• Connected components

BFS:

• Shortest path trong unweighted graphs
• Level-order traversal
• Finding connected components
• Multi-source problems

Dijkstra:

• Shortest path với non-negative weights
• GPS navigation systems
• Network routing protocols

Bellman-Ford:

• Shortest path với negative weights
• Currency arbitrage detection
• Network routing với negative costs

💻 Ví dụ minh họa

Ví dụ 1: Social Network Analysis

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;

class SocialNetwork {
private:
    unordered_map<string, vector<string>> friendships;
    unordered_map<string, int> userIndex;
    vector<string> users;
    
public:
    void addUser(const string& user) {
        if (userIndex.find(user) == userIndex.end()) {
            userIndex[user] = users.size();
            users.push_back(user);
            friendships[user] = vector<string>();
        }
    }
    
    void addFriendship(const string& user1, const string& user2) {
        addUser(user1);
        addUser(user2);
        
        friendships[user1].push_back(user2);
        friendships[user2].push_back(user1);
    }
    
    // Find shortest connection path between two users
    vector<string> findConnectionPath(const string& start, const string& end) {
        if (friendships.find(start) == friendships.end() || 
            friendships.find(end) == friendships.end()) {
            return {};
        }
        
        unordered_map<string, string> parent;
        unordered_set<string> visited;
        queue<string> queue;
        
        queue.push(start);
        visited.insert(start);
        parent[start] = "";
        
        while (!queue.empty()) {
            string current = queue.front();
            queue.pop();
            
            if (current == end) break;
            
            for (const string& friend_user : friendships[current]) {
                if (visited.find(friend_user) == visited.end()) {
                    visited.insert(friend_user);
                    parent[friend_user] = current;
                    queue.push(friend_user);
                }
            }
        }
        
        // Reconstruct path
        vector<string> path;
        if (parent.find(end) != parent.end()) {
            string current = end;
            while (current != "") {
                path.push_back(current);
                current = parent[current];
            }
            reverse(path.begin(), path.end());
        }
        
        return path;
    }
    
    // Find mutual friends
    vector<string> findMutualFriends(const string& user1, const string& user2) {
        vector<string> mutual;
        
        if (friendships.find(user1) == friendships.end() || 
            friendships.find(user2) == friendships.end()) {
            return mutual;
        }
        
        unordered_set<string> friends1(friendships[user1].begin(), friendships[user1].end());
        
        for (const string& friend_user : friendships[user2]) {
            if (friends1.find(friend_user) != friends1.end()) {
                mutual.push_back(friend_user);
            }
        }
        
        return mutual;
    }
    
    // Find friend recommendations (friends of friends)
    vector<string> recommendFriends(const string& user) {
        unordered_map<string, int> recommendations;
        unordered_set<string> directFriends(friendships[user].begin(), friendships[user].end());
        directFriends.insert(user); // Don't recommend self
        
        for (const string& friend_user : friendships[user]) {
            for (const string& friendOfFriend : friendships[friend_user]) {
                if (directFriends.find(friendOfFriend) == directFriends.end()) {
                    recommendations[friendOfFriend]++;
                }
            }
        }
        
        vector<pair<int, string>> scored;
        for (const auto& rec : recommendations) {
            scored.push_back({rec.second, rec.first});
        }
        
        sort(scored.rbegin(), scored.rend());
        
        vector<string> result;
        for (const auto& score : scored) {
            result.push_back(score.second);
        }
        
        return result;
    }
    
    void demonstrateSocialNetwork() {
        cout << "=== SOCIAL NETWORK ANALYSIS ===" << endl;
        
        // Add users and friendships
        addFriendship("Alice", "Bob");
        addFriendship("Bob", "Charlie");
        addFriendship("Charlie", "David");
        addFriendship("Alice", "Eve");
        addFriendship("Eve", "Frank");
        addFriendship("Frank", "Charlie");
        addFriendship("David", "Grace");
        addFriendship("Bob", "Grace");
        
        // Find connection path
        cout << "\n🔍 Finding connection path from Alice to David:" << endl;
        vector<string> path = findConnectionPath("Alice", "David");
        if (!path.empty()) {
            for (int i = 0; i < path.size(); i++) {
                cout << path[i];
                if (i < path.size() - 1) cout << " -> ";
            }
            cout << " (Distance: " << path.size() - 1 << ")" << endl;
        }
        
        // Find mutual friends
        cout << "\n👥 Mutual friends of Alice and Charlie:" << endl;
        vector<string> mutual = findMutualFriends("Alice", "Charlie");
        for (const string& friend_user : mutual) {
            cout << friend_user << " ";
        }
        cout << endl;
        
        // Friend recommendations
        cout << "\n💡 Friend recommendations for Alice:" << endl;
        vector<string> recommendations = recommendFriends("Alice");
        for (int i = 0; i < min(3, (int)recommendations.size()); i++) {
            cout << (i + 1) << ". " << recommendations[i] << endl;
        }
    }
};

int main() {
    SocialNetwork network;
    network.demonstrateSocialNetwork();
    
    return 0;
}

🏋️ Thực hành

Bài tập 1: Flight Route Optimization

Build flight route system:

• Cities as vertices, flights as weighted edges
• Find cheapest route between cities
• Handle layovers và time constraints
• Find alternative routes if direct flight unavailable

Bài tập 2: Dependency Resolution

Implement package dependency resolver:

• Packages as vertices, dependencies as edges
• Detect circular dependencies
• Generate installation order
• Handle version conflicts

Bài tập 3: Network Flow

Implement maximum flow algorithms:

• Ford-Fulkerson method
• Find bottlenecks trong network
• Applications: Traffic flow, resource allocation

Bài tập 4: Minimum Spanning Tree

Build network infrastructure optimizer:

• Cities as vertices, cable costs as weights
• Find minimum cost to connect all cities
• Compare Kruskal's vs Prim's algorithms

📋 Tóm tắt

Các điểm quan trọng

Graph Fundamentals:

• Representation: Adjacency list vs matrix
• Types: Directed vs undirected, weighted vs unweighted
• Properties: Connected, cyclic, bipartite

Essential Algorithms:

• Traversal: DFS, BFS for exploration
• Shortest Path: Dijkstra, Bellman-Ford, Floyd-Warshall
• Topological Sort: Dependency resolution
• Cycle Detection: Deadlock prevention

Algorithm Selection:

• DFS: When you need to explore all possibilities
• BFS: For shortest path trong unweighted graphs
• Dijkstra: Single-source shortest path với non-negative weights
• Bellman-Ford: When negative weights are possible

Best Practices

Implementation:

• Choose appropriate graph representation
• Handle edge cases (empty graphs, disconnected components)
• Use efficient data structures (priority queue cho Dijkstra)
• Consider space-time tradeoffs

Real-world Considerations:

• Scalability: Large graphs require optimized algorithms
• Dynamic graphs: Handle edge insertions/deletions
• Approximation: Sometimes exact solutions are too expensive
• Parallel processing: Distribute graph computations

Chuẩn bị cho bài tiếp theo

Bài học cuối cùng sẽ tìm hiểu về Mathematical Algorithms:

• Number Theory: GCD, LCM, prime numbers
• Modular Arithmetic: Fast exponentiation, modular inverse
• Combinatorics: Permutations, combinations
• Probability: Random algorithms, Monte Carlo methods

Graph algorithms are essential cho modeling real-world relationships. Master these concepts để solve complex connectivity và optimization problems!