Graph
그래프 종류
- 방향 그래프 vs 무향 그래프(코테에서 가장 많이 출제)
- 다중 그래프 vs 단순 그래프
- 가중치 그래프 (다익스트라)
인접 행렬(adjaency matrix)
전체적으로 자기자신과 연결된 그래프는 없다.
0번 index가 2번 인덱스와 연결이 되어 있기 때문에 2번째 list에서 0번째 index가 1(true)이다.
즉, \ 방향을 기준으로 가르면 \ 부분은 전부 0이고 그걸 기준으로 대칭 시켜보면 완전히 대칭된다는 것을 알 수 있다.
graph = [
[0,0,1,0,1], # 2번이랑 4번 index와 연결되 있음
[0,0,1,1,1], # 2, 3, 4번 index와 연결되있음
[1,1,0,1,0], # 0, 1, 3번 index와 연결되있음
[0,1,1,0,1], # 1, 2, 4번 index와 연결되있음
[1,1,0,1,0] # 0, 1, 3번 index와 연결되있음
]인접 리스트(adjacency list)
위의 코드를 인접 리스트로 바꾸면 다음과 같다.
adj_list = {
0: [2, 4],
1: [2, 3, 4],
2: [0, 1, 3],
3: [1, 2, 4],
4: [0, 1, 3]
}암시적 그래프(implicit graph)
벽을 1로 통로를 0으로 놓고 그래프를 만드는 것이다.
BFS
First In First Out 방식의 접근 방법이다.
- 현재 Vertax와 연결되있는 모든 Vertax를 Queue에 넣는다 and 방문했다는 표시를 한다.
- Queue에서 새로운 Vertax를 가져와서 해당 Vertax와 연결된 모든 Vertax에 대해서 1의 작업을 해준다.
- Queue가 빌때까지 반복한다.
from collections import deque
def bfs(graph, start_v) :
visited = [start_v]
q = deque(start_v)
while q :
cur_v = q.popleft()
for v in graph[cur_v] :
if v not in visited :
visited.append(v)
q.append(v)
print(visited)
bfs(graph=graph, start_v="A")