2020-2021:teams:namespace:广度优先搜索_bfs_与标数最短路

Dijkstra的三步走

前提条件

Dijkstra算法（又称标号法），运行结果是从权重为 0 的起始点开始，为所有顶点标号——标权重。

要求权重全部为正。（为负的话请另寻他法）

头文件只有stdio.h（输入输出）、string.h（memset初始化）……

以及 queue 和C++里万能的语句 using namespace std;

需要两个数组。两个数组的大小都是顶点数。

数据类型小一点的数组vis，用于记录顶点是否已经编号了。

数据类型大一点的数组dis，用于记录顶点权重（即运行结果）。

您还需要一个特殊的优先队列：priority_queue<pair<int,int> > q;

介绍一下工具：priority_queue，又称大顶堆。每次默认弹出最大元素。

和通常的队列语法类似。pop是弹出，push是压入。

top是堆顶元素。empty是判断是否为空。

其中，pair 是特殊的结构体，两元素 first 和 second 。

比较时默认先比较 first 大小，first 相同时比较 second 大小。这是在强调序关系的 priority_queue 中可以调用的原理基础。

make_pair 函数，将输入两个元素按顺序结合，成为输出的 pair 类型结构体。

第一步：初始化

利用 memset 函数，将 dis 数组全写成 0x3f （正最大值，代指距离无穷大），将 vis 数组全写为 0 （未访问过）。

将起始点（标号为 0 的点，可以不止一个）全部压入堆，同时将对应 dis 数组（之前置为最大值了）置为 0 。

语句为：

click here if you want to know more

    q.push(make_pair(0,begin));
    dis[begin]=0;

根据堆特征， push 和 make_pair 连用。因为要对权重（距离）排序，所以权重是第一元素。这里的 0 ，代表距离为 0 。

第二步：找下一个标号点

click here if you want to know more

    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x])
        {
            continue;
        }
        vis[x]=1;

这段的意思：只要堆 q 非空——（空的话就表示图里全标完了，结束就完事了）

令 x 是要找的下一标号点（的编号，那么x是第二元素）。那么 x 一定在堆顶。

于是top 、second 、pop组合拳连用。

但是堆顶未必是想要的元素，没准 x 已经被访问过了。因此，检查 vis 数组。如果已经访问，就直接 continue 掉这一循环，从下一循环重新找，本循环仅仅 pop 了一个元素而已。

然后，置 vis 数组为 1 ，表示已经访问过。

第三步：标号

令 i 跑遍上文节点 x 的所有邻居。（ for 循环，跑遍即可，i未必是节点编号）

这里依赖于图的建构。如果用矩阵写，就跑遍矩阵的一行。如果用邻接表写，就跑遍邻接表的一行。

注意，对于无向图，建构时要将两个方向全部写入（序号、权重）。

对于每一个邻居节点，无论标过与否，都跑一遍。这里 y 是节点编号， time 是对应权重，然后有：

click here if you want to know more

            if(dis[y]>dis[x]+time)
            {
                dis[y]=dis[x]+time;
                q.push(make_pair(-dis[y],y));
            }

只有新权重（节点+权重）比老权重小的时候，才编号，其余时候并不编号。编号完了，就把这个刚编的节点压入堆。

注意！这里的堆，默认是大顶堆，而每次取的时候（见第二步），要取最小的元素。

因此每次压入的时候，将每个权重（第一元素）取负，变相将大顶堆改造成小顶堆。这个操作很巧妙。

总共只有这三个步骤。后面没有了。

完整代码

click here if you want to know more

