분류 전체보기338 최소신장트리!(프림과 크루스칼) *그래프 내의 모든 정점을 포함하는 트리(최소로) *사이클 있으면 ㄴㄴ 프림 — 시작정점을 기준으로 신장트리를 확장— 방법은 다익스트라와 동일한거 같음! 차이점- 다익스트라는 모든정점이 아닌 최단경로만 계산! 프림은 모든 정접을 지나가는 경로를 계산! def get_min_node(node_num): print("get_min_node 함수 진입했다") for i in range(node_num): if not visited[i]: v = i break print("아직 방문하지 않은 v: ", v) for i in range(node_num): if not visited[i] and distances[i] < distances[v]: print("i: ", i, "\\tv: ", v) print("di.. 2022. 3. 4. 다익스트라, 플로이드와샬, 벨만포드에 대해서! 가중치가 있는 그래프탐색! 다익스트라 — 시작점과 다른 모든 정점간의 최단경로를 탐색할때 사용 시작점부터 탐색하여 연결되는 정점의 거리를 최솟값으로 최신화 해주고 시작정점으로 부터 연결된 정점까지의 거리중 최솟값을 가지고 아직 방문하지않은 정점으로 이동하여 반복해줍니다. # 방문하지 않은 노드이면서 시작노드와 최단거리인 노드 반환 def get_smallest_node(): min_value = INF index = 0 for i in range(1, n+1): if not visited[i] and distance[i] < min_value: min_value = distance[i] index = i return index def dijkstra(start): # 시작노드 방문처리 distance[s.. 2022. 3. 4. BFS,DFS에 대해서 간선의 가중치가 없는 그래프 탐색! BFS-너비탐색 최단거리를 구하는 문제에서 자주 사용 큐를 이용하여 구현 탐색할수록 메모리 업업 최단거리는 무조건 보장 def bfs(graph, start_node):# 너비 # 큐사용해서 한쪽으로는 하나씩 꺼내주고 다른쪽으로는 꺼낸값의 자식노드를 입력받는 형태로 구성 visit = list() queue = list() queue.append(start_node) while queue: node = queue.pop(0) if node not in visit: visit.append(node) queue.extend(graph[node]) return visit BFS를 사용하는 경우, 알고리즘 문제풀이 그래프 탐색(BFS, DFS)에 대한 알고리즘 문제풀이 우리가.. 2022. 3. 4. 이전 1 ··· 65 66 67 68 다음 728x90 반응형
