Python 拓扑排序及Python希尔排序

vlambda
2022-02-26

Python 拓扑排序及Python希尔排序

一、拓扑排序

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

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）：

每个顶点出现且只出现一次；
若A在序列中排在B的前面，则在图中不存在从B到A的路径。

from collections import defaultdict 
class Graph:  def __init__(self,vertices):  self.graph = defaultdict(list)  self.V = vertices
 def addEdge(self,u,v):  self.graph[u].append(v) 
 def topologicalSortUtil(self,v,visited,stack): 
 visited[v] = True
 for i in self.graph[v]:  if visited[i] == False:  self.topologicalSortUtil(i,visited,stack) 
 stack.insert(0,v) 
 def topologicalSort(self):  visited = [False]*self.V  stack =[] 
 for i in range(self.V):  if visited[i] == False:  self.topologicalSortUtil(i,visited,stack) 
 print (stack) 
g= Graph(6) g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); 
print ("拓扑排序结果：")g.topologicalSort()

以上代码执行输出结果为:

拓扑排序结果：[5, 4, 2, 3, 1, 0]

二、希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

def shellSort(arr):   n = len(arr) gap = int(n/2)  while gap > 0:   for i in range(gap,n):   temp = arr[i]  j = i  while j >= gap and arr[j-gap] >temp:  arr[j] = arr[j-gap]  j -= gap  arr[j] = temp  gap = int(gap/2) arr = [ 12, 34, 54, 2, 3]  n = len(arr) print ("排序前:") for i in range(n):  print(arr[i]),  shellSort(arr)  print ("\n排序后:") for i in range(n):  print(arr[i]),