课程进度 43% · 第5/10章第5/10章 · 标签 1/3
— 1 —
图的基本概念与存储
图分为有向图、无向图、带权图等。常用存储方式有邻接矩阵和邻接表：
cpp
1
// 邻接矩阵存储
2
const int N = 100;
3
int g[N][N]; // g[i][j]=1表示i到j有边
4
// 邻接表存储
5
vector<int> adj[N]; // adj[i]存储与i相邻的点
6
// 带权邻接表
7
vector<pair<int,int>> adjw[N]; // adjw[i]存储(i,权值)
— 2 —
图的遍历算法（DFS与BFS）
图的遍历主要有深度优先搜索（DFS）和广度优先搜索（BFS）：
cpp
1
// DFS递归
2
void dfs(int u, vector<bool>& vis, vector<int> adj[]) {
3
vis[u] = true;
4
cout << u << ' ';
5
for (int v : adj[u]) if (!vis[v]) dfs(v, vis, adj);
6
}
7
// DFS非递归
8
void dfsIter(int start, vector<bool>& vis, vector<int> adj[]) {
9
stack<int> st; st.push(start);
10
while (!st.empty()) {
11
int u = st.top(); st.pop();
12
if (vis[u]) continue;
13
vis[u] = true;
14
cout << u << ' ';
15
for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it)
16
if (!vis[*it]) st.push(*it);
17
}
18
}
19
// BFS
20
void bfs(int start, vector<bool>& vis, vector<int> adj[]) {
21
queue<int> q; q.push(start); vis[start] = true;
22
while (!q.empty()) {
23
int u = q.front(); q.pop();
24
cout << u << ' ';
25
for (int v : adj[u]) if (!vis[v]) { vis[v] = true; q.push(v); }
26
}
27
}
邻接矩阵邻接表DFSBFS有向图无向图