말하는 감자

너비 우선 탐색 각 정점을 방문할 때마다 모든 인접 정점들을 검사하는 알고리즘이다. 처음 보는 정점이 있다면 방문예정이라고 표시하고 별도의 위치에 저장한다. 인접한 정점들을 모두 검사하고 나면, 목록에서 다음 정점을 꺼내어 방문하게 된다. 이 목록은 FIFO의 큐형태를 지니게 될 것이다. 한가지 특징은 모든 정점을 탐색할 수 있다는 것이다. 알고리즘의 큰 틀 # 슈도 코드 # 인접 리스트 or 인접 행렬 adj = [] # 발견 리스트 - false 로 초기화 discovered = [] # 방문 예정 큐 que = deque() def bfs(start): # 1. 시작점을 발견하고 방문 예정에 푸쉬한다. discovered[start] = True que.append(start) # 2. 방문 예정 ..

들어가기 전 한붓그리기로도 알려진 문제 오일러 서킷은 그래프 이론에서 첫 번째로 연구된 문제로 유명하다. 오일러 서킷은 주어진 도형의 모든 선을 정확히 한 번씩 그리고 시작점으로 돌아오는 문제이다. 결론부터 말하자면, 간선들이 하나의 컴포넌트에 포함되어 있고(부분 그래프가 없고) 모든 정점의 차수가 짝수라면 오일러 서킷은 항상 존재한다. 오일러 서킷을 찾아내는 알고리즘 # 슈도 코드 # 인접 행렬 adj = [[], ... ,[]] answer = [] dfs(here): answer.append(here) for there in adj[here]: while(adj[here][there] > 0): # 방문할 간선을 지운다 adj[here][there] -= 1 # 무향 그래프라면 # adj[there..

그래프의 탐색 알고리즘은 특정 정점을 찾아낸다기 보다는 정점들을 정해진 순서대로 둘러보기 위한 알고리즘으로 이해하는 것이 맞다. 가장 유명한 깊이 우선탐색과 너비 우선탐색의 컨셉과 문제상황들을 살펴본다. 깊이 우선 탐색 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다. 더이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다 (재귀호출로 구현한다. 그러면 종료하고 호출시점으로 돌아간다). 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하는 알고리즘이다. 알고리즘의 큰 틀 # 슈도 코드 # 인접 리스트 or 인접 행렬 adj = [] # 정점의 방문 여부 리스트 - false 로 초기화 visite..

그래프의 기본 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등이 주변에서 찾을 수 있는 연결 구조의 예들이다. 트리에 있었던 부모 자식 관계에 관한 제약이 없기 때문에 다양한 구조를 표현할 수 있는 장점이 있다. 그래프는 다양한 구조가 있지만 트리에 비해 훨씬 더 정적인 용도로 사용된다. 다른 말로 하면 새로운 정점이나 간선을 추가하고 삭제하는 일이 자주 일어나지 않는다는 의미이다. 따라서 대부분의 그래프는 구조의 변경이 어렵더라도 좀더 간단하고 메모리를 적게 차지하는 방법으로 구현한다. 간단한 방법으로 구현한다는 것은 노드(정점)과 엣지(간선)을 간단하게 저장한다는 것인데 1) 노드에 번호를 매긴다. 2) 노드에 해당하는 정보를 배열에 저장한다. 3) 엣지의 정보를..