基础图论

树与图的存储和遍历

树与图的 存储

因为树是无环连通图，所以可以只看图。而图分为无向图和有向图，无向图每条边可以表示为两条有向边，所以可以只看有向图。

1.邻接表

用多个单链表构成的邻接表存储这个点指向的边（即出度），多用于稀疏图(n== m)。

1
2
3
4
5
6
7
8
9
10
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
	e[idx]=b;ne[idx]=h[a],h[a]=idx++;
}
int main()
{
	memset(h,-1,sizeof h);
}

2.邻接矩阵

用一个二维数组存储点边的关系，多用于稠密图(n == m^2)。

g[a] [b]指从a指向b的边，为0即为无边，非0即为有边（值可以存成权值等）

缺点：不能存重边。

树与图的 遍历

DFS

同普通DFS

AcWing 846. 树的重心

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<bits/stdc++.h>
using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;
int ans=N,st[N];
int n;
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int dfs(int u)
{
    st[u]=1;
    int sum=1,res=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            int s=dfs(j);
            res=max(res,s);
            sum+=s;
        }
    }
    res=max(res,n-sum);
    ans=min(ans,res);
    return sum;
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b;cin>>a>>b;
        add(a,b);add(b,a);
    }
    dfs(1);
    cout<<ans;
    return 0;
}

BFS

同普通BFS

AcWing 847. 图中点的层次

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
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;
int d[N];
int n,m;

void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}

int bfs()
{
    queue<int> q;
    q.push(1);
    memset(d,-1,sizeof d);
    d[1]=0;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]!=-1)continue;
            d[j]=d[t]+1;
            q.push(j);
        }
    }
    return d[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b;cin>>a>>b;
        add(a,b);
    }
    cout<<bfs();
    return 0;
}

常用算法

拓扑排序

有向无环图。（bfs）

做法

类比多元bfs

  1. 将所有入度为0的点放入queue。
  2. 遍历queue每个点，将点所有出度对应的点入读-1。
  3. 将入读为0的点再放到queue中。
  4. 最后判断所有的点入度是否都是0。

AcWing 848. 有向图的拓扑序列

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
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx;
int d[N],c[N],num;
int n,m;
queue<int> q;
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void bfs()
{
    
    while(q.size())
    {
        int t=q.front();
        q.pop();
        c[++num]=t;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(!d[j])q.push(j);
            
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)h[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int a,b;cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    for(int i=1;i<=n;i++)if(!d[i])q.push(i);
    bfs();
    if(num!=n)cout<<"-1";
    else 
    {
        for(int i=1;i<=n;i++)cout<<c[i]<<' ';
    }
}

最短路

详见最短路。

总结

image-20230412204030858

Dijkstra（朴素）

思路：
  1. n次循环，每次找到点集外最近的点
  2. 更新所有点最近距离

Dijkstra（堆优化）

思路：
  1. n次循环，每次找到点集外最近的点（小根堆实现）
  2. 更新所有点最近距离

bellman-ford算法

思路：
  1. n次循环，循环所有边。
  2. 循环所有边时更新所有边

spfa算法

思路：
1
2
3
4
5
6
7
8
9
queue <- 初点

while（queue不空）
	t <- q.front();
	q.pop();
	// 更新t的所有出边
	t -w-> b 
	(如果b变小了)queue <- b

Floyd

思路
1
2
3
4
for(k 1~n)
	for(i 1~n)
		for(j 1~n)
			g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

最小生成树

Prim

Kruskal

其它

染色法判定二分图

匈牙利算法