DFS와 BFS

그래프

그래프 : 복잡하게 연결된 자료 객체 사이의 관계를 효율적으로 표현한 것

객체 : 정점

관계 : 간선 (= 객체간의 관계)

그래프 : 접점과 간선의 집합으로 구성됨 -> A와 B를 연결하는 간선 (A, B)

인접 : 간선으로 연결된 두 정점을 인접해 있다고 함

차수 : 정점에 연결된 간선의 수

경로 : 간선을 따라 갈 수 있는 길을 순서대로 나열한 것

연결그래프 : 모든 정점사이에 경로가 존재하는 그래프

트리 : 사이클을 가지지 않는 연결 그래프

 

그래프의 표현 : 인접리스트를 이용한 표현

인접리스트 : 각 정점이 인접한 정점 리스트를 갖도록 하는 것 -> [[], [2, 5], [1, 5, 4, 3], [4, 2], [3, 6, 5, 2], [2, 1, 4], [4]]

그래프 순회 : 하나의 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문하는 작업

 

깊이우선탐색 (DFS)

시작 정점에서 한 방향으로 가다가 더 이상 갈 수 없으면 가장 가까운 갈림길로 다시 돌아와 다른 방향을 다시 탐색

# 2. dfs를 실행해주는 함수를 만든다
# g : graph, / start : 탐색을 시작하는 정점, / visited : 방문했는지 확인하는 리스트
def DFS(graph, start, visited):
    # 시작하는 정점은 탐색을 했기 때문에 방문했다고 체크
    visited[start] = True
    print(start, end=' ')

    # 시작 정점부터 탐색 시작
    for i in graph[start]:
        if visited[i] is False:
            DFS(graph, i, visited)

g =[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
]
# 1. 방문했는지 여부를 기록하는 리스트를 만든다.
visited = [False] * len(g)

# 3. 함수를 실행한다
DFS(g, 1, visited)

 

너비우선탐색 (BFS)

시작 정점에서 가장 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문

# 2. deque를 import 해준다
from collections import deque

# 3. bfs를 구현한다
# g : graph, / start : 탐색을 시작하는 정점, / visited : 방문했는지 확인하는 리스트
def BFS(graph, start, visited):
    queue = deque()
    # 큐에 들어왔기 때문에 방문했다고 체크
    queue.append(start)
    visited[start] = True

    while queue:
        # 큐에서 제거하는 순간 진짜로 방문된 것
        v = queue.popleft()
        print(v, end=' ')
        # 방문한 정점과 인접한 정점 탐색
        for i in graph[v]:
            # 방문하지 않은 정점이라면
            if visited[i] is False:
                # 큐에 넣고 방문했다고 체크
                queue.append(i)
                visited[i] = True

g =[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
]

# 1. 정점의 방문 여부를 체크하는 리스트를 만든다
visited = [False] * len(g)

# 3. 함수를 실행한다
BFS(g, 1, visited)