2021-1 基于队列的拓扑排序 c++

理论准备

  • 优先级的调度问题,做饭先烧水,切菜先买菜,炒菜先放油,活动之间有先后限制关系。
  • 把必须先准备的事放到前面,需要大量铺垫的活动放到后面,得到一个序列就是拓扑排列。
  • 拓扑排序不唯一
    2021-1 基于队列的拓扑排序 c++

算法

  • 依次拿掉入度(指向自己的箭头个数)为零的节点(起点),并把起点的邻接点的入度减一。
  • 重复以上操作,直到不存在入度为零的点(起点)。
  • 如果最后仍然剩余节点,说明图中必然有环。

准备:图的度数类API

  • Degrees(Digraph G) 构造函数
  • int indegree(int v)v的入度
  • int outdegree(int v)v的出度
  • list<int> sources()所有起点的集合
  • list<int> sinks()所有终点的集合
  • bool isMap()G是一幅映射吗?

定义:入度为零的点是起点,出度为零的点为终点,一个图允许出现自环且每个顶点的出度为1的有向图叫做映射(从0到V-1之间的整数到他们自身的函数)

实现degrees

得到 Digraph.h 点这里

#pragma once
#include<queue>
#include"Digraph.h"
class Degrees
{
public:
	Degrees(Digraph& G);

	int indegree(int v) { return m_indegree->at(v); }
	int outdegree(int v) {
		return m_outdegree->at(v);
	}

	list<int>* sources();
	list<int>* sinks();

	bool isMap();
private:
	vector<int>* m_indegree=nullptr;
	vector<int>* m_outdegree=nullptr;
};


list<int>* TopSortByQueue(Digraph& G);
void testForTopSortByQ();

队列拓扑排序 Degrees.cpp 见注释

#include "Degrees.h"

Degrees::Degrees(Digraph& G)
{
	int n = G.V();
	m_indegree = new vector<int>(n, 0);
	m_outdegree = new vector<int>(n, 0);


	
	for (int i = 0; i < n; ++i) {
		m_outdegree->at(i)=(G.adj(i)->size());
		forIt(G.adj(i)) {
			++m_indegree->at(*it);
		}
	}
}

list<int>* Degrees::sources()
{
	list<int>* ans = new list<int>();
	for (int i = 0; i < m_indegree->size();++i) {
		if (m_indegree->at(i) == 0) {
			ans->push_back(i);
		}
	}
	return ans;
}

list<int>* Degrees::sinks()
{
	list<int>* ans = new list<int>();
	for (int i = 0; i < m_outdegree->size(); ++i) {
		if (m_outdegree->at(i) == 0) {
			ans->push_back(i);
		}
	}
	return ans;
}

bool Degrees::isMap()
{
	bool is_map = true;
	for (int i = 0; i < m_outdegree->size(); ++i) {
		if (m_outdegree->at(i) != 1) {
			is_map = false;
			break;
		}
	}
	return is_map;
}

list<int>* TopSortByQueue(Digraph& G)
{
	list<int>* topSortList = new list<int>();
	
	vector<bool>* marked = new vector<bool>(G.V(), false);
	vector<int>* indegrees = new vector<int>(G.V(), 0);
	queue<int>* inQ = new queue<int>();

	//取出入度放入数组indegrees
	Degrees dg(G);
	for (int i = 0; i < G.V(); ++i) {
		indegrees->at(i) = dg.indegree(i);
	}

	//将起点(入度为零的点)入队
	list<int>* sources = dg.sources();
	forIt(sources) {
		inQ->push(*it);
	}

	//队列不空
	while (!inQ->empty())
	{
	//取出 标记 写到topSortList
		int now = inQ->front(); inQ->pop();
		marked->at(now) = true;
		topSortList->push_back(now);
		//修改邻接点的入度,把新起点入队
		forIt(G.adj(now)) {
			int nxt = *it;
			if (!marked->at(nxt)) {
				indegrees->at(nxt)--;
				if (indegrees->at(nxt) == 0) {
					inQ->push(nxt);
				}
			}
			
		}
	}

	return topSortList;
}

void testForTopSortByQ()
{
	Digraph G("tinyDAG.txt");
	list<int>* topSlist = TopSortByQueue(G);
	forIt(topSlist) {
		out(*it);
	}
	hh;
}
/*
2 8 0 3 7 1 5 6 9 4 11 10 12
*/

测试图

2021-1 基于队列的拓扑排序 c++
依次取出起点,得到拓扑序列:

2 8 0 3 7 1 5 6 9 4 11 10 12

2021-1 基于队列的拓扑排序 c++

拓扑排序的其他思路 点这里

上一篇:想知道自己的磁盘健康状况吗?SMART Utility for mac能够自动检测磁盘的状态和错误情况


下一篇:【数位DP】Amount of Degrees