图论

二叉树

例题

1、已知中、后序遍历求先序

代码逻辑
  • 后序遍历的最后一个字符一定是当下二叉树的根结点，先序遍历中根节点首先被遍历，所以每找到一个根节点就输出。在中序遍历中，根结点前面的是左子树，后面的是右子树，根据后序遍历的最后一个字符可以确定根，从而根据中序遍历确定左子树，从而根据左子树的大小从后序遍历中取出左子树，然后递归求解子树，右子树同理用递归求解
核心代码
1
2
3
4
5
6
7
8
9
void forw(string s1, string s2)
{
	if(!s1.size()) return ;
	char root = s2[s2.size()-1];
	int p = s1.find(root);
	std::cout<<root;
	forw(s1.substr(0,p),s2.substr(0,p));
	forw(s1.substr(p+1,std::string::npos),s2.substr(p,s2.size()-p-1));
}

2、已知先、后序遍历，求中序

代码逻辑
  • 考虑一棵树只有一个根结点和一个结点，那么它子结点为左和子结点为右结点时，得出的先、后序遍历不变
  • 如果树有一棵子树满足上述条件，那么子树有 2 种中序遍历，整棵树也就有 2 种中序遍历，根据乘法原理，如果树上有 k 个结点只有一个子结点，那么整棵树有 2^k^种中序遍历
  • 如果一个结点只有一个子结点，那么先序遍历时，子结点一定在它的后一位，后序遍历时，子结点一定在它的前一位
核心代码
1
2
3
4
5
6
7
8
9
10
pow = 0
for(int i=0;i<=s1.length()-2;i++)
   {
       for(int j=1;j<=s2.length()-1;j++)
       {
           if( s1[i]==s2[j] && s1[i+1]==s2[j-1] )
               pow++;
       }
   }
ans = (1<<pow)

树的直径

概述

边具有权重，如果以权重代表距离，那么整棵树距离最远的两个结点的距离就是树的直径

代码逻辑

  • 以任意结点（比如 1 结点）为起点，dfs 求出各结点到 1 结点的距离，找到距离 1 结点最远的 far 结点
  • 以 far 结点为起点，dfs 求结点到 far 结点的距离，找到最大距离，最大距离就是树的直径

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs( int cur, int fath)
{
	if(dist[cur] > D)
	{
		D = dist[cur];
		far = cur;
	}
	for( int ver : edge[cur])
	{
		if(ver==fat)
			continue;
		dist[ver] = dist[cur] + 1;
		dfs(ver,cur);
	}
}

例题

1、城市规划

问题描述

n 个城市有 n-1 条边，边权都视作 1，以 k 个城市组成核心城市，核心城市之间可以不经过普通城市相互联通，求其他城市到核心城市的最大距离的最小值

代码逻辑
  • 先求直径，dfs 找到以任意结点为起点，离它最远的结点 far，然后用 dfs 求离 far 最远的结点，第二份 dfs 相比前一份 dfs 多一行代码，每次递归求子结点 dfs 之前先令 fa[ver] = cur，留下回溯数组方便找直径中点
  • 直径中点作为核心城市的核心，其他所有结点都具有两个距离值，一个是自己到核心的距离，一个是自己联通的子结点距离核心最远的距离。为了让普通城市离核心城市群尽可能近，必须把自己到核心距离与子结点到核心最远距离的差值前 k-1 大的归为核心城市
核心代码_求直径留回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs( int cur, int fat)
{
	if(dist[cur] > D)
	{
		D = dist[cur];
		far = cur;
	}
	for (int ver : edge[cur])
	{
		if(ver==fat)
			continue;
		dist[ver] = dist[cur] + 1;
		fa[ver] = cur;
		dfs(ver,cur);
	}
}
核心代码_回溯找直径中点
1
2
3
center = far;
for(int i=1;i<=( D + 1 )/2;i++)
	center = fa[center];
核心代码_核心距离、最深距离
1
2
3
4
5
6
7
8
9
10
11
12
void dfs( int cur, int fat)
{
	dist_max[cur] = dist[cur];
	for( int ver : edge[cur])
	{
		if(ver==fat)
			continue;
		dist[ver] = dist[cur] + 1;
		dfs(ver,cur);
		dist_max[cur] = dist_max[ver] > dist_max[cur] ? dist_max[ver] : dist_max[cur];
	}
}

最小生成树

Kruskal

例题

N 个结点的图有 M 条无向有权边，判断能否生成一棵树，如果能则求出最小权重和

代码逻辑

  • 将边从小到大遍历，如果边的两个结点不在同一个并查集中，就合并它们，合并的权重代价就是这条边的权重

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Kruskal()
{
 	for(int i=1;i<=m;i++)
    {
       	int root1 = FindRoot(edge[i].u), root2 = FindRoot(edge[i].v);
        if(root1==root2)
            continue;
		root[root1] = root[root2];
        ans += edge[i].w;
        cnt++;
        if(cnt==n-1)  //合并n-1次并查集可以得到n个结点的树
            return ans;
    }
    return -1;
}

