在用邻接表表示图时，拓扑排序算法时间复杂度为( )。

[单选题]

对于用邻接表表示图（包含n个定点e条边）时，拓扑排序算法时间复杂度为（）

```
O(n)
```
```
O(n＋e)
```
```
O(n^2)
```
```
O(n^3)
```

查看正确选项

jfjdjdjs

发表于 2019-11-23 19:29:49 回复(0)

黏黏糖

对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e)；建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减1的操作在while语句中总共执行e次，所以总的时间复杂度为O(n+e)。
拓扑排序初始参数只有邻接表，所以第一步建立入度数组，因为每1入度对应一条弧，总共e条弧，建立入度数组的复杂度为O(e)。每个节点输出一次，n个节点遍历一次，时间复杂度为O(n)。（使用零入度节点栈的原因是，如果不把零入度节点入栈，每次输出时都要遍历节点。建立此栈，只需遍历一次。）然后节点入度减1的操作，也是一条弧对应一次，e条弧总共O(e)。以上总计O(n+2e)即O(n+e)。
即对每条弧要建立入度数组操作和删除操作，每个顶点要遍历一次并删除。故时间复杂度为O(n+e)

编辑于 2017-05-24 10:51:50 回复(0)

空空以空空

我猜的。。。课本上说以邻接表作图的存储结构时，找邻接点所需时间是O(e),e是无向图的边或者有向图的弧的数，深度优先搜索遍历图时间复杂度为O(n+e);

拓扑排序的步骤：1.在有向图中选一个没有前驱的顶点且输出之。2.从图中删除该顶点和所有以它为尾的弧。重复这两步，知道所有顶点都输出，或者！当前图中不存在无前驱的顶点为止。后一种情况，说明有环。

/**
采用邻接表作为存储结构
且在头节点中增加一个存放顶点入度的数组（indegree).
入度为0的顶点就是没有前驱的顶点（有几个前驱就入度就为多少）
删除顶点以及以它为尾的弧的操作，可换为以弧头顶点入度减1来实现
为了避免重复检测入度为0的顶点，另设一栈暂存所有入度为0的顶点
*/
Status TopologocalSort(ALGraph G){
//有向图G采用邻接表存储结构
若G无回路，则输出G的顶点的一个拓扑序列并返回OK。否则ERROR
FindInDegree(G,indegree);//对各顶点求入度indegree[0...vernum-1];
InitStack(S);
for(i=0;i<G.vexnum;++i)//建零入度顶点栈
 if(!indegree[i])Push(S,i);//入度为0者进栈
 count = 0;
while(!StackEmpty(S);{
 Pop(S,i);printf(i,G.vertices[i].data);++count;//输出i号顶点并计数
 for(p=G.vertices[i].firstarc;p;p = p->nextarc){
   k = p->adjvex;//对i号顶点的每个邻接点的入度减1
   if(!(--indegree[k]））Push(S,k);//若入度为0，入栈
}
if(count<G.vexnum) return ERROR;
else return OK;
}

这个算法对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e);

建零入度顶点栈的时间复杂度是O(n);

在拓扑排序过程中，如果有向图无环，则每个顶点进一次栈，出一次栈，入度减1的操作在WHILE语句敏感词执行了e次，所以总的时间复杂度就是O(n+e)；

当有向图无环时，也可以利用深度优先遍历进行拓扑排序，所以时间复杂度也是O(n+e)

编辑于 2017-08-28 11:00:32 回复(0)

simon_free

拓扑排序（Topological Sort）是指将一个有向无环图（Directed Acyclic Graph，简称DAG）进行排序，从而得到一个有序的线性序列。这个序列需要满足以下两个条件：每个顶点出现且只出现一次；若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面。拓扑排序可以用来确定事物发生的顺序，例如制定一个计划，确定A、B、C、D的执行顺序。

拓扑排序算法的时间复杂度取决于图的表示方式和所使用的排序算法。在邻接表表示图的情况下，拓扑排序算法的时间复杂度通常为O(n + e)，其中n是顶点的数量，e是边的数量。

拓扑排序算法的基本思路是遍历所有边，并使用一个栈来保存顶点。算法首先从图中找到一个没有前驱（即入度为0）的顶点，将其压入栈中。然后，从该顶点出发，遍历与之相关的边（即出边），并将这些边的终点的入度减1。如果某个顶点的入度变为0，则将其压入栈中。重复这个过程，直到栈为空或存在环。

在邻接表表示图的情况下，遍历所有边的时间复杂度为O(e)，而每次将顶点压入栈或从栈中弹出的时间复杂度均为O(1)。因此，总的时间复杂度为O(n + e)。

需要注意的是，如果图中存在环，则无法进行拓扑排序。在这种情况下，算法需要检测环的存在并处理，这会增加算法的时间复杂度。

发表于 2023-11-16 12:25:51 回复(0)

笨鸟在思考

–一楼的，方便看提出来了。对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e)；建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减1的操作在while语句中总共执行e次，所以总的时间复杂度为O(n+e)。拓扑排序初始参数只有邻接表，所以第一步建立入度数组，因为每1入度对应一条弧，总共e条弧，建立入度数组的复杂度为O(e)。每个节点输出一次，n个节点遍历一次，时间复杂度为O(n)。（使用零入度节点栈的原因是，如果不把零入度节点入栈，每次输出时都要遍历节点。建立此栈，只需遍历一次。）然后节点入度减1的操作，也是一条弧对应一次，e条弧总共O(e)。以上总计O(n+2e)即O(n+e)。即对每条弧要建立入度数组操作和删除操作，每个顶点要遍历一次并删除。故时间复杂度为O(n+e)

发表于 2019-01-04 00:09:41 回复(0)