09-图

💡 核心结论

图的本质

• 定义：节点（顶点）+ 边的集合，G = (V, E)

• 分类：有向/无向、有权/无权、连通/非连通

• 存储：邻接矩阵O(V²)、邻接表O(V+E)

• 遍历：DFS深度优先、BFS广度优先

• 应用：社交网络、地图导航、依赖关系

存储方式对比

方式	空间	查边	遍历邻居	适用
邻接矩阵	O(V²)	O(1)	O(V)	稠密图、需频繁查边
邻接表	O(V+E)	O(degree)	O(degree)	稀疏图、节省空间

图的遍历

算法	数据结构	空间	应用
DFS	栈/递归	O(V)	路径、连通性、拓扑排序
BFS	队列	O(V)	最短路径、层级关系

经典算法

• 最短路径：Dijkstra、Bellman-Ford、Floyd

• 最小生成树：Prim、Kruskal

• 拓扑排序：DFS、Kahn算法

• 强连通分量：Kosaraju、Tarjan

🎯 图的表示

邻接矩阵

# 无向图
graph = [
    [0, 1, 1, 0],  # 0连接1,2
    [1, 0, 0, 1],  # 1连接0,3
    [1, 0, 0, 1],  # 2连接0,3
    [0, 1, 1, 0]   # 3连接1,2
]

# 有向图
graph = [
    [0, 1, 0, 0],  # 0→1
    [0, 0, 1, 1],  # 1→2,3
    [0, 0, 0, 1],  # 2→3
    [0, 0, 0, 0]   # 3无出边
]

# 带权图
graph = [
    [0, 4, 2, 0],
    [4, 0, 0, 5],
    [2, 0, 0, 3],
    [0, 5, 3, 0]
]

邻接表

# 无向图
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# 有向图
graph = {
    0: [1],
    1: [2, 3],
    2: [3],
    3: []
}

# 带权图
graph = {
    0: [(1, 4), (2, 2)],
    1: [(0, 4), (3, 5)],
    2: [(0, 2), (3, 3)],
    3: [(1, 5), (2, 3)]
}

🌲 DFS深度优先

递归实现