Prime

代码逻辑

  • 起始让 1 结点入树，每当有结点入树就更新和它相连且未入树的结点到树的距离，每次找距离树最近的结点收入树中，无法用边联通的结点的距离视作 inf
  • visited 判断结点是否已经入树

核心代码

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
bool prime()
{
	for(int i=2;i<=n;i++)
		dist[i] = inf;
	for(edge ver : e[1])
		dist[ver.to] = dist[ver.to] < ver.weight ? dist[ver.to] : ver.weight;
	int now = 1, tot = 0;
    while(++tot<n)
    {
        int min = inf;
        visited[now] = true;

        for(int i=1;i<=n;i++)
        {
            if(!visited[i] && min>dist[i])
            {
                min = dist[i];
				now = i;
            }
        }
   	//树中结点还没到n个，但已经找不到可以连接的结点了
        if(min==inf)
            return false;
        ans+=min;

        for(edge ver : e[now])
        {
        	if(!visited[ver.to] && dist[ver.to]>ver.weight)
        		dist[ver.to] = ver.weight;
		}
    }
    return true;
}

树上结点最近祖先（LCA）

例题

问题描述

n 个结点的树，s 为根，查询任意两个结点的最近祖先

代码逻辑

  • 先将两结点提到同一深度，然后一起向上回溯，回溯数组存 2 的幂次祖先，fanow,i表示从 now 向前回溯 2^i^得到的祖先
  • 无论是提到同一高度还是一起回溯，都按照 2 的幂次为单位向前跳，可以降低时间开销
  • 一起回溯时，从大到小遍历所有 2 的幂次级别的祖先结点，若不相同就跳。如果最近公共祖先是 x 结点，再向上看，两个结点上面的全部祖先结点肯定都相同

核心代码_预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int now, int fath)
{
    //求深度
	depth[now] = depth[fath] + 1;
	//求回溯数组
    fa[now][0] = fath;
	for(int i=1;i<= (int)( log(depth[now])/log(2) );i++)
		fa[now][i] = fa[fa[now][i-1]][i-1];

	for(int ver : edge[now])
	{
		if(ver!=fath)
			dfs(ver,now);
	}
	return ;
}

核心代码_LCA 主程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int LCA(int a, int b)
{
	if(depth[a]<depth[b])
		Swap(a,b);

	while(depth[a]>depth[b])
		a = fa[a][log_2[depth[a]-depth[b]]-1];
	if(a==b)
		return a;

	for(int i=log_2[depth[a]]-1;i>=0;i--)
	{
		if(fa[a][i]!=fa[b][i])
			a = fa[a][i], b = fa[b][i];
	}
	return fa[a][0];
}

单源最短路径（Dijkstra）

概述

  • Dijkstra只能处理无负权图的单源最短路径问题

例题

1、有向有权图单源最短距离

问题描述

n 个结点 m 条边，以 s 为源点，求其它所有结点到它的最短距离

代码逻辑
  • 辅助数据结构：优先队列 元素属性：队列中元素具有标号和距源点距离两个属性 排序方式：距离源点小的排前
  • 先让源点入队，每次循环从队列中弹出元素，更新它子结点到源点的距离，将被修改的子结点入队
  • 代码是广度优先搜索的逻辑，所以可能会出现同一个结点被修改多次，所以它会多次入队，由于是优先队列，只有第一次出队表示的才是它离源点的最短距离，所以用 visited 数组记录结点是否出过队
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Dijkstra()
   {
       q.push( (node) {s,0} );
       while(!q.empty())
       {
           int ind = q.top().ind;
           q.pop();
           if(visited[ind])
               continue;
           for( edge ver : e[ind] )
           {
    			if( dist[ver.to] > dist[ind] + ver.w ) //满足if条件的必然没有出过队
               {
                   dist[ver.to] = dist[ind] + ver.w;
                   q.push( (node) { ver.to,dist[ver.to] } );
               }
           }
       }
   }

2、无向无权图单源最短路

问题描述

n 个结点 m 条边的无向无权图（边权都视作 1）以 1 为源点，求抵达任意点的最短路径的条数

