数据结构用队列实现拓扑排序、逆拓扑排序

对于拓扑排序和逆拓扑排序，可以使用队列结构来实现。

首先，让我们来解释一下拓扑排序和逆拓扑排序的概念：

- 拓扑排序：对有向无环图（DAG）的所有顶点进行线性排序，使得对于任何有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 的前面。拓扑排序可以用来解决依赖关系的问题。
- 逆拓扑排序：与拓扑排序相反，对有向无环图（DAG）的所有顶点进行线性排序，使得对于任何有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 的后面。

下面是使用队列实现拓扑排序和逆拓扑排序的步骤：

1. 创建一个队列，并将所有入度为 0 的顶点入队。
2. 循环执行以下步骤，直到队列为空：
- 从队列中取出一个顶点，并将其加入结果列表中。
- 遍历该顶点的所有邻接顶点，并将其入度减 1。
- 如果邻接顶点的入度为 0，则将其入队。
3. 检查结果列表中的顶点个数是否与图中的顶点个数相等。如果不相等，则说明图中存在环，无法进行拓扑排序。
4. 对结果列表进行反转，得到逆拓扑排序的结果。

需要注意的是，为了实现上述步骤，我们还需要维护一个邻接表来表示图的边关系以及一个入度数组来统计每个顶点的入度。

希望以上解答能对你有所帮助！如果你还有其他问题，请继续提问。

相关问题

数据结构用队列实现拓扑排序、逆拓扑排序C语言代码

以下使用队列实现拓扑排序和逆拓扑排序的示例代码（C语言）：

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

#define MAX_VERTICES 100

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

typedef struct Graph {
    int numVertices;
    int* indegree;
    Node** adjLists;
} Graph;

typedef struct Queue {
    int front;
    int rear;
    int size;
    int capacity;
    int* elements;
} Queue;

Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;

    graph->indegree = (int*)malloc(numVertices * sizeof(int));
    for (int i = 0; i < numVertices; i++) {
        graph->indegree[i] = 0;
    }

    graph->adjLists = (Node**)malloc(numVertices * sizeof(Node*));
    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    graph->indegree[dest]++;
}

Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    queue->capacity = capacity;
    queue->elements = (int*)malloc(capacity * sizeof(int));
    
    return queue;
}

int isEmpty(Queue* queue) {
    return queue->size == 0;
}

int isFull(Queue* queue) {
    return queue->size == queue->capacity;
}

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        printf("Queue is full.\n");
        return;
    }
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->elements[queue->rear] = item;
    queue->size++;
}

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int item = queue->elements[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;

    return item;
}

void topologicalSort(Graph* graph) {
    int* result = (int*)malloc(graph->numVertices * sizeof(int));
    int index = 0;

    Queue* queue = createQueue(graph->numVertices);

    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->indegree[i] == 0) {
            enqueue(queue, i);
        }
    }

    while (!isEmpty(queue)) {
        int vertex = dequeue(queue);
        result[index++] = vertex;

        Node* temp = graph->adjLists[vertex];
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            graph->indegree[adjVertex]--;
            if (graph->indegree[adjVertex] == 0) {
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }

    if (index != graph->numVertices) {
        printf("Graph contains a cycle, topological sorting not possible.\n");
        return;
    }

    printf("Topological Sort: ");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result);
}

void reverseTopologicalSort(Graph* graph) {
    int* result = (int*)malloc(graph->numVertices * sizeof(int));
    int index = graph->numVertices - 1;

    Queue* queue = createQueue(graph->numVertices);

    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->indegree[i] == 0) {
            enqueue(queue, i);
        }
    }

    while (!isEmpty(queue)) {
        int vertex = dequeue(queue);
        result[index--] = vertex;

        Node* temp = graph->adjLists[vertex];
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            graph->indegree[adjVertex]--;
            if (graph->indegree[adjVertex] == 0) {
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }

    if (index != -1) {
        printf("Graph contains a cycle, reverse topological sorting not possible.\n");
        return;
    }

    printf("Reverse Topological Sort: ");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result);
}

