파 이 썬 토폴로지 정렬 지식 에 대한 설명

유 향 무 환 도(Directed Acyclic Graph 약칭 DAG)G 에 대해 토폴로지 정렬 을 하 는 것 은 G 의 모든 정점 을 하나의 선형 서열 로 배열 하여 그림 에서 임의의 정점 u 와 v 를 만 드 는 것 이다.만약 에 변(u,v)8712°E(G)가 있 으 면 u 는 선형 서열 에서 v 전에 나타난다.
일반적으로 이러한 선형 서열 은 토폴로지 순서(Topological Order)를 만족 시 키 는 서열 이 라 고 하 는데 토폴로지 서열 이 라 고 부른다.쉽게 말 하면 특정한 집합 상의 한 편차 에서 이 집합 상의 전 서 를 얻 을 수 있 는데 이 조작 을 토폴로지 정렬 이 라 고 한다.
그림 이론 에서 고리 가 없 는 그림 의 정점 으로 구 성 된 서열 로 다음 조건 을 만족 시 킬 때 이 그림 의 토폴로지 정렬(영어:Topological sorting)이 라 고 합 니 다.
4.567917.정점 마다 나타 나 고 한 번 만 나타난다4.567917.만약 에 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 toposort(graph):
 in_degrees = dict((u,0) for u in graph) #          0
 vertex_num = len(in_degrees)
 for u in graph:
  for v in graph[u]:
   in_degrees[v] += 1  #         
 Q = [u for u in in_degrees if in_degrees[u] == 0] #      0   
 Seq = []
 while Q:
  u = Q.pop()  #         
  Seq.append(u)
  for v in graph[u]:
   in_degrees[v] -= 1  #       
   if in_degrees[v] == 0:
    Q.append(v)   #       0   
 if len(Seq) == vertex_num:  #          0           ，       
  return Seq
 else:
  print("there's a circle.")
G = {
 'a':'bce',
 'b':'d',
 'c':'d',
 'd':'',
 'e':'cd'
}
print(toposort(G))

출력 결과:
['a', 'e', 'c', 'b', 'd']
파 이 썬 의 토폴로지 정렬 지식 에 대한 설명 은 여기까지 입 니 다.더 많은 파 이 썬 토폴로지 정렬 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!