拓扑排序及算法实现

article/2025/10/1 7:55:18

 

一、拓扑排序概念

  1. 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
  2. 简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

二、理解

  • 在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。
  • 先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度减一。
  • 一直做改操作，直到所有的节点都被分离出来。
  • 如果最后不存在入度为0的节点，但还存在节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。

三、基本实现思路

  1. 先把入度为0 的节点找到并打印
  2. 删掉入度为0的节点，继续循环1的步骤，直至图为null。

四、算法具体思路

第一种方式

是遍历整个图中的顶点，找出入度为0的顶点，然后标记删除该顶点，更新相关顶点的入度，由于图中有V个顶点，每次找出入度为0的顶点后会更新相关顶点的入度，因此下一次又要重新扫描图中所有的顶点。故时间复杂度为O(V^2)

问题：由于删除入度为0的顶点时，只会更新与它邻接的顶点的入度，即只会影响与之邻接的顶点。但是上面的方式却遍历了图中所有的顶点的入度。

第二种方式（更优的算法）

先将入度为0的顶点放在栈或者队列中。当队列不空时，删除一个顶点v，然后更新与顶点v邻接的顶点的入度。只要有一个顶点的入度降为0，则将之入队列。此时，拓扑排序就是顶点出队的顺序。该算法的时间复杂度为O（V+E）

五、拓扑排序方法实现

该算法借助队列来实现时，感觉与 二叉树的 层序遍历算法很相似啊。说明这里面有广度优先的思想。

第一步：遍历图中所有的顶点，将入度为0的顶点 入队列。

第二步：从队列中出一个顶点，打印顶点，更新该顶点的邻接点的入度(减1)，如果邻接点的入度减1之后变成了0，则将该邻接点入队列。

第三步：一直执行上面 第二步，直到队列为空。

