图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
Concept of Graph
Storage and Traversal of Graphs
所谓遍历(Traversal)，是指沿着某条搜索路线，依次对图中每个顶点均做一次访问。
邻接矩阵
使用一个二维数组 a[i][j] 为0或1表示i -> j这条边是否存在。
如果是赋权图，a[i][j]可以直接存储i -> j的边权。
邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。
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
using namespace std;
const int N = 1e5+5, M = 2e5+5;
int n, m, u, v, c, a[N][N];
int main()
{
//无向图赋权
cin>>n>>m;
memset(a, 0, sizeof(a));
for(;m;--m)
{
cin>>u>>v>>c;
a[u][v] = a[v][u] = c;
}
//邻接矩阵遍历 O(n^2)
for(int u = 1; u<=n; ++u)
{
for(int v = 1; v<=n; ++v)
{
printf("%d->%d : %d\n", u, v, a[u][v]);
}
}
}
邻接表
使用一个支持动态增加元素的数据结构构成的数组，如 vector
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//无向赋权图
int n,m,u,v,c;
struct Edge
{
int v,c;
Edge(int _v,int _c){v=_v,c=_c;} //结构体函数
};
vector<Edge> a[N];
int main()
{
cin>>n>>m;
memset(a,0,sizeof(a));
for(;m;--m)
{
cin>>u>>v>>c;
a[u].push_back(Edge(v,c)); //引用结构体函数
a[v].push_back(Edge(u,c));
}
}
//遍历O(n+m)
//(写法1)
for(int i=1;i<=n;i++) //起点
{
for(auto [v,w]:a[i]) //遍历vector里面函数的所有变量,把a[i]中的变量取出来，赋给v,w
{
cout<<i<<>"->"<<v<<" "<<w<<endl;
}
}
//(写法2)
for(int u=1;u<=n;++u)
{
for(int i=0;i<a[u].size();++i)
{
int v=a[u][i].v,c=a[u][i].c;
printf("%d->%d : %d\n",u,v,c);
}
}
// for(auto x:b[i]) 可以遍历一个vector<node> b
// x -> [v,c] == int v=x.v , c=x.c;
//(写法3)深度优先搜索
void dfs(int u)
{
vis[u] = 1;
printf("%d visited!\n", u);
for(int i = 0; i<a[u].size(); ++i)
{
int v = a[u][i].v, c = a[u][i].c;
if(vis[v])continue;
dfs(v);
}
}
//（写法4）广度优先搜索
void bfs(int st)
{
queue<int> Q;
Q.push(st);
memset(vis, 0, sizeof(vis));
while(!Q.empty())
{
int u = Q.front();
vis[st]=1;
printf("%d visited!\n", u);
Q.pop();
for(int i = 0; i<a[u].size(); ++i)
{
int v = a[u][i].v, c = a[u][i].c;
if(vis[v])continue;
Q.push(v);vis[v] = 1;
}
}
}
板子
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
//邻接表无向图的赋权与遍历
using namespace std;
struct node
{
int v,c;
};
vector<node> a[10];
void add(int u,int v,int c)
{
node temp;
temp.v=v;
temp.c=c;
a[u].push_back(temp);
}
void solve()
{
int n=10;
for(int i=1;i<=5;i++)
{
int u,v,c;
cin>>u>>v>>c;
add(u,v,c);
add(v,u,c);
}
for(int i=1;i<=n;i++)
{
for(auto[v,c]:a[i]) //利用auto从结构体中取出v和c
{
cout<<i<<"->"<<v<<" "<<c<<endl;
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}
链式前向星
可以理解为链表实现的邻接表。
1 | int n,m,u,v,c,cnt,head[N]; |
DFS遍历
1 | //链式前向星 |
BFS遍历
1 | //链式前向星 |
Thanks to SZUACM