[Code Tree] Graph, DFS, BFS 그래프 탐색

그래프

노드 - 각각의 지점, 정점(Vertex)

간선 - 정점과 정점을 잇는 선(Edge) / 간선에 값이 적혀 있으면 간선의 가중치라고 함

무방향 그래프 - 방향이 없음

방향 그래프 - 방향이 존재

 

차수(Degree) - 특정 노드와 연결된 정점의 수 / 방향 그래프는 진입, 진출 차수가 다름 

진입차수(In-degree) 

진출차수(Out-degree) 

 

사이클(Cycle) - 특정 지점에서 출발해서 다시 본래 지점으로 돌아올 수 있음

 

연결 관계에 따라 

연결 그래프: 모든 정점들에 대해서 어느 두 정점을 잡아도 갈 수 있는 경로가 존재하는 그래프

비연결 그래프(단절 그래프): 연결 그래프가 아닌 그래프 

 

인접 행렬로 그래프 만들기

그래프 구현 방식

1. 인접 행렬

2. 인접 리스트 

 

1. 인접 행렬로 구현

A -> B 로 가는 길이 있다면 배열의 값을 1로, 가는 길이 없다면 0으로 지정한다. 

• 특정 정점 I, J 가 연결되어 있는지를 확인: O(1)
• 특정 정점과 연결되어 있는 모든 정점을 확인: O(|V|)
• 공간 복잡도: O(|V|∗|V|)

2. 인접 리스트로 구현

|V|개의 연결 리스트를 만들고, 연결 리스트에 특정 정점과 인접해있는 정점들의 정보를 담는다. 

• 특정 정점 I, J 가 연결되어 있는지를 확인: O(min(degree(I),degree(J)))
• 특정 정점과 연결되어 있는 모든 정점을 확인:O(degree(X))
• 공간 복잡도: O(|V|+|E|)

---

DFS(Depth First Search) 깊이 우선 탐색

: 최대한 깊게 탐색한 후 더 이상 도달할 수 없는 상황이라면 이전으로 돌아간다. 

 

- 재귀(스택)를 활용해 구현

- 이전에 방문했던 지점은 다시 방문하지 않아야 한다. 

- visited 배열을 만들어서 방문 여부를 확인하며 진행

 

def dfs(pos):
	visit(pos)
    for children of pos:
    	if visited[child] == false:
        	dfs(child)

---

BFS(Breadth First Search) 너비 우선 탐색

: 자신의 이웃들을 먼저 모두 방문하는 방식으로 탐색 

- 시작점을 기준으로 가장 가까운 정점부터 방문 

 

- 큐를 사용해 구현

- 하나의 노드에 방문하게 되면, 그. 노드와 인접한 노드 중 방문한 적 없는 다른 노드를 모두 큐에 넣는다. 

 

DFS와 시간복잡도 동일 / O(|V| + |E|)

* 실제로 코드를 짜게 되면 DFS가 약간 느린 편인데, 재귀함수의 오버헤드 때문(함수를 동작시킬 때 발생하는 약간의 시간 지연을 의미)

def bfs(pos):
	q = queue()
    q.append(pos)
    visit(pos)
    while q is not empty:
    	node = q.pop()
        for children of node:
        	if visited[child] == false:
            	visit(child)
                q.push(child)

---

가중치가 동일한 그래프에서의 BFS

 

* BFS는 정의상 시작점으로부터 가까운 지점부터 방문하게 되기 때문에 가중치가 전부 동일한 그래프에서 최단 거리를 구할 수 있다.