[Python] DFS & BFS 코드와 graph 데이터 구조 이해

유향그래프 : 노드간 연결에 방향이 있는 그래프

먼저 유향 그래프에 대한 예제의 그래프 정보를 파악하자

---

위 그림과같은 노드간의 연결을 담은 그래프를 파이썬에서 구현하려면 아래와 같이 노드 번호와 해당 노드에서 갈 수 있는(간선이 존재하는) 노드에 대한 정보가 필요하다.

1번 노드에서 갈 수 있는 노드는 3, 4번 노드(화살표 주의)

2번 노드에서 갈 수 있는 노드는 3,4,5번 노드

…….

이를 아래와같은 구조로 저장해야한다.

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1

BFS 너비우선탐색 알고리즘

---

from collections import deque

def BFS_with_adj_list(graph, root):
    
		visited = [] # 한번 방문한 노드는 다시 방문하지않도록
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))

위의 코드는 조금 간략한 버전으로, 아래 코드를 돌려보면 출력문으로 BFS의 노드 방문 과정과, 어떤 판단을 거쳐 방문하는지, 방문하지않는지 알아볼 수 있다.

BFS알고리즘 이해용 코드

---

from collections import deque

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])
    
    iterCountForTest = 1
    while queue:
        
        print(f'iteration{iterCountForTest}')
        
        n = queue.popleft()
        print(f'popleft result = {n}')
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
        print(f'visited is = {visited}')
        print(f'queue is = {queue}')
        
        iterCountForTest += 1
        
        print('\\n')
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))

DFS

---

def DFS_with_adj_list(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

print(DFS_with_adj_list(graph_list, root_node))

네트워크 개수 문제 다른 두 풀이

---

# 내 풀이 인데, mylist 선언 후 remove 하는 idea 보다 node visit 아이디어가 더 좋은 것 같아
def solution(n, computers):
    answer = 0
    mylist = [i for i in range(n)]
    def connected_set(node_num):
        mylist.remove(node_num)
        for i in range(n):
            if i in mylist:
                if computers[node_num][i] == 1:
                    connected_set(i)
        return 1
    for i in range(n):
        if i in mylist:
            answer += connected_set(i)
    return answer

def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)] # = [0] * n
    def dfs(computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            # for i in range(len(computers)-1, -1, -1):
            for i in range(0, len(computers)):
                if computers[j][i] ==1 and visited[i] == 0:
                    stack.append(i)
    i=0
    while 0 in visited:
        if visited[i] ==0:
            dfs(computers, visited, i)
            answer +=1
        i+=1
    return answer