对一个包含 N 个顶点的有向图 G(V, E) 用邻接表进行存储，其中顶点以数组保存。对于该有向图类 adjListGraph，要求增加一个成员函数 noLoop，判断该图是否为无环图，是则给出拓扑排序结果（优先从编号小的结点开始），否则返回字符串 “loop” 。(40’). 要求：在文件头部说明新增成员函数的设计思路，并分析时间复杂度分析.(10’) 输入描述 第1行输入顶点个数 N，N 为正整数。 第2行输入有向边信息，边的起点和终点分别为顶点的编号，编号间以逗号相隔，边之间以空格相隔。 输出描述 输出无环检查的结果。无环则给出拓扑排序结果，否则输出字符串 “loop”。 输入举例 6 1,3 2,3 1,4 3,5 2,5 4,2 5,6 3,6 输出举例 1 4 2 3 5 6

设计思路：

该问题可以使用拓扑排序算法来解决。首先，我们需要统计每个顶点的入度，然后从入度为 0 的顶点开始，将其加入拓扑序列中，并将与该顶点相邻的顶点的入度减 1。重复此过程，直到所有顶点都被加入拓扑序列中。如果此时拓扑序列的长度与图中顶点的数量相等，则该图是无环图；否则，该图存在环。

时间复杂度分析：

遍历每个顶点，统计其入度，时间复杂度为 O(|V|+|E|)；

创建一个队列用于存储入度为 0 的顶点，时间复杂度为 O(1)；

从队列中取出入度为 0 的顶点，将其加入拓扑序列中，并将与该顶点相邻的顶点的入度减 1，时间复杂度为 O(|E|)；

重复执行步骤 2 和 3，直到队列为空，时间复杂度为 O(|V|+|E|)；

因此，总时间复杂度为 O(|V|+|E|)。

代码实现如下：

相关问题

假设有向图g采用邻接表存储，设计一个算法求出图g每个顶点的入度

可以遍历邻接表中的每个顶点，并统计每个顶点的入度。具体地，可以定义一个数组in_degree，初始值都为0，然后遍历邻接表，对于每个顶点v的邻接表中的每个顶点u，都将in_degree[u]增加1。最终in_degree数组中的每个元素即为对应顶点的入度。

以下是具体的算法实现：

def get_in_degree(adj_list):
    n = len(adj_list)
    in_degree = [0] * n
    for u in range(n):
        for v in adj_list[u]:
            in_degree[v] += 1
    return in_degree

其中，adj_list是邻接表，n是顶点数。算法的时间复杂度是O(m+n)，其中m是边数。

对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则占用的存储空间为

### 回答1：
邻接表是一种表示图的数据结构，用于表示一个具有n个顶点和e条边的无向图。在邻接表中，每个顶点都有一个对应的链表，该链表包含与该顶点相邻的所有顶点。

对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则占用的存储空间为O(n+e)。具体而言，每个顶点需要占用一个指针和一个链表节点，因此占用的空间为O(n)，而每条边需要在两个顶点的链表中各占用一个节点，因此占用的空间为O(e)。因此，邻接表的总空间复杂度为O(n+e)。

### 回答2：
对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则占用的存储空间为O(n+e)。

邻接表表示无向图的存储方式是通过数组和链表结合的方式。具体来说，我们可以使用一个长度为n的数组，数组的每个元素都是一个链表。数组的下标表示图中的顶点，而链表则存储该顶点相邻的其他顶点。

在邻接表中，每个顶点需要占用一个空间，所以需要n个空间。而每条边需要在两个顶点的链表中都存储一次，因此需要占用2e个空间。

综上所述，对于一个具有n个顶点和e条边的无向图，采用邻接表表示时，占用的存储空间为O(n+e)。

### 回答3：
对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则占用的存储空间为O(n + e)。

邻接表是一种常见的无向图的存储方式。其基本思想是将图中每个顶点都对应一个链表，链表中存储的是与该顶点相邻的顶点。在邻接表中，每个顶点所对应的链表的长度就是其度数。

首先，对于图中的n个顶点，需要n个链表来表示它们的相邻顶点，因此需要占用n个空间。

其次，对于图中的每条边，需要在对应的两个顶点的链表中分别插入一个节点，表示它们之间的边。因此，需要2e个空间。

综上所述，采用邻接表表示一个具有n个顶点和e条边的无向图，需要占用的存储空间为O(n + e)。