有向图的拓扑排序算法

在计算机科学中，有时需要对有向无环图（DAG）进行排序，这种排序被称为拓扑排序。 拓扑排序是一种对有向无环图进行排序的算法，其中每个节点（顶点）表示一个任务，每个边表示一个任务之间的依赖关系，排序结果明确显示了任务之间的依赖性，从而可以确定任务执行顺序。

拓扑排序算法的基本思想是，首先找到入度为0的节点，将其作为排序的起点，然后删除与该节点相邻的边，同时将该节点从图中删除。这样就会产生一个新的入度为0的节点，不断重复以上过程，直到图中没有剩余节点为止，排序完成。

实现算法的前提条件是必须确保当前的DAG是有向无环图。如果存在环路，则无法进行拓扑排序。拓扑排序算法的时间复杂度为O(V+E)，其中V是节点数目，E是边数目。

拓扑排序的方法：

1. 首先遍历整个图，统计每个节点的入度。并将入度为0的节点加入队列。

2. 从队列中弹出入度为0的节点，并删除与该节点相邻的边。此时该节点的相邻节点入度减1，若入度减为0，则将该节点加入队列。

3. 重复步骤2，直到队列为空。

拓扑排序的实现：

使用队列保存入度为0的节点，使用map保存每个节点的入度，使用vector保存每个节点的相邻节点。

bool topological_sort(vector adj[], int indegree[], int n)

{

queue q;

for(int i=0; i

{

if(indegree[i] == 0)

{

q.push(i);

}

}

int cnt = 0;

vector order;

while(!q.empty())

{

int u = q.front();

q.pop();

order.push_back(u);

cnt++;

for(int i=0; i

{

int v = adj[u][i];

if(--indegree[v] == 0)

{

q.push(v);

}

}

}

if(cnt != n) return false; //图中存在环路

for(int i=0; i

{

cout<

}

cout<

return true;

}