【不带权图算法之拓扑排序】-C++

淩亂°似流年 2021-11-01 07:28 226阅读 0赞

拓扑排序算法主要由以下两步循环执行，直到不存在入度为 的顶点为止。

1.  选择一个入度为 的顶点并将它输出；
2.  删除从该顶点连出的所有边。  
    循环结束，若输出的顶点数小于图中的顶点数，则表示该图中存在回路，也就是无法进行拓扑排序；否  
    则输出的顶点序列就是一个拓扑序列。  
    接下来，我们用一个例子来说明这个算法过程。对于如下的图，我们首先统计所有顶点的入度，并找出  
    其中所有入度为零的顶点，发现只有 ，于是我们将 插入队列中。  
    图中圆圈内的数字表示顶点的入度，圆圈下方的数字表示顶点编号，直线表示边，直线一端的箭头表示  
    边的方向。图的下方是一个队列，用来在拓扑排序时储存所有未处理的入度为零的顶点。

**基于邻接表的 C++ 示例代码如下：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMzNjk1NA_size_16_color_FFFFFF_t_70]  
基础代码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMzNjk1NA_size_16_color_FFFFFF_t_70 1]  
现在代码中已经给出了用来存储图的邻接表的声明和相关函数的实现。  
接下来我们需要声明顶点数量 n 和边的数量 m 以及统计每个点入度的数组 indegree 。  
在 main 函数上面写下

int n, m;
    int indegree[MAX_N];

初始化操作以及输入 n和 m的值。  
初始时所有点入度都是 0。  
在 main 函数里面写下

init();
    memset(indegree, 0, sizeof(indegree));
    cin >> n >> m;

接下来输入 m 条边插入邻接表并增加该边终点的入度数量。  
在 main 函数里面继续写下

for (int i = 0; i < m; i++) 
    {
    	int u, v;
    	cin >> u >> v;
    	insert(u, v);
    	indegree[v]++;
    }

接下来实现 topo 函数，实现拓扑排序。拓扑排序的步骤如下：  
1、首先我们找到图中入度为0 的点，将其入队。  
我们在 main 函数前写下

void topo()
    {
    	queue<int> q;
    	for (int i = 1; i <= n; i++)
    	{
    		if (indegree[i] == 0) 
    		{
    			q.push(i);
    		}
    	}
    }

拓扑排序的步骤：  
2、每一次选取队首的点，将其输出并出队，随后删除所有以该点为起点的边，如果删边之后出现入度为的0点，则将这个点入队。  
3、重复第二步直到队列为空。  
我们先完成第2步的选取队首的点，输出并出队。  
在 topo 函数里继续写下

while (!q.empty())
    {
    	int now = q.front();
    	cout << now << endl;
    	q.pop();
    }

拓扑排序的步骤：  
2、每一次选取队首的点，将其输出并出队，随后删除所有以该点为起点的边，如果删边之后出现入度为0的点，则将这个点入队。  
3、重复第二步直到队列为空。  
接下来我们来完成第2 步的删边操作，边可以不用真删，只是改变该边终点的入度就可以了。  
在 topo 函数里的 while 循环中继续写下

for (int i = p[now]; i != -1; i = E[i].next)
    {
    	int v = E[i].v;
    	indegree[v]--;
    }

拓扑排序的步骤：  
2、每一次选取队首的点，将其输出并出队，随后删除所有以该点为起点的边，如果删边之后出现入度为0的点，则将这个点入队。  
3、重复第二步直到队列为空。  
接下来我们来完成第2步的入队操作，如果删边后出现了入度为0的点，我们需要把它加入队列。  
在 topo 函数里的 while 循环中的 for 循环内继续写下

if (indegree[v] == 0)
    {
    	q.push(v);
    }

我们已经完成了 topo 函数，那么就可以在 main 函数里调用 topo 函数进行拓扑排序了。  
在 main 函数里面写下

topo();

终于完成了，点击运行，输入下面的数据看看效果吧。

4 3
    1 2
    3 2
    2 4

聪明的你一定学会了实现拓扑排序了

例题传送门:  
[排队][Link 1]  
[威虎山上的分配][Link 2]  
ov.

转载于:https://www.cnblogs.com/moyujiang/p/11167783.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMzNjk1NA_size_16_color_FFFFFF_t_70]: /images/20211101/9aaea55920774eaf883c136087e3dfec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMzNjk1NA_size_16_color_FFFFFF_t_70 1]: /images/20211101/180ec980d91844a8a846b215e6f21212.png
[Link 1]: https://blog.csdn.net/weixin_44336954/article/details/90730115
[Link 2]: https://blog.csdn.net/weixin_44336954/article/details/90729933