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

帆帆资源网

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

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

1. #include <stdio.h>
   
2. #define MAX_SIZE 100
   
3. void topologicalSort(int graph[][MAX_SIZE], int n) {
   
4.     int indegree[MAX_SIZE] = {0};
   
5.     int queue[MAX_SIZE];
   
6.     int front = 0, rear = 0;
   
7.      // 计算每个顶点的入度
   
8.     for (int i = 0; i < n; i++) {
   
9.         for (int j = 0; j < n; j++) {
   
10.             indegree[i] += graph[j][i];
    
11.         }
    
12.     }
    
13.      // 将入度为0的顶点入队列
    
14.     for (int i = 0; i < n; i++) {
    
15.         if (indegree[i] == 0) {
    
16.             queue[rear++] = i;
    
17.         }
    
18.     }
    
19.      // 拓扑排序
    
20.     while (front < rear) {
    
21.         int vertex = queue[front++];
    
22.         printf("%d ", vertex);
    
23.          for (int i = 0; i < n; i++) {
    
24.             if (graph[vertex][i] == 1) {
    
25.                 indegree[i]--;
    
26.                 if (indegree[i] == 0) {
    
27.                     queue[rear++] = i;
    
28.                 }
    
29.             }
    
30.         }
    
31.     }
    
32. }
    
33. 
    

复制代码

int main() {
    int n = 6;
    int graph[MAX_SIZE][MAX_SIZE] = {
        {0, 0, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0, 0},
        {1, 1, 0, 0, 0, 0}
    };
     printf("Topological Sort: ");
    topologicalSort(graph, n);
     return 0;
}





2. C++:

1. #include <iostream>
   
2. #include <queue>
   
3. #include <vector>
   
4. using namespace std;
   
5. void topologicalSort(vector<vector<int>>& graph) {
   
6.     int n = graph.size();
   
7.     vector<int> indegree(n, 0);
   
8.     queue<int> q;
   
9.      // 计算每个顶点的入度
   
10.     for (int i = 0; i < n; i++) {
    
11.         for (int j = 0; j < n; j++) {
    
12.             indegree[i] += graph[j][i];
    
13.         }
    
14.     }
    
15.      // 将入度为0的顶点入队列
    
16.     for (int i = 0; i < n; i++) {
    
17.         if (indegree[i] == 0) {
    
18.             q.push(i);
    
19.         }
    
20.     }
    
21.      // 拓扑排序
    
22.     while (!q.empty()) {
    
23.         int vertex = q.front();
    
24.         q.pop();
    
25.         cout << vertex << " ";
    
26.          for (int i = 0; i < n; i++) {
    
27.             if (graph[vertex][i] == 1) {
    
28.                 indegree[i]--;
    
29.                 if (indegree[i] == 0) {
    
30.                     q.push(i);
    
31.                 }
    
32.             }
    
33.         }
    
34.     }
    
35. }
    
36. 
    

复制代码

int main() {
    int n = 6;
    vector<vector<int>> graph = {
        {0, 0, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0, 0},
        {1, 1, 0, 0, 0, 0}
    };
     cout << "Topological Sort: ";
    topologicalSort(graph);
     return 0;
}





3. Java:

1. import java.util.*;
   
2. public class TopologicalSort {
   
3.     public static void topologicalSort(int[][] graph) {
   
4.         int n = graph.length;
   
5.         int[] indegree = new int[n];
   
6.         Queue<Integer> queue = new LinkedList<>();
   
7.          // 计算每个顶点的入度
   
8.         for (int i = 0; i < n; i++) {
   
9.             for (int j = 0; j < n; j++) {
   
10.                 indegree[i] += graph[j][i];
    
11.             }
    
12.         }
    
13.          // 将入度为0的顶点入队列
    
14.         for (int i = 0; i < n; i++) {
    
15.             if (indegree[i] == 0) {
    
16.                 queue.add(i);
    
17.             }
    
18.         }
    
19.          // 拓扑排序
    
20.         while (!queue.isEmpty()) {
    
21.             int vertex = queue.poll();
    
22.             System.out.print(vertex + " ");
    
23.              for (int i = 0; i < n; i++) {
    
24.                 if (graph[vertex][i] == 1) {
    
25.                     indegree[i]--;
    
26.                     if (indegree[i] == 0) {
    
27.                         queue.add(i);
    
28.                     }
    
29.                 }
    
30.             }
    
31.         }
    
32.     }
    
33.    
    
34. }

复制代码

public static void main(String[] args) {
        int n = 6;
        int[][] graph = {
            {0, 0, 0, 0, 0, 0},
            {0, 0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0, 0},
            {0, 0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0, 0},
            {1, 0, 0, 0, 0, 0}
        };
         System.out.print("Topological Sort: ");
        topologicalSort(graph);
    }




4. Python:

1. from collections import deque
   
2. def topological_sort(graph):
   
3.     n = len(graph)
   
4.     indegree = [0] * n
   
5.     queue = deque()
   
6.      # 计算每个顶点的入度
   
7.     for i in range(n):
   
8.         for j in range(n):
   
9.             indegree[i] += graph[j][i]
   
10.      # 将入度为0的顶点入队列
    
11.     for i in range(n):
    
12.         if indegree[i] == 0:
    
13.             queue.append(i)
    
14.      # 拓扑排序
    
15.     while queue:
    
16.         vertex = queue.popleft()
    
17.         print(vertex, end=" ")
    
18.          for i in range(n):
    
19.             if graph[vertex][i] == 1:
    
20.                 indegree[i] -= 1
    
21.                 if indegree[i] == 0:
    
22.                     queue.append(i)
    
23. # 主函数
    
24. # 下面隐藏代码为主函数
    
25. # 调用主函数
    
26. if __name__ == "__main__":
    
27.     main()

复制代码

def main():
    n = 6
    graph = [
        [0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0, 0],
        [1, 1, 0, 0, 0, 0]

     print("Topological Sort: ", end="")
    topological_sort(graph)





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


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