逆拓扑排序判断回路代码

逆拓扑排序可以用来判断有向无环图（DAG）中是否存在回路。如果存在回路，则无法进行拓扑排序。以下是逆拓扑排序判断回路的代码：

bool TopologicalSort(Graph G) {
    InitStack(S); //初始化栈
    for(int i=0;i<G.vexnum;i++) {
        if(Dedegree[i]==0) //度为0的顶点入栈
        {
            push(S,i);
        }
    }
    int count=0; //计数
    while(!IsEmpty(S)) {
        pop(S,i);
        print[count++]=i;
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)//将指向i的顶点的出度减1，并且将出度减为0的顶点压入栈中
        {
            v=p->adjvex;
            if(!(--Dedegree[v])) {
                push(S,v)
            }
        }
    }
    if(count<G.vexnum) //拓扑排序失败，说明有回路
    {
        return false;
    }
    else {
        return true;
    }
}

相关问题

代码实现深度优先的逆拓扑排序判断回路

深度优先搜索（DFS）通常用于寻找有向图中的拓扑序列，也就是无环路径。而判断图是否存在回路则需要用到另一种算法——反向深度优先搜索（Reverse DFS），或称为反向拓扑排序。当我们从最后一个节点开始做DFS，并标记每个访问过的节点，如果发现某个节点已经被标记过，那么就说明存在回路。

以下是简单的Python代码实现这个过程：

def is_cyclic(graph):
    visited = [False] * len(graph)
    stack = []

    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
            elif visited[neighbor]:  # 如果邻居已被访问且未出栈，则存在回路
                return True

        stack.append(node)  # 标记已访问并入栈

    for node in range(len(graph)):
        if not visited[node]:
            if dfs(node):
                return True

    return False  # 没有找到回路，返回False

# 示例：
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
print(is_cyclic(graph))  # 输出：True (存在回路 A->B->E->F)

在这个例子中，`is_cyclic` 函数首先初始化所有节点未访问的状态，然后对每个节点进行反向深度优先搜索。如果在遍历过程中遇到已访问的节点，说明存在回路；否则，节点加入栈中表示已经访问完毕。如果遍历完所有节点都没有发现回路，则返回False。

使用c语言代码实现深度优先的逆拓扑排序判断回路

在C语言中，我们可以使用邻接表来存储图，并利用深度优先搜索（DFS）来实现图的逆向拓扑排序。首先，我们需要一个队列来辅助深度优先遍历，并标记节点是否已经被访问过。下面是基本的步骤：

1. 定义图的结构，例如用邻接数组表示邻接表：

typedef struct Node {
    int data;
    struct Node* next; // 邻接表中的下一个节点指针
} Node;

Node* createGraph(int V); // 创建空图函数

2. 利用DFS实现深度优先搜索并记录入度（每个节点的出边数），同时找出有环的标志：

void dfs(Node* node, int visited[], bool graph[V], int inDegree[]) {
    visited[node->data] = 1;
    for (Node* temp = node->next; temp != NULL; temp = temp->next) {
        if (!visited[temp->data]) {
            dfs(temp, visited, graph, inDegree);
        } else if (visited[temp->data] == 1) { // 发现回路
            inDegree[temp->data] = -1; // 标记有环
        }
    }
    inDegree[node->data]++; // 更新当前节点的入度
}

// 主函数，用于遍历整个图并检查是否有环
int checkCycles(int V, Node** adj) {
    int visited[V] = {0};
    int inDegree[V]; // 初始化所有节点的入度为0

    for (int i = 0; i < V; i++) {
        if (visited[i] == 0 && inDegree[i] == 0) { // 如果未访问且入度为0，开始DFS
            dfs(adj[i], visited, adj, inDegree);
        }
    }

    for (int i = 0; i < V; i++) {
        if (inDegree[i] == -1) return 1; // 找到回路，返回1
    }
    return 0; // 没有找到回路，返回0
}