[Jungle][TIL] 240404 dfs/bfs/다익스트라/이분 그래프/최소 신장 트리

• dfs/bfs 구현하기

import sys
input = sys.stdin.readline
from collections import deque 

N = int(input())
graph = [[]*(N+1) for _ in range(N+1)]

for _ in range(N-1):
	a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
 

dfs_visited = [False]* (N+1)

def dfs(v):
	dfs_visited[v] = True
    
    for i in graph[v]:
    	if not visited[i] and graph[v]:
        	dfs(i)
            dfs_visited[i] = v
                
---

def bfs():
	queue = deque([1])
    
    while queue:
    	a= queue.popleft()
        for i in graph[a]:
        	if not bfs_visited[i]:
            	bfs_visited[i] = a
                queue.append(i)
                
   
   return bfs_visited[2:] 
   
 print(bfs())
 

dfs/bfs 개념을 이해했다고 생각했지만 어떤 방식으로 진행되는지 왜 진행되는지를 정확하게 설명할 수 있을정도로 알지 못한다.
총체적인 과정에 대한 이해와 개념, 구현력 모두 부족한 상태!

bfs와 다익스트라 간단 비교

bfs는 큐를 활용해서 모든 정점을 방문하는 것

다익스트라는 우선순위 큐를 활용해서 가중치가 있는 그래프에서 최소 경로를 찾는다. => 우선순위 큐를 구현하기 위해 heap, 최소 힙을 활용한다.

distance=  [INF for _ in range(N+1)]
이렇게 무한대로 초기값을 설정한다. 

q= []
#current_node, cost 
heapq.heappush(q, (start, 0))


c, s = heappop(heap)

최소 신장 트리

신장트리: 그래프 내의 모든 정점이 연결된 그래프,
간선의 수가 가장 적은 최소 연결 부분 그래프
find(), union() 왜 쓰는가?
=> 싸이클 형성 유무를 파악하기 위해

이분 그래프

dfs/bfs깊이를 탐색할 때마다 group을 확인해서 탐색한다.

def dfs(start, group):
    global error
    if error:
        return
    #해당 그룹으로 등록
    visited[start] = group
    for i in graph[start]:
        if not visited[i]:
            dfs(i, -group)
        elif visited[start] == visited[i]:
            error = True
            return