public void topoSort() throws Exception{int count = 0;//判断是否所有的顶点都出队了,若有顶点未入队(组成环的顶点)，则这些顶点肯定不会出队Queue<Vertex> queue = new LinkedList<>();// 拓扑排序中用到的栈,也可用队列.//扫描所有的顶点,将入度为0的顶点入队列Collection<Vertex> vertexs = directedGraph.values();for (Vertex vertex : vertexs)if(vertex.inDegree == 0)queue.offer(vertex);//度为0的顶点出队列并且更新它的邻接点的入度while(!queue.isEmpty()){Vertex v = queue.poll();System.out.print(v.vertexLabel + " ");//输出拓扑排序的顺序count++;for (Edge e : v.adjEdges)if(--e.endVertex.inDegree == 0)queue.offer(e.endVertex);}if(count != directedGraph.size())throw new Exception("Graph has circle");}

第7行for循环：先将图中所有入度为0的顶点入队列。

第11行while循环：将入度为0的顶点出队列，并更新与之邻接的顶点的入度，若邻接顶点的入度降为0，则入队列（第16行if语句）。

第19行if语句判断图中是否有环。因为，只有在每个顶点出队时，count++。对于组成环的顶点，是不可能入队列的，因为组成环的顶点的入度不可能为0（第16行if语句不会成立）.

因此，如果有环，count的值 一定小于图中顶点的个数。

完整代码实现

DirectedGraph.java中定义了图 数据结构，（图的实现可参考：数据结构--图 的JAVA实现(上)）。并根据FileUtil.java中得到的字符串构造图。

构造 图之后，topoSort方法实现了拓扑排序。

import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;/** 用来实现拓扑排序的有向无环图*/
public class DirectedGraph {private class Vertex{private String vertexLabel;// 顶点标识private List<Edge> adjEdges;private int inDegree;// 该顶点的入度public Vertex(String verTtexLabel) {this.vertexLabel = verTtexLabel;inDegree = 0;adjEdges = new LinkedList<Edge>();}}private class Edge {private Vertex endVertex;// private double weight;public Edge(Vertex endVertex) {this.endVertex = endVertex;}}private Map<String, Vertex> directedGraph;public DirectedGraph(String graphContent) {directedGraph = new LinkedHashMap<String, DirectedGraph.Vertex>();buildGraph(graphContent);}private void buildGraph(String graphContent) {String[] lines = graphContent.split("\n");Vertex startNode, endNode;String startNodeLabel, endNodeLabel;Edge e;for (int i = 0; i < lines.length; i++) {String[] nodesInfo = lines[i].split(",");startNodeLabel = nodesInfo[1];endNodeLabel = nodesInfo[2];startNode = directedGraph.get(startNodeLabel);if(startNode == null){startNode = new Vertex(startNodeLabel);directedGraph.put(startNodeLabel, startNode);}endNode = directedGraph.get(endNodeLabel);if(endNode == null){endNode = new Vertex(endNodeLabel);directedGraph.put(endNodeLabel, endNode);}e = new Edge(endNode);//每读入一行代表一条边startNode.adjEdges.add(e);//每读入一行数据,起始顶点添加一条边endNode.inDegree++;//每读入一行数据,终止顶点入度加1}}public void topoSort() throws Exception{int count = 0;Queue<Vertex> queue = new LinkedList<>();// 拓扑排序中用到的栈,也可用队列.//扫描所有的顶点,将入度为0的顶点入队列Collection<Vertex> vertexs = directedGraph.values();for (Vertex vertex : vertexs)if(vertex.inDegree == 0)queue.offer(vertex);while(!queue.isEmpty()){Vertex v = queue.poll();System.out.print(v.vertexLabel + " ");count++;for (Edge e : v.adjEdges)if(--e.endVertex.inDegree == 0)queue.offer(e.endVertex);}if(count != directedGraph.size())throw new Exception("Graph has circle");}
}

FileUtil.java负责从文件中读取图的信息。将文件内容转换成 第一点 中描述的字符串格式。--该类来源于网络

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;public final class FileUtil
{/** * 读取文件并按行输出* @param filePath* @param spec 允许解析的最大行数， spec==null时，解析所有行* @return* @author* @since 2016-3-1*/public static String read(final String filePath, final Integer spec){File file = new File(filePath);// 当文件不存在或者不可读时if ((!isFileExists(file)) || (!file.canRead())){System.out.println("file [" + filePath + "] is not exist or cannot read!!!");return null;}BufferedReader br = null;FileReader fb = null;StringBuffer sb = new StringBuffer();try{fb = new FileReader(file);br = new BufferedReader(fb);String str = null;int index = 0;while (((spec == null) || index++ < spec) && (str = br.readLine()) != null){sb.append(str + "\n");
//                System.out.println(str);}}catch (IOException e){e.printStackTrace();}finally{closeQuietly(br);closeQuietly(fb);}return sb.toString();}/** * 写文件* @param filePath 输出文件路径* @param content 要写入的内容* @param append 是否追加* @return* @author s00274007* @since 2016-3-1*/public static int write(final String filePath, final String content, final boolean append){File file = new File(filePath);if (content == null){System.out.println("file [" + filePath + "] invalid!!!");return 0;}// 当文件存在但不可写时if (isFileExists(file) && (!file.canRead())){return 0;}FileWriter fw = null;BufferedWriter bw = null;try{if (!isFileExists(file)){file.createNewFile();}fw = new FileWriter(file, append);bw = new BufferedWriter(fw);bw.write(content);}catch (IOException e){e.printStackTrace();return 0;}finally{closeQuietly(bw);closeQuietly(fw);}return 1;}private static void closeQuietly(Closeable closeable){try{if (closeable != null){closeable.close();}}catch (IOException e){}}private static boolean isFileExists(final File file){if (file.exists() && file.isFile()){return true;}return false;}
}

测试类：TestTopoSort.java

public class TestTopoSort {public static void main(String[] args) {String graphFilePath;if(args.length == 0)graphFilePath = "F:\\xxx";elsegraphFilePath = args[0];String graphContent = FileUtil.read(graphFilePath, null);//从文件中读取图的数据DirectedGraph directedGraph = new DirectedGraph(graphContent);try{directedGraph.topoSort();}catch(Exception e){System.out.println("graph has circle");e.printStackTrace();}}
}

以上内容为参照多个大佬的博客整合后的内容，主要代码部分为 https://www.cnblogs.com/hapjin/p/5432996.html

其余纯手打，有错误请指出，感谢


http://chatgpt.dhexx.cn/article/K1elLjYO.shtml

相关文章

利用迭代法求平方根——迭代法开平方运算

利用迭代法求平方根——迭代法开平方运算

一、题目 用迭代法求&#xff1a; 的值。要求精度为0.00001&#xff0c;即 二、迭代公式 求平方根的迭代公式为&#xff1a; 当满足 时&#xff0c;这时的即是求得的根。如果 得到是精确值。如果不为0&#xff0c;则是近似值。 三、C代码 先给出开平方运算的函数。再给出主…
阅读更多...
【算法】牛顿迭代法求平方根的原理和误差分析

【算法】牛顿迭代法求平方根的原理和误差分析

前言 在《算法(第四版)》中的P23页&#xff0c;给出了经典的利用牛顿迭代法求平方根的算法&#xff0c;牛顿迭代法在数值计算中应用十分广泛&#xff0c;但是在看书中的代码时&#xff0c;我最困惑的是其中对收敛条件的判断&#xff0c;经过查阅资料和论坛&#xff0c;找到…
阅读更多...
使用迭代法来求a的平方根

使用迭代法来求a的平方根

今天朋友问我一道使用迭代法求a的平方根的题&#xff0c;感觉受益匪浅&#xff0c;与诸君相分享 首先我们来看一下题目 我们也无需了解迭代法是什么原理&#xff0c;根据这个题目可以分析得到&#xff0c;需要使用while循环&#xff0c;下面是我的代码实践 #define _CRT_SEC…
阅读更多...
利用牛顿迭代法求平方根

利用牛顿迭代法求平方根

求n的平方根&#xff0c;先假设一猜测值X0 1&#xff0c;然后根据以下公式求出X1&#xff0c;再将X1代入公式右边&#xff0c;继续求出X2…通过有效次迭代后即可求出n的平方根&#xff0c;Xk1 先让我们来验证下这个巧妙的方法准确性&#xff0c;来算下2的平方根 (Computed b…
阅读更多...
牛顿迭代法求解平方根

牛顿迭代法求解平方根

一个实例迭代简介牛顿迭代法 牛顿迭代法简介简单推导泰勒公式推导延伸与应用 一个实例 //java实现的sqrt类和方法 public class sqrt {public static double sqrt(double n){if (n<0) return Double.NaN;double err 1e-15;double t n;while (Math.abs(t - n/t) > err…
阅读更多...
牛顿迭代法求一个数的平方根（python）

牛顿迭代法求一个数的平方根（python）

# !/usr/bin/env python # -*- coding: utf-8 -*- """ Author: P♂boy License: (C) Copyright 2013-2017, Node Supply Chain Manager Corporation Limited. Contact: 17647361832163.com Software: Pycharm File: sqrt.py.py Time: 2018/11/19 16:22 Desc:牛顿…
阅读更多...
c++迭代法求平方根

c++迭代法求平方根

用迭代法求x &#xff0c;要求前后两次求出的x的差的绝对值小于10-5&#xff0c;求平方根的迭代公式为&#xff1a; 输入 一个数a。 输出 的值。 样例输入 2.0样例输出 The square root of 2.00 is 1.41421 这道题我无语了...&#xff1a; #include<bits/stdc.h> …
阅读更多...
牛顿迭代法求平方根原理

牛顿迭代法求平方根原理

牛顿迭代法可以求解n次方的根&#xff0c;但这里只讨论用它来求平方根。 牛顿迭代法求平方根过程 Java代码实现 /*** 求一个数的平方根* param number* return*/public static double squareRoot(double number){if(number < 0){ //小于0的数无法开平方return Double.NaN;}e…
阅读更多...
【算法】牛顿迭代法求平方根及多次方根

【算法】牛顿迭代法求平方根及多次方根

1. 概述 牛顿迭代法 牛顿迭代法 牛顿迭代法 是非常高效的求解方程的根的方法。其求解原理可以参考各文献。大体的思路如下&#xff1a; 通过不断地做切线来逼近真实的根&#xff0c;直到误差小于精度。 可得迭代公式&#xff1a; x n 1 x n − f ( x n ) f ′ ( x n ) x_{…
阅读更多...
二分法和牛顿迭代法求平方根(Python实现)

二分法和牛顿迭代法求平方根(Python实现)

求一个数的平方根函数sqrt(int num) ,在大多数语言中都提供实现。那么要求一个数的平方根&#xff0c;是怎么实现的呢&#xff1f; 实际上求平方根的算法方法主要有两种&#xff1a;二分法(binary search)和牛顿迭代法(Newton iteration) 1&#xff1a;二分法 求根号5 a:折半…
阅读更多...
牛顿迭代法-求平方根

牛顿迭代法-求平方根

牛顿迭代法 求出根号a的近似值&#xff1a;首先随便猜一个近似值x&#xff0c;然后不断令x等于x和a/x的平均数&#xff0c;迭代个六七次后x的值就已经相当精确了。 例如&#xff0c;我想求根号2等于多少。假如我猜测的结果为4&#xff0c;虽然错的离谱&#xff0c;但你可以看到…
阅读更多...
迭代法求平方根-C

迭代法求平方根-C

迭代法求a的平方根的近似值&#xff0c;计算公式如下&#xff1a; 迭代是重复反馈过程的活动&#xff0c;目的是为了逼近所需目标或结果。每次对过程的重复称为一次“迭代”&#xff0c;而每一次迭代得到的结果会作为下一次迭代的初始值。 算法&#xff1a;先给定一个假设的平…
阅读更多...
用迭代法求某数a的平方根

用迭代法求某数a的平方根

今天晚上笔试题目最后一题很简单&#xff0c;可是自己做不出 &#xff0c;就是不用库函数&#xff0c;求一个浮点数的平方根。 立马想到用物理法&#xff0c;比如正方形的面积法等&#xff0c;可是求解出不出&#xff0c;然后就绕在里面了。归根到底还是平时的知识储备太少了&…
阅读更多...
Java基础——运行时异常和非运行时异常

Java基础——运行时异常和非运行时异常

文章目录 Java中异常机制的体系结构Error&#xff08;错误&#xff09;Exception&#xff08;异常&#xff09;运行时异常和非运行时异常的区别结束 Java中异常机制的体系结构 在Java中&#xff0c;万物皆对象&#xff0c;异常也不例外。 Exception&#xff08;异常&#xff0…
阅读更多...
Java编译时异常与运行时异常的区别

Java编译时异常与运行时异常的区别

Java的异常可以分为编译异常和运行异常&#xff0c;其主要区别&#xff1a; 编译异常要求程序员必须处理&#xff08;捕获或者抛出&#xff09;&#xff0c;不然没法通过编译。 而运行异常可以不处理。 这应该是纸面最明显的区别了&#xff0c;我认为更重要的区别是在处理机…
阅读更多...
运行时异常与非运行时异常有什么区别？

运行时异常与非运行时异常有什么区别？

运行时异常与非运行时异常有什么区别&#xff1f; 运行时异常 RuntimeException 又称为非检查异常 uncheck exception。是 Exception 的子类。 在 Java 中&#xff0c;异常可以分为两种。Error 和 Exception&#xff0c;它们的父类是 Throwable。 Error 一些底层的类出错&…
阅读更多...
杂谈——运行时异常和普通异常有什么区别

杂谈——运行时异常和普通异常有什么区别

说到异常&#xff0c;大家都熟悉&#xff0c;只要程序出错了&#xff0c;那么肯定会说&#xff1a;“哎呀&#xff0c;我的程序出错啦~它抛出异常啦”。 但单单以“异常”的名称来称呼它们&#xff0c;未免也太粗糙了。我们毕竟是一个精致的程序员&#xff0c;当然得知道他们到…
阅读更多...
常见的编译时异常和运行时异常

常见的编译时异常和运行时异常

常见的编译时异常和运行是异常 1、粉红色的是编译时异常 2、绿色的异常是运行时异常 3、声明为Error的&#xff0c;则属于严重错误&#xff0c;如系统崩溃、虚拟机错误、动态链接失败等&#xff0c;这些错误无法恢复或者不可能捕捉&#xff0c;将导致应用程序中断&#xff0c;…
阅读更多...
浅谈Java异常及其编译时异常和运行时异常的区别

浅谈Java异常及其编译时异常和运行时异常的区别

异常是程序编码和运行时经常发生的事件&#xff0c;了解异常有助于我们提高代码质量&#xff0c;增强系统的健壮性&#xff0c;这里总结一下Java编程中的异常、以及Java编译时异常和运行时异常的区别&#xff0c;并列举几种常见的异常&#xff0c;以供参考学习。 一、什么是异…
阅读更多...
Java 运行时异常和非运行时异常

Java 运行时异常和非运行时异常

异常类型分为两类&#xff1a;运行时异常和非运行时异常。 一、运行时异常&#xff1a; 运行时异常&#xff08;RuntimeException&#xff09;&#xff0c;一般不需要程序员进行捕获。 例如&#xff1a;NullPointException&#xff0c;IndexOutOfBoundsException。如果不对该…
阅读更多...
推荐文章

Copyright @ 2022~2023