다음 두가지 조건을 가진 그래프라면 위상정렬을 할 수 있다. 1. 간선이 방향성을 가진 그래프여야한다. 2. 그래프 내부에 순환(cycle)이 없어야 한다. 위상정렬 코드 큐(deque)를 이용한 방식 from collections import deque num=10 indegree=[0 for _ in range(num+1)] result=[] a=[[] for _ in range(num+1)] def topology_sort(): q=deque() # 진입차수가 0인 노드를 큐에 삽입 for i in range(1,num+1): if indegree[i]==0: q.append(i) # 위상정렬이 수행되려면 정확히 n개의 노드를 방문 for i in range(1,num+1): if len(q)==0..

플로이드 워셜 알고리즘 -모든 정점에서 다른 모든 정점으로 가는 최소비용을 구하는 알고리즘 위 그래프를 2차원 배열의 형태로 보면 arr=[ [0,5,INF,8], [7,0,9,INF], [2,INF,0,4], [INF,INF,3,0], ] 플로이드 워셜 코드 def floyd_warshall(): dist=[[INF]* num for i in range(num)] for i in range(num): for j in range(num): dist[i][j]=arr[i][j] # 거처가는 노드 for k in range(num): # 출발 노드 for i in range(num): # 도착 노드 for j in range(num): if dist[i][k]+dist[k][j]

선형버전 / 파이썬 heapq 사용 개선된 버전 import sys import heapq from collections import deque INF=1000000 num=6 arr=[ [0,2,5,1,INF,INF], [2,0,3,2,INF,INF], [5,3,0,3,1,5], [1,2,3,0,1,INF], [INF,INF,1,1,0,2], [INF,INF,5,INF,2,0] ] visited=[0 for _ in range(num)] min_d=[0 for _ in range(num)] def get_small_idx(): min=INF idx=0 for i in range(num): if visited[i]!=1 and min_d[i]

union find 함수 + 크루스칼 알고리즘 code # 부모노드 찾는 함수 def getPar(arr,x): if arr[x]==x:return x arr[x]=getPar(arr,arr[x]) return arr[x] # 두 부모노드를 합치는 함수 def unionPar(arr,a,b,): a=getPar(arr,a) b=getPar(arr,b) if a

모든 정점(vertex)을 최소 비용의 간선(edge)로 연결하는 것. 1. 프림(prim) 알고리즘 이용 2. 크루스칼(kruskal) 알고리즘 이용

시간복잡도: O(n^2) def bubble_sort_improve(lists): global count1 n=len(lists) for loop in range(n-1): change=False for i in range(n-loop-1): if lists[i]>lists[i+1]: lists[i],lists[i+1]=lists[i+1],lists[i] count1+=1 change=True if change==False: break