图的拓扑排序的非递归c语言实现

图的拓扑排序是一种算法，它将有向无环图（DAG，Directed Acyclic Graph）的所有顶点按照一定的线性顺序排列，使得对于每条有向边 u->v，顶点 u 总是排在顶点 v 的前面。以下是使用非递归方法在C语言中实现拓扑排序的一个基本思路：

#include <stdio.h>
#include <stdlib.h>

// 定义邻接表表示图的数据结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 添加边到图中
void addEdge(Node** adjacencyList, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = adjacencyList[src];
    adjacencyList[src] = newNode;
}

// 检查图是否为有向无环图
int isAcyclic(Node** adjacencyList, int numVertices) {
    // 使用布尔数组记录每个节点是否已访问过
    int visited[numVertices] = {0};
    for (int i = 0; i < numVertices; ++i) {
        if (visited[i] == 0 && !hasCycle(adjacencyList, i, visited)) {
            return 1;
        }
    }
    return 0;
}

// 辅助函数检查是否有环，递归调用
int hasCycle(Node** adjacencyList, int vertex, int* visited) {
    visited[vertex] = 1;
    Node* temp = adjacencyList[vertex];

    while (temp != NULL) {
        if (visited[temp->data] == 1)
            return 1; // 发现环，返回1
        if (!visited[temp->data]) {
            if (hasCycle(adjacencyList, temp->data, visited))
                return 1;
        }
        temp = temp->next;
    }
    visited[vertex] = 0; // 出了循环，清除标记
    return 0;
}

// 执行拓扑排序并打印结果
void topologicalSort(Node** adjacencyList, int numVertices) {
    if (isAcyclic(adjacencyList, numVertices)) {
        int visited[numVertices] = {0};
        for (int i = 0; i < numVertices; ++i) {
            if (!visited[i] && dfs(adjacencyList, i, visited))
                break;
        }
        // 输出排序后的顶点序列
        printf("Topological Sort:\n");
        for (int i = 0; i < numVertices; ++i)
            if (visited[i])
                printf("%d ", i);
        printf("\n");
    } else {
        printf("Graph contains a cycle and cannot be sorted.\n");
    }
}

// 深度优先搜索辅助函数
int dfs(Node** adjacencyList, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    Node* temp = adjacencyList[vertex];
    while (temp != NULL) {
        if (!visited[temp->data]) {
            if (dfs(adjacencyList, temp->data, visited))
                return 1; // 如果发现不可达的节点，则返回1
        }
        temp = temp->next;
    }

    return 0;
}

// 主程序入口
int main() {
    int V, E; // 用户输入顶点数和边数
    printf("Enter number of vertices and edges: ");
    scanf("%d %d", &V, &E);

    Node** adjacencyList = (Node**)malloc(V * sizeof(Node*));
    for (int i = 0; i < V; ++i)
        adjacencyList[i] = NULL;

    // 根据用户输入构建图
    // ...

    // 执行拓扑排序
    topologicalSort(adjacencyList, V);

    // 清理内存
    for (int i = 0; i < V; ++i)
        free(adjacencyList[i]);
    free(adjacencyList);
    return 0;
}

这个示例展示了如何使用邻接表数据结构来实现非递归的拓扑排序。注意，实际应用中你需要处理用户输入，并在主函数中添加构建图的代码。