拓扑排序,分别用C语言，C++,java,python编写出来

拓扑排序是一种把有向无环图转换成线性序列的排序算法，算法的输入是一个有向无环图，经过算法分析吧图中的所有节点按照先后顺序进行拆解，最后得到一个有顺序的队列，在前的节点靠前，越靠后的节点或有多个节点指向该节点，那这个节点再队列中的位置就越靠后。

拓扑排序,分别用C语言，C++,java,python编写出来
下面是拓扑排序（Topological Sort）的不同语言实现示例：
1. C语言：

#include <stdio.h>
#define MAX_SIZE 100
void topologicalSort(int graph[][MAX_SIZE], int n) {
int indegree[MAX_SIZE] = {0};
int queue[MAX_SIZE];
int front = 0, rear = 0;
// 计算每个顶点的入度
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
indegree[i] += graph[j][i];
}
}
// 将入度为0的顶点入队列
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue[rear++] = i;
}
}
// 拓扑排序
while (front < rear) {
int vertex = queue[front++];
printf(“%d “, vertex);
for (int i = 0; i < n; i++) {
if (graph[vertex][i] == 1) {
indegree[i]–;
if (indegree[i] == 0) {
queue[rear++] = i;
}
}
}
}
}

2. C++:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void topologicalSort(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> indegree(n, 0);
queue<int> q;
// 计算每个顶点的入度
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
indegree[i] += graph[j][i];
}
}
// 将入度为0的顶点入队列
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
// 拓扑排序
while (!q.empty()) {
int vertex = q.front();
q.pop();
cout << vertex << ” “;
for (int i = 0; i < n; i++) {
if (graph[vertex][i] == 1) {
indegree[i]–;
if (indegree[i] == 0) {
q.push(i);
}
}
}
}
}

3. Java:

import java.util.*;
public class TopologicalSort {
public static void topologicalSort(int[][] graph) {
int n = graph.length;
int[] indegree = new int[n];
Queue<Integer> queue = new LinkedList<>();
// 计算每个顶点的入度
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
indegree[i] += graph[j][i];
}
}
// 将入度为0的顶点入队列
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.add(i);
}
}
// 拓扑排序
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + ” “);
for (int i = 0; i < n; i++) {
if (graph[vertex][i] == 1) {
indegree[i]–;
if (indegree[i] == 0) {
queue.add(i);
}
}
}
}
}

}

4. Python:

from collections import deque
def topological_sort(graph):
n = len(graph)
indegree = [0] * n
queue = deque()
# 计算每个顶点的入度
for i in range(n):
for j in range(n):
indegree[i] += graph[j][i]
# 将入度为0的顶点入队列
for i in range(n):
if indegree[i] == 0:
queue.append(i)
# 拓扑排序
while queue:
vertex = queue.popleft()
print(vertex, end=” “)
for i in range(n):
if graph[vertex][i] == 1:
indegree[i] -= 1
if indegree[i] == 0:
queue.append(i)
# 主函数
# 下面隐藏代码为主函数
# 调用主函数
if __name__ == “__main__”:
main()

这些示例展示了使用不同编程语言实现拓扑排序算法的方式。请根据您选择的编程语言，使用相应的示例来实现拓扑排序算法。

扫码关注微信公众号，免费查看完整算法内容。