有向无环图——AOV网及拓扑排序

有向无环图——AOV网及拓扑排序

有向无环图

无环的有向图叫有向无环图，简称DAG图

其应用大致如下：

• 在工程计划和管理方面有着广泛而重要的应用
• 描述一项工程或系统的进行进程的有效工具
• 对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。

这篇文章单独讨论AOV网及其拓扑排序

AOV网及拓扑排序

概念

AOV网：用顶点表示活动，用弧表示活动间优先关系的有向无环图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网。

拓扑排序：把AOV网中各顶点按照它们相互之间的优先关系排列成一个线性序列（拓扑序列）的过程。若网中所有顶点都在它的拓扑有序序列中，则该拓扑序列就是一个工程顺利完成的可行方案；否则，该工程无法顺利完成。

拓扑排序方法：

• 从图中选择一个入度为0的顶点输出
• 从图中删除该顶点及源自该顶点的所有弧
• 重复以上两步，直至全部顶点都输出，拓扑排序顺利完成。否则，若剩有入度非0的顶点，说明图中有环，拓扑排序不能进行

拓扑排序代码

AOV网类定义

class aov {
public:
	aov() {}
private:
	class node {
	public:
		set<int> prev;	//前驱结点
		set<int> next;	//后继结点

		//备份
		set<int> back_prev;
		set<int> back_next;

	};

	unordered_map<int, node*> adjList;	//邻接表

public:
	void Insert(int index, initializer_list<int> lst);
	bool DeleteArc(int a, int b);
	void Sort();

private:
	void _Sort(unordered_map<int, node*> adjList);
};
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

插入操作

//插入
void aov::Insert(int index, initializer_list<int> lst) {
	//若当前结点不存在则创建
	node* n = this->adjList[index] ? this->adjList[index] : new node;

	for (auto it = lst.begin(); it != lst.end(); it++)
	{
		//将该节点后继插入到后继索引集合中去
		n->next.insert(*it);
		n->back_next.insert(*it);
		node* p = nullptr;
		
		//若后继结点不存在，则创建
		if (this->adjList[*it] == nullptr)
		{
			p = new node;
			this->adjList[*it] = p;
		}
		else {
			p = this->adjList[*it];
		}
		
		//向相连结点记入前驱
		p->prev.insert(index);
		p->back_prev.insert(index);
	}

	this->adjList[index] = n;	//保存至邻接表
}
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

删除关系

//删除a指向b之间的关系（注意，这里有方向规定）
bool aov::DeleteArc(int a, int b)
{
	//如果不存在a结点或b结点则返回false
	if (this->adjList[a] == nullptr || this->adjList[b] == nullptr)
		return false;

	node* p_a = this->adjList[a];
	node* p_b = this->adjList[b];

	auto p_a_find = p_a->next.find(b);
	auto p_b_find = p_b->prev.find(a);

	if (p_a_find != p_a->next.end())
		p_a->next.erase(p_a_find);

	if (p_b_find != p_b->prev.end())
		p_b->prev.erase(p_b_find);

	p_a_find = p_a->back_next.find(b);
	p_b_find = p_b->back_prev.find(a);

	if (p_a_find != p_a->back_next.end())
		p_a->back_next.erase(p_a_find);

	if (p_b_find != p_b->back_prev.end())
		p_b->back_prev.erase(p_b_find);


	return true;
}

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

拓扑排序

//拓扑排序
void aov::_Sort(unordered_map<int, node*> adjList)
{
	stack<int> st;

	if (adjList.size() == 0)
	{
		cout << endl;
		return;
	}

	for (auto it = adjList.begin(); it != adjList.end(); it++)
	{
		if (it->second->prev.size() == 0)
			st.push(it->first);
	}
	
	while (!st.empty())
	{
		int t = st.top();
		cout << t << " ";
		st.pop();

		//对t指向的每一个结点删除弧，及这些结点入度都减1
		for (auto it = adjList[t]->next.begin(); it != adjList[t]->next.end(); it++)
		{
			if (adjList[*it])
			{
				auto index = adjList[*it]->prev.find(t);
				if (index != adjList[*it]->prev.end())
					adjList[*it]->prev.erase(index);
			}
		}

		adjList.erase(t);
	}

	_Sort(adjList);

}

void aov::Sort()
{
	_Sort(this->adjList);
	//排序会破坏结点之间的关系，利用备份重新回复原有关系
	for (auto it = this->adjList.begin(); it != this->adjList.end(); it++)
	{
		it->second->next = it->second->back_next;
		it->second->prev = it->second->back_prev;
	}

}

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
47
48
49
50
51
52
53

测试

int main()
{
	aov* v = new aov;
	
	v->Insert(1, { 2,3,4 });
	v->Insert(3, { 2,5 });
	v->Insert(4, { 5 });
	v->Insert(6, { 4,5 });

	v->Sort();
	v->Sort();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

代码缺点

对于拓扑排序，我这种写法一开始没考虑好，使用指针进行拓扑排序会破坏结点之间的连接，因此使用了备份集合来回复，但这种操作会多占用一部分资源。