[알고리즘] 그래프 - DFS, BFS

📈 그래프

데이터 간 관계를 표현한 자료구조

• 관계란? 데이터 사이의 연관성
• DFS
• BFS

---

인접행렬

• 장점 : 구현이 쉽다
• 단점 : 메모리 낭비 (불필요한 0도 표시)

graph = [
	   [0, 1, 0, 1, 0],	
       [1, 0, 1, 1, 1],
       [0, 1, 0, 0, 0],
       [1, 1, 0, 0, 1],
       [0, 1, 0, 1, 0]
        ]

---

DFS - 스택 구현

def dfs_stack(start):
    visited = []
    stack = [start]

    while stack:
        now = stack.pop()
        # 이미 방문한 지점이라면 continue
        if now in visited:
            continue

        # 방문하지 않은 지점이라면 방문 표시
        visited.append(now)

        # 갈 수 있는 곳들을 stack에 추가
        # 작은 번호부터 조회하려면 역순으로 순회
        # for next in range(4, -1, -1):
        for next in range(5):
            # 연결이 안되어있다면 continue
            if graph[now][next] == 0:
                continue

            # 방문한 지점이라면 stack에 추가하지 않음
            if next in visited:
                continue

            # 위 조건들을 모두 통과했으면 stack에 넣기
            stack.append(next)
    # 출력을 위한 반환
    return visited

print(*dfs_stack(0))  # 0 3 4 1 2         

• 조건은 취향 차
• 조건을 만족할 때의 코드 구현 : 백트래킹할 때 조건이 너무 많아질 수 있다
• 조건을 만족하지 않을 때의 코드 구현 : 명시성

DFS - 재귀 구현

• MAP 크기(길이)를 알 때 append 형식 말고 아래와 같이 사용하면 더 빠르다

visited = [0] * 5 

def dfs(now):
    # 재귀호출 생각해야 할 단계
    # 기저 조건
    # 들어가기 전 행동
    # 함수 호출
    # 돌아와서 할 행동
    visited[now] = 1  # 현재 지점 방문 표시
    print(now, end=' ')
    # 인접한 노드들을 방문
    for next in range(5):
        if graph[now][next] == 0:
            continue

        if visited[next]:
            continue
        dfs(next)
dfs(0)

---

BFS - 큐 구현

def bfs(start):
    visited = [0] * 5

    # 먼저 방문 했던 것을 먼저 처리 = queue
    queue = [start]
    visited[start] = 1

    while queue:
        # queue의 맨 앞 요소 꺼냄
        now = queue.pop(0)
        print(now, end=' ')

        # 인접 노드를 queue에 추가
        for next in range(5):
            # 연결이 안되어있다면 continue
            if graph[now][next] == 0:
                continue

            # 방문한 지점이라면 추가 x
            if visited[next]:
                continue

            queue.append(next)
            visited[next] = 1
bfs(0)

---

인접리스트

• 갈 수 있는 지점만 저장
• 노드마다 갈 수 있는 지점의 개수가 다름을 주의
• range 쓸 때 index 조심
• 메모리 적으로 인접행렬에 비해 훨씬 효율적
• dict로 작성하는 법도 있다

graph = [
    [1, 3],
    [0, 2, 3, 4],
    [1],
    [0, 1, 4],
    [1, 3]
]

graph = {
    '0': [1, 3],
    '1': [0, 2, 3, 4],
    '2': [1],
    '3': [0, 1, 4],
    '4': [1, 3]
}

---

추후 인접리스트 dfs, bfs 탐색 추가