int main() {
    int numVertices, numEdges;
    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &numVertices, &numEdges);

    Graph* graph = createGraph(numVertices);

    printf("Enter the edges (source vertex and destination vertex):\n");
    for (int i = 0; i < numEdges; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    topologicalSort(graph);
    reverseTopologicalSort(graph);

    return 0;
}

在这段代码中，我们首先定义了 `Node` 结构体表示图的顶点，并使用邻接表的形式存储图的边关系。然后定义了 `Graph` 结构体表示图的基本属性，包括顶点个数、入度数组和邻接表数组。接下来，定义了 `Queue` 结构体表示队列，并实现了相关的队列操作函数。最后，实现了拓扑排序和逆拓扑排序的函数，并在 `main` 函数中进行测试。

希望这段代码对你有帮助！如果还有其他问题，请随时提问。

拓扑排序数据结构c语言实现

拓扑排序是一种常用的图算法，用于解决有向无环图（DAG）中的排序问题。其基本思想是通过不断选择入度为0的顶点来构建排序序列。下面是一个基于邻接表的C语言实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define ERROR -1 // 错误标识

// 邻接表结构体
typedef struct EdgeNode {
    int adjvex; // 邻接点编号
    struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;

typedef struct VertexNode {
    int data; // 顶点数据
    EdgeNode *firstEdge; // 指向第一个邻接点的指针
    int indegree; // 顶点的入度
} VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList adjList; // 邻接表
    int vexNum, edgeNum; // 顶点数和边数
} Graph;

// 初始化图
void initGraph(Graph *G, int vexNum) {
    G->vexNum = vexNum;
    G->edgeNum = 0;
    for (int i = 0; i < vexNum; i++) {
        G->adjList[i].data = i; // 顶点数据
        G->adjList[i].firstEdge = NULL; // 邻接表为空
        G->adjList[i].indegree = 0; // 入度为0
    }
}

// 添加边
void addEdge(Graph *G, int u, int v) {
    EdgeNode *e = (EdgeNode *) malloc(sizeof(EdgeNode));
    e->adjvex = v;
    e->next = G->adjList[u].firstEdge;
    G->adjList[u].firstEdge = e;
    G->adjList[v].indegree++; // 修改入度
    G->edgeNum++; // 边数加1
}

// 拓扑排序
int topSort(Graph *G, int *result) {
    int count = 0; // 计数器
    int front = 0, rear = 0; // 队列的头尾指针
    int queue[MAX_VERTEX_NUM]; // 存储入度为0的顶点
    for (int i = 0; i < G->vexNum; i++) {
        if (G->adjList[i].indegree == 0) {
            queue[rear++] = i; // 入度为0的顶点入队
        }
    }
    while (front != rear) { // 队列非空
        int u = queue[front++]; // 出队一个顶点
        result[count++] = u; // 存储排序结果
        for (EdgeNode *e = G->adjList[u].firstEdge; e != NULL; e = e->next) {
            int v = e->adjvex;
            if (--G->adjList[v].indegree == 0) {
                queue[rear++] = v; // 入度为0的顶点入队
            }
        }
    }
    if (count != G->vexNum) { // 存在环路
        return ERROR;
    }
    return 0;
}

int main() {
    Graph G;
    int vexNum = 6; // 顶点数
    int result[MAX_VERTEX_NUM]; // 存储排序结果
    initGraph(&G, vexNum);
    addEdge(&G, 0, 1);
    addEdge(&G, 0, 2);
    addEdge(&G, 1, 3);
    addEdge(&G, 2, 3);
    addEdge(&G, 2, 4);
    addEdge(&G, 3, 5);
    if (topSort(&G, result) == ERROR) {
        printf("存在环路\n");
    } else {
        printf("拓扑排序结果:\n");
        for (int i = 0; i < vexNum; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
    }
    return 0;
}

以上代码中，`initGraph()`函数用于初始化图，`addEdge()`函数用于添加边，`topSort()`函数用于执行拓扑排序，并将排序结果存储在`result`数组中。在`topSort()`函数中，我们使用队列来存储入度为0的顶点，并依次从队列中取出顶点来构建排序序列。如果排序序列的长度不等于顶点数，则说明存在环路，返回错误标识。否则，将排序序列输出即可。