【数据结构】【图】图算法考点精讲与实战代码
·
图是数据结构中的重要内容，也是互联网大厂笔试面试的常考考点。下面我为你详细梳理图的考点，并结合典型题目和Python、Java、C++三种语言的代码实现，助你高效备考。
📊 图（Graph）考点详解与实战
✨ 一、图的基本概念
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成的数据结构，通常表示为 G(V, E)，其中 V 是顶点集，E 是边集。
主要概念：
- 无向图：边没有方向
- 有向图：边有方向
- 完全图：任意两个顶点之间都有边（无向完全图有
n(n-1)/2条边，有向完全图有n(n-1)条边） - 连通图：图中任意两个顶点都是连通的
- 强连通图：有向图中任意一对顶点互相可达
- 度：与顶点关联的边数（有向图中分为入度和出度）
- 权：边上的数值权重
重要性质：
- 无向图所有顶点度之和等于边数的2倍
- 有向图所有顶点入度之和等于出度之和等于边数
- n个顶点的无向连通图最少有
n-1条边，最多有n(n-1)/2条边 - n个顶点的有向强连通图最少有
n条边（形成一个环），最多有n(n-1)条边
💾 二、图的存储结构
1. 邻接矩阵
使用二维数组存储顶点间的邻接关系。
# Python实现
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0] * vertices for _ in range(vertices)]
def add_edge(self, u, v, weight=1):
self.graph[u][v] = weight
# 如果是无向图，还需要添加 self.graph[v][u] = weight
// Java实现
public class Graph {
private int V;
private int[][] graph;
public Graph(int vertices) {
this.V = vertices;
this.graph = new int[V][V];
}
public void addEdge(int u, int v, int weight) {
graph[u][v] = weight;
// 如果是无向图，还需要添加 graph[v][u] = weight;
}
}
// C++实现
class Graph {
private:
int V;
vector<vector<int>> graph;
public:
Graph(int vertices) : V(vertices), graph(vertices, vector<int>(vertices, 0)) {}
void addEdge(int u, int v, int weight) {
graph[u][v] = weight;
// 如果是无向图，还需要添加 graph[v][u] = weight;
}
};
2. 邻接表
使用链表存储每个顶点的邻接顶点。
# Python实现（使用字典和列表）
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
def add_edge(self, u, v, weight=None):
if weight:
self.graph[u].append((v, weight))
else:
self.graph[u].append(v)
# 如果是无向图，还需要添加 self.graph[v].append(u) 或 self.graph[v].append((u, weight))
// Java实现（使用HashMap和LinkedList）
import java.util.*;
public class Graph {
private int V;
private Map<Integer, List<Integer>> graph;
public Graph(int vertices) {
this.V = vertices;
this.graph = new HashMap<>();
for (int i = 0; i < V; i++) {
graph.put(i, new LinkedList<>());
}
}
public void addEdge(int u, int v) {
graph.get(u).add(v);
// 如果是无向图，还需要添加 graph.get(v).add(u);
}
// 对于加权图，可以使用 Map<Integer, List<int[]>>，其中int[]存储[邻接顶点, 权重]
}
// C++实现
#include <vector>
using namespace std;
class Graph {
private:
int V;
vector<vector<int>> adjList;
public:
Graph(int vertices) : V(vertices), adjList(vertices) {}
void addEdge(int u, int v) {
adjList[u].push_back(v);
// 如果是无向图，还需要添加 adjList[v].push_back(u);
}
};
存储结构对比：
| 存储方式 | 空间复杂度 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | O(V²) | 查边: O(1) | 稠密图 |
| 邻接表 | O(V+E) | 查边: O(degree(V)) | 稀疏图 |
🔍 三、图的遍历算法
1. 深度优先搜索（DFS）
# Python实现
def dfs(graph, start):
visited = set()
stack = [start]
result = []
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
result.append(vertex)
# 将未访问的邻接节点加入栈（注意逆序加入以保证顺序）
for neighbor in reversed(graph[vertex]):
if neighbor not in visited:
stack.append(neighbor)
return result
// Java实现
public List<Integer> dfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Stack<Integer> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
stack.push(start);
while (!stack.isEmpty()) {
int vertex = stack.pop();
if (!visited.contains(vertex)) {
visited.add(vertex);
result.add(vertex);
// 将未访问的邻接节点加入栈（注意逆序加入以保证顺序）
List<Integer> neighbors = graph.get(vertex);
for (int i = neighbors.size() - 1; i >= 0; i--) {
int neighbor = neighbors.get(i);
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
return result;
}
// C++实现
vector<int> dfs(vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false);
stack<int> st;
vector<int> result;
st.push(start);
while (!st.empty()) {
int vertex = st.top();
st.pop();
if (!visited[vertex]) {
visited[vertex] = true;
result.push_back(vertex);
// 将未访问的邻接节点加入栈（注意逆序加入以保证顺序）
for (auto it = graph[vertex].rbegin(); it != graph[vertex].rend(); ++it) {
if (!visited[*it]) {
st.push(*it);
}
}
}
}
return result;
}
2. 广度优先搜索（BFS）
# Python实现
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
result = []
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
result.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
return result
// Java实现
public List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
List<Integer> result = new ArrayList<>();
queue.offer(start);
while (!queue.isEmpty()) {
int vertex = queue.poll();
if (!visited.contains(vertex)) {
visited.add(vertex);
result.add(vertex);
for (int neighbor : graph.get(vertex)) {
if (!visited.contains(neighbor)) {
queue.offer(neighbor);
}
}
}
}
return result;
}
// C++实现
vector<int> bfs(vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false);
queue<int> q;
vector<int> result;
q.push(start);
while (!q.empty()) {
int vertex = q.front();
q.pop();
if (!visited[vertex]) {
visited[vertex] = true;
result.push_back(vertex);
for (int neighbor : graph[vertex]) {
if (!visited[neighbor]) {
q.push(neighbor);
}
}
}
}
return result;
}
🧠 四、图的应用算法
1. 最短路径算法
Dijkstra算法（单源最短路径，无负权边）
# Python实现
import heapq
def dijkstra(graph, start):
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
// Java实现
public int[] dijkstra(List<List<int[]>> graph, int start) {
int n = graph.size();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
heap.offer(new int[]{0, start});
while (!heap.isEmpty()) {
int[] current = heap.poll();
int d = current[0], u = current[1];
if (d > dist[u]) continue;
for (int[] edge : graph.get(u)) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
heap.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
// C++实现
vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
heap.push({0, start});
while (!heap.empty()) {
int d = heap.top().first;
int u = heap.top().second;
heap.pop();
if (d > dist[u]) continue;
for (auto& edge : graph[u]) {
int v = edge.first;
int w = edge.second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
heap.push({dist[v], v});
}
}
}
return dist;
}
2. 最小生成树算法
Kruskal算法
# Python实现
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * 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):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.rank[rx] < self.rank[ry]:
self.parent[rx] = ry
elif self.rank[rx] > self.rank[ry]:
self.parent[ry] = rx
else:
self.parent[ry] = rx
self.rank[rx] += 1
return True
def kruskal(n, edges):
uf = UnionFind(n)
edges.sort(key=lambda x: x[2])
mst = []
total_weight = 0
for u, v, w in edges:
if uf.union(u, v):
mst.append((u, v, w))
total_weight += w
if len(mst) == n - 1:
break
return mst, total_weight
3. 拓扑排序（用于有向无环图）
# Python实现
def topological_sort(graph):
n = len(graph)
in_degree = [0] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1
queue = collections.deque()
for i in range(n):
if in_degree[i] == 0:
queue.append(i)
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return result if len(result) == n else [] # 如果存在环，返回空列表
💡 五、互联网大厂常见面试题
1. 判断图是否有环
题目描述：给定一个有向图，判断图中是否存在环。
解题思路：使用拓扑排序或DFS。如果能完成拓扑排序（所有顶点都能处理），则无环；否则有环。
# Python实现（使用DFS检测环）
def has_cycle_dfs(graph):
n = len(graph)
visited = [False] * n
on_stack = [False] * n
def dfs(u):
visited[u] = True
on_stack[u] = True
for v in graph[u]:
if not visited[v]:
if dfs(v):
return True
elif on_stack[v]:
return True
on_stack[u] = False
return False
for i in range(n):
if not visited[i]:
if dfs(i):
return True
return False
2. 课程表问题（LeetCode 207）
题目描述：总共有n门课程，编号从0到n-1。先修条件数组中prerequisites[i] = [a_i, b_i]表示要学习课程a_i必须先修课程b_i。判断是否可能完成所有课程？
解题思路：将课程关系构建为有向图，判断图中是否有环。
// Java实现
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int[] inDegree = new int[numCourses];
for (int[] pre : prerequisites) {
graph.get(pre[1]).add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
count++;
for (int v : graph.get(u)) {
inDegree[v]--;
if (inDegree[v] == 0) {
queue.offer(v);
}
}
}
return count == numCourses;
}
3. 克隆图（LeetCode 133）
题目描述：深度拷贝一个无向连通图。
解题思路：使用DFS或BFS遍历图，同时用哈希表记录已克隆的节点。
// C++实现
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
unordered_map<Node*, Node*> copies;
queue<Node*> q;
q.push(node);
copies[node] = new Node(node->val);
while (!q.empty()) {
Node* curr = q.front();
q.pop();
for (Node* neighbor : curr->neighbors) {
if (copies.find(neighbor) == copies.end()) {
copies[neighbor] = new Node(neighbor->val);
q.push(neighbor);
}
copies[curr]->neighbors.push_back(copies[neighbor]);
}
}
return copies[node];
}
🎯 六、笔试面试备考建议
- 掌握基础概念：深入理解图的基本概念、存储方式和遍历算法。
- 熟练经典算法：Dijkstra、Floyd、Kruskal、Prim、拓扑排序等经典算法务必掌握。
- 多语言实现：能用Python、Java、C++三种语言实现常见图算法。
- 复杂度分析：对每种算法的时间复杂度和空间复杂度有清晰认识。
- 实战练习：在LeetCode、牛客网等平台多做图相关题目。
- 举一反三：理解算法本质，能够解决变种问题。
📊 图算法复杂度总结
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| DFS | O(V+E) | O(V) | 连通性检测、拓扑排序 |
| BFS | O(V+E) | O(V) | 最短路径（未加权）、连通分量 |
| Dijkstra | O((V+E)logV) | O(V) | 单源最短路径（无负权边） |
| Floyd | O(V³) | O(V²) | 多源最短路径 |
| Kruskal | O(ElogE) | O(V) | 最小生成树 |
| 拓扑排序 | O(V+E) | O(V) | 任务调度、课程安排 |
更多推荐
6
0- 0
已为社区贡献3条内容
所有评论(0)