菜缤的世界 CairBin's Blog - AOV
type: channel
link: https://blog.cairbin.top/index.php/tag/AOV/
items: 有向无环图——AOV网及拓扑排序

有向无环图——AOV网及拓扑排序
type: item
date: 2022-11-08T07:54:28+00:00
description: 有向无环图——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); };插入操作//插入 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; //保存至邻接表 }删除关系//删除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; } 拓扑排序//拓扑排序 void aov::_S…