求aov的所有拓扑序列。C语言

在图论中，AOV（有向无环图）的拓扑排序是指将图中的顶点按照一定的线性顺序排列，使得对于每条有向边 (u, v)，顶点 u 都出现在顶点 v 的前面。由于AOV图中不存在环，所以这样的排序总是存在的。

C语言中求AOF图的拓扑序列可以采用深度优先搜索(DFS)或者广度优先搜索(BFS)。这里以BFS为例，因为BFS通常能保证找到最短路径，并且在AOF图中也能保证找到拓扑序列。

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

bool visited[100]; // 标记节点是否已访问
Node* adj[100];   // 存储邻接表

void addEdge(int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = dest;
    newNode->next = adj[src];
    adj[src] = newNode;
}

void topologicalSort(int n) {
    int i, j;
    for (i = 0; i < n; i++) {
        if (visited[i] == false && adj[i] != NULL) {
            printf("%d ", i); // 添加当前未访问且有出边的节点到序列
            dfs(i);
        }
    }
}

void dfs(int node) {
    visited[node] = true;
    Node* temp = adj[node];

    while (temp != NULL) {
        if (visited[temp->data] == false) {
            dfs(temp->data);
        }
        temp = temp->next;
    }
}

int main() {
    int n, i;
    printf("Enter number of vertices: ");
    scanf("%d", &n);

    // 初始化邻接表
    for (i = 0; i < n; i++) {
        adj[i] = NULL;
        visited[i] = false;
    }

    // 假设输入的边已经添加好了
    // 对于每个边 (u, v)，调用 addEdge(u, v)
    
    topologicalSort(n);
    return 0;
}

在这个C程序中，首先需要输入图的顶点数和边，然后构建邻接表表示图，最后调用topologicalSort函数获取并打印拓扑序列。注意，实际应用中还需要处理用户输入的边和错误检查。