09.01_基础图论

基础图论

问题描述

基础图论处理图的遍历和基本性质，包括DFS、BFS、拓扑排序和强连通分量等问题。

深度优先搜索

算法思想

沿着一条路径尽可能深入
使用栈或递归实现
适用于路径查找和连通性判断
时间复杂度 $\mathcal{O}(V+E)$

代码实现

c++
java
python

class Solution {
public:
    vector<vector<int>> adj;  // 邻接表
    vector<bool> visited;     // 访问标记
    
    void dfs(int v) {
        visited[v] = true;
        for (int u : adj[v]) {
            if (!visited[u]) {
                dfs(u);
            }
        }
    }
    
    // 检测环
    bool hasCycle(int v, int parent) {
        visited[v] = true;
        for (int u : adj[v]) {
            if (!visited[u]) {
                if (hasCycle(u, v)) return true;
            } else if (u != parent) {
                return true;
            }
        }
        return false;
    }
};

class Solution {
    private List<List<Integer>> adj;  // 邻接表
    private boolean[] visited;         // 访问标记
    
    public void dfs(int v) {
        visited[v] = true;
        for (int u : adj.get(v)) {
            if (!visited[u]) {
                dfs(u);
            }
        }
    }
    
    // 检测环
    public boolean hasCycle(int v, int parent) {
        visited[v] = true;
        for (int u : adj.get(v)) {
            if (!visited[u]) {
                if (hasCycle(u, v)) return true;
            } else if (u != parent) {
                return true;
            }
        }
        return false;
    }
}

class Solution:
    def __init__(self):
        self.adj = []      # 邻接表
        self.visited = []  # 访问标记
    
    def dfs(self, v: int) -> None:
        self.visited[v] = True
        for u in self.adj[v]:
            if not self.visited[u]:
                self.dfs(u)
    
    # 检测环
    def hasCycle(self, v: int, parent: int) -> bool:
        self.visited[v] = True
        for u in self.adj[v]:
            if not self.visited[u]:
                if self.hasCycle(u, v):
                    return True
            elif u != parent:
                return True
        return False

广度优先搜索

算法思想

逐层遍历图中节点
使用队列实现
适用于最短路径和层次遍历
时间复杂度 $\mathcal{O}(V+E)$

代码实现

c++
java
python

class Solution {
public:
    vector<vector<int>> adj;  // 邻接表
    vector<bool> visited;     // 访问标记
    
    void bfs(int start) {
        queue<int> q;
        q.push(start);
        visited[start] = true;
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            
            for (int u : adj[v]) {
                if (!visited[u]) {
                    visited[u] = true;
                    q.push(u);
                }
            }
        }
    }
};

class Solution {
    private List<List<Integer>> adj;  // 邻接表
    private boolean[] visited;         // 访问标记
    
    public void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        
        while (!q.isEmpty()) {
            int v = q.poll();
            
            for (int u : adj.get(v)) {
                if (!visited[u]) {
                    visited[u] = true;
                    q.offer(u);
                }
            }
        }
    }
}

class Solution:
    def bfs(self, start: int) -> None:
        q = deque([start])
        self.visited[start] = True
        
        while q:
            v = q.popleft()
            
            for u in self.adj[v]:
                if not self.visited[u]:
                    self.visited[u] = True
                    q.append(u)

时间复杂度分析

算法时间复杂度空间复杂度

DFS	$\mathcal{O}(V+E)$	$\mathcal{O}(V)$
BFS	$\mathcal{O}(V+E)$	$\mathcal{O}(V)$
拓扑排序	$\mathcal{O}(V+E)$	$\mathcal{O}(V)$
强连通分量	$\mathcal{O}(V+E)$	$\mathcal{O}(V)$

应用场景

路径查找
连通性判断
环路检测
拓扑排序
二分图判定

注意事项

图的表示方式
访问标记的重置
递归栈的深度
连通性的处理
环路的判断

常见变形

拓扑排序

cpp
java
python

class Solution {
public:
    vector<int> topologicalSort(vector<vector<int>>& adj) {
        int n = adj.size();
        vector<int> indegree(n);
        vector<int> result;
        
        // 计算入度
        for (const auto& edges : adj) {
            for (int v : edges) {
                indegree[v]++;
            }
        }
        
        // BFS
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            result.push_back(v);
            
            for (int u : adj[v]) {
                if (--indegree[u] == 0) {
                    q.push(u);
                }
            }
        }
        
        return result.size() == n ? result : vector<int>();
    }
};

class Solution {
    public List<Integer> topologicalSort(List<List<Integer>> adj) {
        int n = adj.size();
        int[] indegree = new int[n];
        List<Integer> result = new ArrayList<>();
        
        // 计算入度
        for (List<Integer> edges : adj) {
            for (int v : edges) {
                indegree[v]++;
            }
        }
        
        // BFS
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }
        
        while (!q.isEmpty()) {
            int v = q.poll();
            result.add(v);
            
            for (int u : adj.get(v)) {
                if (--indegree[u] == 0) {
                    q.offer(u);
                }
            }
        }
        
        return result.size() == n ? result : new ArrayList<>();
    }
}

class Solution:
    def topologicalSort(self, adj: List[List[int]]) -> List[int]:
        n = len(adj)
        indegree = [0] * n
        result = []
        
        # 计算入度
        for edges in adj:
            for v in edges:
                indegree[v] += 1
        
        # BFS
        q = deque([i for i in range(n) if indegree[i] == 0])
        
        while q:
            v = q.popleft()
            result.append(v)
            
            for u in adj[v]:
                indegree[u] -= 1
                if indegree[u] == 0:
                    q.append(u)
        
        return result if len(result) == n else []

二分图判定

cpp
java
python

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);
        
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!dfs(graph, i, 0, color)) {
                    return false;
                }
            }
        }
        return true;
    }
    
private:
    bool dfs(vector<vector<int>>& graph, int v, int c, vector<int>& color) {
        color[v] = c;
        for (int u : graph[v]) {
            if (color[u] == -1) {
                if (!dfs(graph, u, c ^ 1, color)) {
                    return false;
                }
            } else if (color[u] == c) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
    public boolean isBipartite(List<List<Integer>> graph) {
        int n = graph.size();
        int[] color = new int[n];
        Arrays.fill(color, -1);
        
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!dfs(graph, i, 0, color)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean dfs(List<List<Integer>> graph, int v, int c, int[] color) {
        color[v] = c;
        for (int u : graph.get(v)) {
            if (color[u] == -1) {
                if (!dfs(graph, u, c ^ 1, color)) {
                    return false;
                }
            } else if (color[u] == c) {
                return false;
            }
        }
        return true;
    }
}

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n
        
        def dfs(v: int, c: int) -> bool:
            color[v] = c
            for u in graph[v]:
                if color[u] == -1:
                    if not dfs(u, c ^ 1):
                        return False
                elif color[u] == c:
                    return False
            return True
        
        for i in range(n):
            if color[i] == -1:
                if not dfs(i, 0):
                    return False
        return True