def dfs(graph, node, visited):
    visited.add(node)
    print(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

应用：检测环

def has_cycle(graph):
    visited = set()
    rec_stack = set()
    
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True  # 找到环
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

🌊 BFS广度优先

最短路径

from collections import deque

def shortest_path(graph, start, end):
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        
        if node == end:
            return path
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None

🛤️ 拓扑排序

Kahn算法（BFS）

def topological_sort(graph):
    # 计算入度
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 入度为0的节点入队
    queue = [node for node in graph if in_degree[node] == 0]
    result = []
    
    while queue:
        node = queue.pop(0)
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == len(graph) else None

🎯 最短路径算法

Dijkstra算法（单源最短路径）

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    
    while pq:
        curr_dist, curr_node = heapq.heappop(pq)
        
        if curr_dist > distances[curr_node]:
            continue
        
        for neighbor, weight in graph[curr_node]:
            distance = curr_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

Floyd算法（所有点对最短路径）

def floyd(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    
    # 初始化
    for i in range(n):
        dist[i][i] = 0
        for j in range(n):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    
    # Floyd
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

🌳 最小生成树

Kruskal算法（并查集）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
            return True
        return False

def kruskal(n, edges):
    # edges: [(weight, u, v)]
    edges.sort()  # 按权重排序
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    for weight, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
    
    return mst, total_weight

📚 LeetCode练习

基础

• 200. Number of Islands

• 133. Clone Graph

• 207. Course Schedule

进阶

• 743. Network Delay Time

• 1584. Min Cost to Connect All Points

• 785. Is Graph Bipartite

💻 完整代码实现

Python 实现

"""
图的实现和基本算法
"""

from collections import deque, defaultdict


class Graph:
    """图的邻接表实现"""
    
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed
    
    def add_edge(self, u, v, weight=1):
        """添加边"""
        self.graph[u].append((v, weight))
        if not self.directed:
            self.graph[v].append((u, weight))
    
    def dfs(self, start):
        """深度优先遍历"""
        visited = set()
        result = []
        
        def dfs_helper(node):
            visited.add(node)
            result.append(node)
            for neighbor, _ in self.graph[node]:
                if neighbor not in visited:
                    dfs_helper(neighbor)
        
        dfs_helper(start)
        return result
    
    def bfs(self, start):
        """广度优先遍历"""
        visited = {start}
        queue = deque([start])
        result = []
        
        while queue:
            node = queue.popleft()
            result.append(node)
            
            for neighbor, _ in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return result
    
    def has_cycle(self):
        """检测有向图是否有环"""
        visited = set()
        rec_stack = set()
        
        def dfs(node):
            visited.add(node)
            rec_stack.add(node)
            
            for neighbor, _ in self.graph[node]:
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True
                elif neighbor in rec_stack:
                    return True
            
            rec_stack.remove(node)
            return False
        
        for node in self.graph:
            if node not in visited:
                if dfs(node):
                    return True
        return False
    
    def topological_sort(self):
        """拓扑排序（Kahn算法）"""
        in_degree = {node: 0 for node in self.graph}
        for node in self.graph:
            for neighbor, _ in self.graph[node]:
                in_degree[neighbor] += 1
        
        queue = [node for node in self.graph if in_degree[node] == 0]
        result = []
        
        while queue:
            node = queue.pop(0)
            result.append(node)
            
            for neighbor, _ in self.graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        return result if len(result) == len(self.graph) else None


def dijkstra(graph, start):
    """Dijkstra最短路径算法"""
    import heapq
    
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        curr_dist, curr_node = heapq.heappop(pq)
        
        if curr_dist > distances[curr_node]:
            continue
        
        for neighbor, weight in graph[curr_node]:
            distance = curr_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances


def demo():
    """演示图操作"""
    print("=== 图演示 ===\n")
    
    # 创建无向图
    g = Graph(directed=False)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 3)
    
    print("DFS遍历:", g.dfs(0))
    print("BFS遍历:", g.bfs(0))
    
    # 有向图
    print("\n=== 拓扑排序 ===\n")
    dag = Graph(directed=True)
    dag.add_edge(5, 2)
    dag.add_edge(5, 0)
    dag.add_edge(4, 0)
    dag.add_edge(4, 1)
    dag.add_edge(2, 3)
    dag.add_edge(3, 1)
    
    print("拓扑排序:", dag.topological_sort())
    
    # Dijkstra
    print("\n=== Dijkstra最短路径 ===\n")
    graph_dict = {
        0: [(1, 4), (2, 2)],
        1: [(2, 1), (3, 5)],
        2: [(3, 3)],
        3: []
    }
    distances = dijkstra(graph_dict, 0)
    print("从节点0到各节点的最短距离:", distances)


if __name__ == '__main__':
    demo()

C++ 实现

/**
 * 图的实现和基本算法
 */

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>

using namespace std;

class Graph {
private:
    unordered_map<int, vector<pair<int, int>>> graph;  // node -> [(neighbor, weight)]
    bool directed;

public:
    Graph(bool dir = false) : directed(dir) {}
    
    void addEdge(int u, int v, int weight = 1) {
        graph[u].push_back({v, weight});
        if (!directed) {
            graph[v].push_back({u, weight});
        }
    }
    
    // DFS递归
    void dfsHelper(int node, unordered_set<int>& visited, vector<int>& result) {
        visited.insert(node);
        result.push_back(node);
        
        for (auto& [neighbor, weight] : graph[node]) {
            if (!visited.count(neighbor)) {
                dfsHelper(neighbor, visited, result);
            }
        }
    }
    
    vector<int> dfs(int start) {
        unordered_set<int> visited;
        vector<int> result;
        dfsHelper(start, visited, result);
        return result;
    }
    
    // BFS
    vector<int> bfs(int start) {
        unordered_set<int> visited;
        queue<int> q;
        vector<int> result;
        
        visited.insert(start);
        q.push(start);
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            result.push_back(node);
            
            for (auto& [neighbor, weight] : graph[node]) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
        
        return result;
    }
    
    // 检测环（有向图）
    bool hasCycleHelper(int node, unordered_set<int>& visited, 
                       unordered_set<int>& recStack) {
        visited.insert(node);
        recStack.insert(node);
        
        for (auto& [neighbor, weight] : graph[node]) {
            if (!visited.count(neighbor)) {
                if (hasCycleHelper(neighbor, visited, recStack)) {
                    return true;
                }
            } else if (recStack.count(neighbor)) {
                return true;
            }
        }
        
        recStack.erase(node);
        return false;
    }
    
    bool hasCycle() {
        unordered_set<int> visited;
        unordered_set<int> recStack;
        
        for (auto& [node, edges] : graph) {
            if (!visited.count(node)) {
                if (hasCycleHelper(node, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // 拓扑排序（Kahn算法）
    vector<int> topologicalSort() {
        unordered_map<int, int> inDegree;
        
        for (auto& [node, edges] : graph) {
            if (!inDegree.count(node)) {
                inDegree[node] = 0;
            }
            for (auto& [neighbor, weight] : edges) {
                inDegree[neighbor]++;
            }
        }
        
        queue<int> q;
        for (auto& [node, degree] : inDegree) {
            if (degree == 0) {
                q.push(node);
            }
        }
        
        vector<int> result;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            result.push_back(node);
            
            for (auto& [neighbor, weight] : graph[node]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        return result.size() == inDegree.size() ? result : vector<int>();
    }
};

// Dijkstra最短路径
unordered_map<int, int> dijkstra(
    const unordered_map<int, vector<pair<int, int>>>& graph, 
    int start) {
    
    unordered_map<int, int> distances;
    for (auto& [node, edges] : graph) {
        distances[node] = INT_MAX;
    }
    distances[start] = 0;
    
    // 优先队列：(distance, node)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [currDist, currNode] = pq.top();
        pq.pop();
        
        if (currDist > distances[currNode]) {
            continue;
        }
        
        if (graph.count(currNode)) {
            for (auto& [neighbor, weight] : graph.at(currNode)) {
                int distance = currDist + weight;
                if (distance < distances[neighbor]) {
                    distances[neighbor] = distance;
                    pq.push({distance, neighbor});
                }
            }
        }
    }
    
    return distances;
}

int main() {
    cout << "=== 图算法演示 ===" << endl << endl;
    
    // 创建无向图
    Graph g(false);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    
    cout << "DFS遍历: ";
    vector<int> dfs_result = g.dfs(0);
    for (int node : dfs_result) {
        cout << node << " ";
    }
    cout << endl;
    
    cout << "BFS遍历: ";
    vector<int> bfs_result = g.bfs(0);
    for (int node : bfs_result) {
        cout << node << " ";
    }
    cout << endl << endl;
    
    // 拓扑排序
    cout << "拓扑排序:" << endl;
    Graph dag(true);
    dag.addEdge(5, 2);
    dag.addEdge(5, 0);
    dag.addEdge(4, 0);
    dag.addEdge(4, 1);
    dag.addEdge(2, 3);
    dag.addEdge(3, 1);
    
    vector<int> topo = dag.topologicalSort();
    cout << "  ";
    for (int node : topo) {
        cout << node << " ";
    }
    cout << endl << endl;
    
    // Dijkstra
    cout << "Dijkstra最短路径:" << endl;
    unordered_map<int, vector<pair<int, int>>> weighted_graph;
    weighted_graph[0] = {{1, 4}, {2, 2}};
    weighted_graph[1] = {{2, 1}, {3, 5}};
    weighted_graph[2] = {{3, 3}};
    weighted_graph[3] = {};
    
    auto distances = dijkstra(weighted_graph, 0);
    for (auto& [node, dist] : distances) {
        cout << "  到节点" << node << "的距离: " << dist << endl;
    }
    
    return 0;
}