Data structures (with python) - 2. Graph - 2.1. Directed graph

Data structures (with python) - 2. Graph - 2.1. Directed graph

 

💡 A directed graph is graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another. A directed graph is sometimes called a digraph or a directed network. In contrast, a graph where the edges are bidirectional is called an undirected graph.

 

방향성 그래프는 서로 연결된 객체(정점 또는 노드라고 함)의 집합으로, 모든 가장자리가 한 정점에서 다른 정점으로 향하는 그래프입니다. 방향성 그래프는 이중그래프(digraph) 또는 방향성 네트워크라고도 불립니다. 이와 대조적으로, 가장자리가 양방향인 그래프를 무방향 그래프라고 합니다.

 

출처 : 위키피디아

Oriented graph with corresponding incidence matrix

 

with python 이니 파이썬에서 방향성 그래프에 대해 알아봅시다.

파이썬에서 방향성 그래프 (Directed Graph) 를 구현하고 탐색하는 방법.

인접 리스트(Adjacency List)을 사용해서 설명하겠습니다.

(인접리스트 추후 다루기)

class DirectedGraph:
    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)

 

먼저, 방향성 그래프를 저장하는 클래스를 생성합니다.

이 클래스는 노드들의 목록을 저장하고, 노드들 간의 연결 관계를 관리합니다.

 

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

이 메서드는 방향성 엣지를 표현하므로, 노드에서 이웃 노드로만 연결됩니다.

 

다음으로, 이 그래프를 깊이 우선 탐색(DFS)하는 메서드를 추가해 보겠습니다.

DFS는 현재 노드에서 가능한 깊게 탐색하고, 더 이상 방문할 노드가 없을 때 이전 노드로 돌아가는 방식으로 작동합니다.

(추후에 DFS, BFS를 다룹니다)

 

    def dfs(self, node, visited): # 위 코드와 이어집니다 들여쓰기 주의
        if node not in visited:
            visited.append(node)
            if node in self.graph:
                for neighbour in self.graph[node]:
                    self.dfs(neighbour, visited)
        return visited

 

위의 메서드에서 visited는 방문한 노드들의 목록을 저장하는 리스트입니다.

재귀적으로 dfs메서드를 호출하여 그래프를 탐색합니다.

이 클래스를 사용하여 방향성 그래프를 생성하고 탐색해 봅시다.

 

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

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

 

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