代码逻辑
  • 先初始化 dist1为 0，其它 dist 都为 inf，ans1为 1，其它 ans 为 0
  • 利用优先队列，使到源点距离小的排前，但优先队列默认小的排后，所以传值时，传入距离的相反数
  • 处理当下结点的子结点时，如果子结点 dist 大于当下结点 dist 再+1，那么说明从当下结点去到子结点才是去它的最短路径，赋值式更新子结的 ans，但如果子结点的 dist 原本就和当下结点的 dist 再+1 相等，由于每个结点只会 visit 一次，所以子结点的 dist 被另外一个父结点更新为了当下结点的 dist 再+1，由排列组合加法原理知子结点的 ans 应当加上当下结点的 ans
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Dijkstra()
{
	std::priority_queue< std::pair<int,int> > q;
	q.push( std::make_pair(0,1) );
	while(q.size())
	{
		int pos = q.top().second;
		q.pop();
		if(visited[pos])
			continue;
		visited[pos] = true;
		for(int ver : edge[pos])
		{
			if(dist[ver] > dist[pos] + 1)
			{
				dist[ver] = dist[pos] + 1;
				ans[ver] = ans[pos];
				q.push( std::make_pair(-dist[ver],ver) );
			}
			else if(dist[ver] == dist[pos] + 1)
				ans[ver] = ( ans[ver] + ans[pos] ) % mod;
		}
	}
}

图上最小环

例题

1、生日

题目描述

现在有 n 个人，起始时每个人只知道自己的生日，每个人都有一个信息传递对象，这个传递对象可以是自己，每一轮都会把自己知道的所有生日告诉传递对象，最少多少轮的时候会有人从别人口中听到自己的生日？

代码逻辑
  • 这是一个找最小环的问题，因为每个人只有一个信息传递对象，所以环都是独立的
  • 初始化每个人的传递对象为自己，每输入一个传递对象就判断能否构成环，可以的话就更新答案，不行的话说明更新传递对象
  • FindEnd 找到直线传递路径的终点，如果成环了，那么成环的结点的 nxt 不会被更新，所以它会导致 FindEnd 返回，也就是说，成环的结点就是直线传递路径的终点
核心代码_寻找直线传递路径终点
1
2
3
4
5
6
7
int FindEnd(int x)
   {
       cnt++;  //全局变量
       if(x==nxt[x])
           return x;
      	return FindEnd(nxt[x]);
   }
核心代码_寻找最小环
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<=n;i++)
       nxt[i] = i;
ans = inf;
for(int i=1;i<=n;i++)
   {
       int x;
       cin>>x;
       cnt = 0; //全局变量
       if(FindEnd(x)==i)
           ans = min(ans,cnt);
      	else
           nxt[i] = x;
   }

拓扑结构

概述

拓扑结构关注结点之间的依赖关系

例题

1、工序时间

问题描述

有 n 项事件待做，输入 n 行，表示事件的标号和花费时间和需要的准备工作的标号，工人无限，可以无限制并行完成任务，输出完成所有事件的最小时间

代码逻辑
  • 利用入度数组 in 存下事件的前驱结点个数，如果入度为 0 了，就说明这件事情可以开始做了
  • ans 数组存完成各事件的最小时间，最终的答案为数组的最大值
  • 入度为 0 的事件入队列，每次把出队列的对象的子结点的入度减 1，且更新它的 ans，同一个事件有多个前驱结点，ans 会被更新多次，必须取最大值，如果子结点的入度被减为 1，那么它入队列
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(int i=1;i<=n;i++)
   {
       if(in[i])
       {
           q.push(i);
           ans[i] = t[i];
       }
   }
while(!q.empty())
   {
       int temp = q.top();
       q.pop();
       for(int ver : edge[temp])
       {
		ans[ver] = max( ans[ver], ans[temp] + t[ver] );
           in[ver]--;
           if(in[ver]==0)
               q.push(ver);
       }
   }

2、火车站分级

问题描述

有 n 个站点（编号 1 到 n）的火车站，每个站点都有一个级别，火车站内走过了 m 躺火车，这些火车都遵循一个原则：如果在某一个站停了车，那么后面凡是级别大于等于这个站的站点都要停车，现在已知 m 躺火车停过的站，求火车站的站点至少有几种级别

代码逻辑
  • 这是一个用拓扑排序分层次的问题
  • 火车停过的站之间没有停下的站的级别必然小于停过的站的级别，用 greateri,j表示 i 号站点级别是否大于 j 号站点，用 out 数组记录出度，outi存的是比 i 号站点级别小的站点的个数
  • 每一层级可能有多个站点，但是答案只关注层级的个数，每次循环消去一个层级，把答案加 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
int cnt,ans=-1;
do
{
	ans++;
	//删除最低层的站点，记下被删的站点
	cnt = 0;
	for(int i=1;i<=n;i++)
	{
		if(out[i]==0 && !deleted[i])
		{
			lowest[++cnt] = i;
			deleted[i] = true;
		}
	}
       //更新比被删除站点要高级的站点的出度
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(greater[j][lowest[i]])
			{
				greater[j][lowest[i]] = false;
				out[j]--;
			}
		}
	}
}while(cnt); //有执行删除操作才把答案加1，第一次进去的加1是多余的，所以ans初始化为-1