owlingcode

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (implicit with recursion or explicit).

Basic DFS Implementation

vector<vector<int>> adj;
vector<bool> visited;

void dfs(int v) {
    visited[v] = true;
    cout << v << " "; // Process vertex
    
    for (int neighbor : adj[v]) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

// Usage
int n = 5;
adj.resize(n + 1);
visited.resize(n + 1, false);

// Start DFS from vertex 1
dfs(1);

Iterative DFS

void dfs_iterative(int start) {
    stack<int> st;
    vector<bool> visited(n + 1, false);
    
    st.push(start);
    
    while (!st.empty()) {
        int v = st.top();
        st.pop();
        
        if (visited[v]) continue;
        
        visited[v] = true;
        cout << v << " ";
        
        // Add neighbors in reverse order for same traversal as recursive
        for (int i = adj[v].size() - 1; i >= 0; i--) {
            int neighbor = adj[v][i];
            if (!visited[neighbor]) {
                st.push(neighbor);
            }
        }
    }
}

Breadth-First Search (BFS)

BFS explores all vertices at the current depth before moving to vertices at the next depth level. It uses a queue.

Basic BFS Implementation

void bfs(int start) {
    queue<int> q;
    vector<bool> visited(n + 1, false);
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        
        cout << v << " "; // Process vertex
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

BFS with Distance Calculation

vector<int> bfs_distance(int start) {
    vector<int> dist(n + 1, -1); // -1 means not visited
    queue<int> q;
    
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        
        for (int neighbor : adj[v]) {
            if (dist[neighbor] == -1) { // Not visited
                dist[neighbor] = dist[v] + 1;
                q.push(neighbor);
            }
        }
    }
    
    return dist; // Returns shortest distance to all vertices
}

Connected Components

Find all connected components in an undirected graph using DFS or BFS.

vector<vector<int>> components;
vector<bool> visited;

void dfs_component(int v, vector<int>& component) {
    visited[v] = true;
    component.push_back(v);
    
    for (int neighbor : adj[v]) {
        if (!visited[neighbor]) {
            dfs_component(neighbor, component);
        }
    }
}

void find_components() {
    visited.assign(n + 1, false);
    components.clear();
    
    for (int v = 1; v <= n; v++) {
        if (!visited[v]) {
            vector<int> component;
            dfs_component(v, component);
            components.push_back(component);
        }
    }
    
    cout << "Number of components: " << components.size() << endl;
}

Cycle Detection

Cycle Detection in Undirected Graph

bool has_cycle_undirected() {
    vector<bool> visited(n + 1, false);
    
    function<bool(int, int)> dfs = [&](int v, int parent) -> bool {
        visited[v] = true;
        
        for (int neighbor : adj[v]) {
            if (neighbor == parent) continue; // Skip parent edge
            
            if (visited[neighbor] || dfs(neighbor, v)) {
                return true; // Cycle found
            }
        }
        return false;
    };
    
    for (int v = 1; v <= n; v++) {
        if (!visited[v] && dfs(v, -1)) {
            return true;
        }
    }
    return false;
}

Cycle Detection in Directed Graph

bool has_cycle_directed() {
    vector<int> color(n + 1, 0); // 0 = white, 1 = gray, 2 = black
    
    function<bool(int)> dfs = [&](int v) -> bool {
        color[v] = 1; // Mark as gray (being processed)
        
        for (int neighbor : adj[v]) {
            if (color[neighbor] == 1) { // Back edge to gray vertex
                return true; // Cycle found
            }
            if (color[neighbor] == 0 && dfs(neighbor)) {
                return true;
            }
        }
        
        color[v] = 2; // Mark as black (fully processed)
        return false;
    };
    
    for (int v = 1; v <= n; v++) {
        if (color[v] == 0 && dfs(v)) {
            return true;
        }
    }
    return false;
}

Topological Sorting

Linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), u comes before v in the ordering.

DFS-based Topological Sort

vector<int> topological_sort() {
    vector<bool> visited(n + 1, false);
    stack<int> result;
    
    function<void(int)> dfs = [&](int v) {
        visited[v] = true;
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
        
        result.push(v); // Add to result after processing all descendants
    };
    
    for (int v = 1; v <= n; v++) {
        if (!visited[v]) {
            dfs(v);
        }
    }
    
    vector<int> topo_order;
    while (!result.empty()) {
        topo_order.push_back(result.top());
        result.pop();
    }
    
    return topo_order;
}

Kahn's Algorithm (BFS-based)

vector<int> kahn_topological_sort() {
    vector<int> in_degree(n + 1, 0);
    
    // Calculate in-degrees
    for (int v = 1; v <= n; v++) {
        for (int neighbor : adj[v]) {
            in_degree[neighbor]++;
        }
    }
    
    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (in_degree[v] == 0) {
            q.push(v);
        }
    }
    
    vector<int> result;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        result.push_back(v);
        
        for (int neighbor : adj[v]) {
            in_degree[neighbor]--;
            if (in_degree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }
    
    // Check if graph has cycle
    if (result.size() != n) {
        return {}; // Graph has cycle, no topological ordering
    }
    
    return result;
}

Bipartite Graph Detection

A bipartite graph can be colored with two colors such that no two adjacent vertices have the same color.

bool is_bipartite() {
    vector<int> color(n + 1, -1); // -1 = uncolored, 0 = color1, 1 = color2
    
    function<bool(int, int)> dfs = [&](int v, int c) -> bool {
        color[v] = c;
        
        for (int neighbor : adj[v]) {
            if (color[neighbor] == -1) {
                if (!dfs(neighbor, 1 - c)) {
                    return false;
                }
            } else if (color[neighbor] == c) {
                return false; // Same color as current vertex
            }
        }
        return true;
    };
    
    for (int v = 1; v <= n; v++) {
        if (color[v] == -1) {
            if (!dfs(v, 0)) {
                return false;
            }
        }
    }
    return true;
}

// Get the two sets of a bipartite graph
pair<vector<int>, vector<int>> get_bipartite_sets() {
    vector<int> color(n + 1, -1);
    vector<int> set1, set2;
    
    // Assume graph is bipartite (check first with is_bipartite())
    function<void(int, int)> dfs = [&](int v, int c) {
        color[v] = c;
        if (c == 0) set1.push_back(v);
        else set2.push_back(v);
        
        for (int neighbor : adj[v]) {
            if (color[neighbor] == -1) {
                dfs(neighbor, 1 - c);
            }
        }
    };
    
    for (int v = 1; v <= n; v++) {
        if (color[v] == -1) {
            dfs(v, 0);
        }
    }
    
    return {set1, set2};
}

Graph Traversal Applications

Implementation Tips