@TOC
图的基本概念
图：由顶点（vertex）和边（edge）组成。
顶点—-具体事物
边—-具体事物之间的联系
顶点的集合$V$，边的集合$E$，图记为$G = (V,E)$
图的存储结构
一般分为两种 ： 邻接矩阵、邻接表
邻接矩阵
由一个二维数组实现,比较简单，但是在存储稠密图时比较不划算。
$G[i][j]$表示的是顶点i与顶点j的关系。
如果顶点i和顶点j之间有边相连， $G[i][j]=1$
如果顶点i和顶点j之间无边相连， $G[i][j]=0$
对于无向图：$G[i][j]=G[j][i]$
如果边上面有权值，则$G[i][j] = val$
邻接表
通过使用$vector$实现
存点
1
2
3
4
5
6
7
8
9
| struct edge {
int v, w;
edge(){};
edge(int V, int W) {
v = V;
w = W;
}
};
vector<edge> G[MAXN];
|
加边
1
2
3
4
| void addEdge(int u, int v, int w) {
G[u].push_back(edge(v, w));
G[v].push_back(edge(u, w));
}
|
图的遍历
有深度优先遍历和广度优先遍历两种
深度优先
初始状态是图中所有顶点未曾被访问，可从图中顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <queue>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 205;
int n, m;
bool v[MAXN];
vector<int> G[MAXN];
void addEdge(int u, int v) {
G[u].push_back(v);
}
void dfs(int x) {
printf("%d ", x);
v[x] = 1;
sort(G[x].begin(), G[x].end());
for(int i = 0;i < G[x].size(); i++) {
if(! v[G[x][i]]) {
v[G[x][i]] = 1;
dfs(G[x][i]);
}
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1;i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
}
for(int i = 1;i <= n; i++) {
if(! v[i]) dfs(i);
}
return 0;
}
|
广度优先
假设从图中某顶点v出发，在访问v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1，2，…的顶点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <queue>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 205;
int n, m;
bool v[MAXN];
vector<int> G[MAXN];
void addEdge(int u, int v) {
G[u].push_back(v);
}
void bfs(int k) {
queue<int> q;
q.push(k);
v[k] = 1;
printf("%d ", k);
while(q.size()) {
int a = q.front();
q.pop();
sort(G[a].begin(), G[a].end());
for(int i = 0;i < G[a].size(); i++) {
if(! v[G[a][i]]) {
v[G[a][i]] = 1;
printf("%d ", G[a][i]);
q.push(G[a][i]);
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1;i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
}
for(int i = 1;i <= n; i++) {
if(! v[i]) bfs(i);
}
return 0;
}
|