그래프의 탐색으로 부터의 응용: 연결성분(부분그래프,Connected component)과 신장트리(Spanning Tree, 모든 정점을 포함하는 트리)

 

보통 그래프 탐색의 두가지 방법으로 DFS, BFS를 배우고 나면 배운 탐색방법을 가지고 응용된 문제를 접하게 되는데 그중 널리 알려진 것이 연결성분(부분그래프Connected Component)과 신장트리(그래프의 모든 정점을 포함하는 트리,Spanning Tree)이다. 이번 포스팅은 기본적인 DFS, BFS코드가 응용에 들어가면서 어떻게 변형이 되는지를 중점으로 보려고 한다.

#연결성분(부분 그래프)-탐색의 응용1. 탐색하여 부분그래프 리스트들의 리스트를 출력하는 것으로 표현됨

 

#신장트리-탐색의 응용2. 탐색중에 사용된 간선들을 출력하는 것으로 표현됨

 

1.부분그래프 (연결성분, Connected component)

 

우선 기본적인 DFS, BFS코드는 아래와 같다.

def dfs(graph, start, visited=set()):
    if(start not in visited):
        visited.add(start)
        print(start, end=" ")
        for i in graph[start]:
            if i  not in visited:
                dfs(graph, i, visited)
                
def bfs(graph, start):

    deque=collections.deque([start])
    visited=set([start])
    while deque:
        v=deque.popleft()
        print(v, end=' ')
        nbr=graph[v]-visited
        for i in nbr:
            visited.add(i)
            deque.append(i)

연결성분(부분 그래프)을 따지기 위해서 DFS에 변형을 가해 주는데 매개변수에 부분 그래프의 정점들을 담을 수 있는 리스트인 color를 추가해 주어 함수 dfs_cc를 만든다.

def dfs_cc(graph, color, start, visited):
	if(start not in visited):
        visited.add(start)
        color.append(start)#일반적인 DFS탐색이었다면 이 자리에 print(start, end=' ')가 들어감(재귀 DFS에서는 자료구조를 사용하지 않으므로 방문을
        #의미하는 visited에 정점을 추가한 후 이렇게 행위를 코딩함. 반면 bfs같은 경우 자료구조를 사용하므로 pop한 이후에 행위를 코딩함)
        for i in graph[start]:
            if i not in visited:
                dfs_cc(graph, color, i, visited)
        return color #재귀호출 한후 반환하는데(바로 윗줄) 그 반환되는 것을 받지 않으므로 이렇게 return 문을 작성해도 별다른 지장 없음

이렇게 하면 연결성분의 개수와 부분그래프의 정점 리스트를 출력하게 되는 코드는 아래와 같다.

graph={"A":set(["B","C"]),"B":set(["A"]),"C":set(["A"]),"D":set(["E"]), "E":set(["D"])}

import collections
#connected component=연결요소=부분 그래프
def find_connected_component(graph):
    visited=set()
    colorList=[]
    for i in graph:
        if i not in visited:
            color=dfs_cc(graph, [], i, visited)
            # color=bfs_cc(graph,[],i, visited)
            colorList.append(color)
    print(len(colorList))
    print(colorList)


def dfs_cc(graph, color, start, visited):
    if(start not in visited):
        visited.add(start)
        color.append(start)#일반적인 DFS탐색이었다면 이 자리에 print(start, end=' ')가 들어감(재귀 DFS에서는 자료구조를 사용하지 않으므로 방문을
        #의미하는 visited에 정점을 추가한 후 이렇게 행위를 코딩함. 반면 bfs같은 경우 자료구조를 사용하므로 pop한 이후에 행위를 코딩함)
        nbr=graph[start]-visited
        for v in nbr:
            dfs_cc(graph, color, v, visited)
        
        return color#재귀호출 한후 반환하는데(바로 윗줄) 그 반환되는 것을 받지 않으므로 이렇게 return 문을 작성해도 별다른 지장 없음

       

# def bfs_cc(graph,color, start,visited):
#     deque=collections.deque([start])
#     visited.add(start)
#     while deque:
#         v=deque.popleft()
#         color.append(v)
#         nbr=graph[v]-visited
#         for v in nbr:
#             visited.add(v)
#             deque.append(v)
#     return color


find_connected_component(graph)

참고로 dfs가 아닌 bfs로 부분 그래프(연결 성분)에 대한 정보를 찾을수 있는 코드는 위의 주석으로 남겨놓았다(물론 내가 짬)

(아래 그래프 참고 해서 테스트 해 볼수 있으면 해 보기

mygraph={"A":set(["B","C"]),

"B":set(["A"]),

"C":set(["A"]),

"D":set(["E"]),

"E":set(["D"])

}

print("Find connected component")

)

 

2. 신장트리(Spanning Tree 그래프의 모든 정점을 연결한 트리로 보통 탐색에 사용된 모든 간선을 출력해 주는 것으로 표현된다)

 

신장트리를 물론 BFS, DFS탐색 방식으로 모두 구현할 수 있다. 여기서는 BFS를 사용한 방식으로 탐색하여 그래프의 모든 정점을 탐색하면서 사용된 모든 간선을 표시해 주었다. 정말 코드 약간만 변경했다. 즉 신장트리란 그래프의 탐색 그 자체인 것이다.

신장트리: 그래프의 모든 정점을 연결한 트리로 그래프 탐색 그 자체이다. 보통 탐색에 사용된 간선을 출력함으로써 표현한다.

graph={"A":{"B","C"},"B":{"A","D"},"C":{"A","D","E"}, "D":{"B","C","F"},
        "E":{"C","G","H"}, "F":{"D"},"G":{"E","H"},"H":{"E","G"}
}

def spanningTree(graph, start):
    visited=set([start])
    deque=collections.deque([start])#여기서 [start]로 하지않고 그냥 start로 해도 문제없음
    while deque:
        v=deque.popleft()
        #교수님께서 말하신 BFS에서는 반드시 POP한 다음에 탐색의 목적을 코딩하라는 말도
        #결국은 항상 옳진 않은것이다... 아래에서 보는바와같이 반복문을 돌면서 탐색의 목적인
        #print문을 실행하고 있다. 
        nbr=graph[v]-visited
        for i in nbr:
            print("(",v,",",i,")", end=' ')
            visited.add(i)
            deque.append(i)

spanningTree(graph, 'A')