有向无环图——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结点则返回falseif (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::_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指向的每一个结点删除弧，及这些结点入度都减1for (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;}}
测试
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;}
代码缺点
对于拓扑排序，我这种写法一开始没考虑好，使用指针进行拓扑排序会破坏结点之间的连接，因此使用了备份集合来回复，但这种操作会多占用一部分资源。