void Dijkstra(int begin)
{
    //步骤一
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(make_pair(0,begin));
    dis[begin]=0;
    //步骤二
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x])
        {
            continue;
        }
        vis[x]=1;
        //步骤三
        int i;
        for(i=0;i<top[x];i++)
        {
            int y=V[x][i].first;
            int time=V[x][i].second;
            if(dis[y]>dis[x]+time)
            {
                dis[y]=dis[x]+time;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
}

利用队列的BFS非递归实现

click here if you want to know more

void bfs(int v)//以v开始做广度优先搜索（非递归实现，借助队列）
{
    //步骤一
    list<int>::iterator it;
    visited[v] = true;
    cout << v << " ";
    queue<int> myque;
    myque.push(v);
    //步骤二
    while (!myque.empty())
    {
        v = myque.front();
        myque.pop();
        //步骤三
        for (it = graph[v].begin(); it != graph[v].end(); it++)
        {
            if (!visited[*it])
            {
                cout << *it << " ";
                myque.push(*it);
                visited[*it] = true;//访问过
            }
        }
    }
    cout << endl;
}

例题

给出了一个具有n个顶点和m条边的加权连通无向图。你知道有人在顶点1点燃了火，它会立即将当前位置烧成灰尘，并以每秒1英里的速度扩展到相邻的地方。火将在顶点处分裂到所有未点亮的边上，并在至少两个火在同一点相遇时引发爆炸。革命者喜欢爆炸。他们想让你数一数图表上发生的爆炸次数。

第一行包含整数n，m（1≤n≤3×105，0≤m≤106）-顶点数。

接下来的m行中的每一行包含3个整数ui，vi，wi（1≤ui，vi≤n，1≤wi≤9）-第i条边的端点和第i条边的权重。

保证图是连通的。

图可以包含自循环和多条边。示例1显示了处理它们的方法。

输入文件的大小可能很大。请不要读得太慢。

输出将在图形上以单行方式发生的爆炸数。

样例

输入

2 3

1 1 1

1 2 1

输出

输入

4 5

1 2 1

1 3 1

2 3 1

2 4 1

3 4 1

输出

题解

在点上爆炸意味着存在至少两个点可以是他最短路上的前驱；在边上爆炸意味着这条边不在最短路里。因此求出最短路即可。

边权≤ 9 并不意味着可以使用SPFA。本题的本意是使用O(nw) 的桶排序Dijkstra, 但是由于vector实现的桶排Dijkstra 和邻接表+ priority_queue 实现的O(mlogm) Dijkstra 速度在使用输入随机数生成器的方法开大数据后没法拉开差距，因此为了避免卡常数都放了过去。

总之大概的意思是，这东西恰好是最短图标记图后直接算出来。

click here if you want to know more

#include<stdio.h>
#include<string.h>
#include<queue>
 
using namespace std;
 
struct node
{
	int to,next,val;
};
 
struct node e[10000050];
 
int head[1000005],cnt,n,m,K;
 
void add(int first,int second,int z)
{
	e[cnt]=(struct node){second,head[first],z};
	head[first]=cnt++;
}
 
priority_queue<pair<int,int> > q;
 
int dis[1000005],vis[1000005],ans,used[1000005];
 
void Dijkstra()
{
	q.push(make_pair(0,1));
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	while(!q.empty())
	{
		int first = q.top().second;
		q.pop();
		if(vis[first])
		{
			continue;
		}
		vis[first] = 1;
		int i;
		for(i=head[first];i!=-1;i=e[i].next)
		{
			int to1 = e[i].to;
			if(dis[to1]>dis[first]+e[i].val)
			{
				dis[to1]=dis[first]+e[i].val;
				used[to1]=1;
				q.push(make_pair(-dis[to1],to1));
			}
			else if(dis[to1]==dis[first]+e[i].val)
			{
				used[to1]++;
			}
		}
	}
}
 
int main()
{
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	int i,x,y,z; 
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	Dijkstra();
	for(i=1;i<=n;i++)
	{
		if(used[i]>=2)
		{
			used[i]--;
		}
		m-=used[i];
	}
	printf("%d\n",m);
}

目录

Dijkstra的三步走

前提条件

第一步：初始化

第二步：找下一个标号点

第三步：标号

完整代码

利用队列的BFS非递归实现

例题

样例

题解