Python实战社群
Java实战社群
长按识别下方二维码，按需求添加
扫码关注添加客服
进Python社群▲
扫码关注添加客服
进Java社群▲
拓扑排序基础篇
由某个集合上的一个偏序得到该集合上的一个全序的操作过程称为拓扑排序。
拓扑排序思想篇
(1) 在有向图中选一个没有前驱的顶点且输出之。 (2) 从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图不存在无前驱的顶点为止，后一种情况说明有向图中存在环。
有向无环图
有向有环图
拓扑排序实现篇
// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i, k, gettop;
int top = 0; // 用于栈指针下标索引
int count = 0; // 用于统计输出顶点的个数
int *stack; // 用于存储入度为0的顶点
stack = (int *)malloc(GL->numVertexes * sizeof(int));
for( i=0; i < GL->numVertexes; i++ )
{
if( 0 == GL->adjList[i].in )
{
stack[++top] = i; // 将度为0的顶点下标入栈
}
}
while( 0 != top )
{
gettop = stack[top--]; // 出栈
printf("%d -> ", GL->adjList[gettop].data);
count++;
for( e=GL->adjList[gettop].firstedge; e; e=e->next )
{
k = e->adjvex;
// 注意：下边这个if条件是分析整个程序的要点！
// 将k号顶点邻接点的入度-1，因为他的前驱已经消除
// 接着判断-1后入度是否为0，如果为0则也入栈
if( !(--GL->adjList[k].in) )
{
stack[++top] = k;
}
}
}
if( count < GL->numVertexes ) // 如果count小于顶点数，说明存在环
{
return ERROR;
}
else
{
return OK;
}
}
时间复杂度分析
拓扑排序实战篇
题目描述
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。 在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1] 给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例
示例 1： 输入: 2, [[1,0]]输出: true解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。 示例 2： 输入: 2, [[1,0],[0,1]]输出: false解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
List<List<Integer>> adjacency = new ArrayList<>();
LinkedList<Integer> stack = new LinkedList<>();
for(int i = 0; i < numCourses; i++)
adjacency.add(new ArrayList<>());
for(int[] cp : prerequisites) {
indegrees[cp[0]]++;
adjacency.get(cp[1]).add(cp[0]);
}
for(int i = 0; i < numCourses; i++)
if(indegrees[i] == 0) stack.add(i);
while(!stack.isEmpty()) {
int pre = stack.pollLast();
numCourses--;
for(int cur : adjacency.get(pre))
if(--indegrees[cur] == 0) stack.add(cur);
}
return numCourses == 0;
}
}
import java.util.*;
class Graph {
int V;
List<Integer> adjListArray[];
public Graph(int V) {
this.V = V;
@SuppressWarnings("unchecked")
List<Integer> adjListArray[] = new LinkedList[V];
this.adjListArray = adjListArray;
for (int i = 0; i < V; i++) {
adjListArray[i] = new LinkedList<>();
}
}
public void addEdge(int src, int dest) {
this.adjListArray[src].add(dest);
}
private void allTopologicalSortsUtil(boolean[] visited,
int[] indegree, ArrayList<Integer> stack) {
boolean flag = false;
for (int i = 0; i < this.V; i++) {
if (!visited[i] && indegree[i] == 0) {
visited[i] = true;
stack.add(i);
for (int adjacent : this.adjListArray[i]) {
indegree[adjacent]--;
}
allTopologicalSortsUtil(visited, indegree, stack);
visited[i] = false;
stack.remove(stack.size() - 1);
for (int adjacent : this.adjListArray[i]) {
indegree[adjacent]++;
}
flag = true;
}
}
if (!flag) {
stack.forEach(i -> System.out.print(i + " "));
System.out.println();
}
}
public void allTopologicalSorts() {
boolean[] visited = new boolean[this.V];
int[] indegree = new int[this.V];
for (int i = 0; i < this.V; i++) {
for (int var : this.adjListArray[i]) {
indegree[var]++;
}
}
ArrayList<Integer> stack = new ArrayList<>();
allTopologicalSortsUtil(visited, indegree, stack);
}
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(5, 2);
graph.addEdge(5, 0);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
System.out.println("All Topological sorts");
graph.allTopologicalSorts();
}
}
总结
近期精彩内容推荐：
好文分享给更多人↓↓