인접리스트, BFS

그래프의 경로가 리스트로 주어질 경우 딕셔너리를 사용한 인접 리스트로 바꾸고 BFS로 탐색하는 방법입니다.

 

V, E = 6, 5
my_list = [[1,4],[1,3],[2,3],[2,5],[4,6]]
S, G = 1, 6

V는 노드의 수 E는 간선의 수 입니다.

S는 시작 노드 G는 목표 노드입니다.

 

my_list가 주어졌을 때 S 에서 G까지 간선이 연결되어있는지 알아보기위해 BFS를 사용했습니다.

우선 주어진 리스트를 딕셔너리로 바꿔줬습니다.

graph = {i : set([]) for i in range(1, V+1)}
for j in my_list:
    if j[0] in graph:
        graph[j[0]] = graph[j[0]] | set([j[1]])
    if j[1] in graph:
        graph[j[1]] = graph[j[1]] | set([j[0]])
        
#{1: {1, 2, 3, 4}, 2: {3, 5}, 3: {1, 2}, 4: {1, 6}, 5: {2}, 6: {4}}

 

시작점과 함께 그래프를 아래 bfs함수에 넣어주면 시작 노드가 거쳐가는 모든 경로를 보여줍니다. 

def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        n = queue.pop(0)
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
    
 print(bfs(graph, S))
 # [1, 2, 3, 4, 5, 6]

위 print된 결과 값으로 G와 S가 연결되어 있다는 것을 알 수 있습니다.

시작점 S에서 G까지 갔는지 판단하기 위해 ( in list ) 문을 사용합니다.

if G in bfs(graph, S):
    print(f"{G} 과 {S}은 연결된 노드입니다.")