Data structures (with python) - 2. Graph - 2.2. Undirected graph

Data structures (with python) - 2. Graph - 2.2. Undirected graph

 

💡 An undirected graph is graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are bidirectional. An undirected graph is sometimes called an undirected network. In contrast, a graph where the edges point in a direction is called a directed graph.

 

방향성 없는 그래프는 그래프, 즉 모든 가장자리가 양방향인 객체(정점 또는 노드라고 함)의 집합으로 서로 연결되어 있는 그래프입니다. 방향성 없는 그래프를 방향성 없는 네트워크라고도 합니다. 이와는 대조적으로, 가장자리가 한 방향을 가리키는 그래프를 방향성 그래프라고 합니다.

 

 

파이썬에서 역시 undirected graph 를 설명하는 방법은 
앞선 directed graph에서 설명할때 사용했던 인접리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)를 이용한다.

 

1. 인접 리스트 (Adjacency List)

- 인접 리스트는 그래프의 각 노드에 대한 인접 노드의 리스트를 저장하는 방식.

- 파이썬에서는 딕셔너리와 리스트를 이용해서 인접 리스트를 표현할 수 있다.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

 

이 graph는 'A':['B','C']는 A 노드가 B와 C 노드와 연결되어 있따는 것을 의미한다.

 

2. 인접행렬 (Adjacency Matrix)

- 인접 행렬은 그래프의 각 노드가 다른 노드와 연결되어 있는지를 이진값(0 또는 1)으로 표현한 2차원 행렬

- 파이썬에서는 2차원 리스트를 이용해 인접 행렬을 표현할수 있다.

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

 

이 인접행렬은 6개의 노드가 있는 무방향 그래프이다.

노드 0 - 1,2 연결

1 - 0,3,4 연결

2 - 0,5 연결

3 - 1 연결

4 - 1,5 연결

5 - 2,4 연결

 

(차후 그림 추가)

 

 

 

class UndirectedGraph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, node, neighbour):   
        if node not in self.graph:
            self.graph[node] = [neighbour]
        else:
            self.graph[node].append(neighbour)
        
        if neighbour not in self.graph:
            self.graph[neighbour] = [node]
        else:
            self.graph[neighbour].append(node)

위의 코드에서 add_edge 메서드를 사용해 노드 간의 엣지를 추가할 수 있다.

이 메서드는 무방향성 엣지를 표현, 노드에서 이웃노드로 그리고 이웃노드에서 노드로 양방향으로 연결된다.

 

앞서 Directed graph에서는 DFS로 그래프를 탐사했기에, 이번에는 BFS로 탐사해본다.

이 그래프를 BFS하는 메서드로 노드를 차례대로 탐색하는 메서드를 추가한다.

    def bfs(self, node): # 들여쓰기 주의
        visited = []
        queue = [node]

        while queue:
            current_node = queue.pop(0)
            if current_node not in visited:
                visited.append(current_node)
                if current_node in self.graph:
                    queue.extend(self.graph[current_node])
        return visited

 

위의 메서드에서 visited는 방문한 노드들의 목록을 저장하는 리스트,
queue는 방문할 노드들을 저장하는 리스트.

 

g = UndirectedGraph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')

print(g.bfs('A'))  # ['A', 'B', 'C', 'D']

 

위의 코드에서 'A' 노드에서 시작하여 BFS를 수행하면, 'B', 'D', 'C'순서로 노드를 방문하게 됩니다.