[자료구조] 그래프

1. 그래프

그래프 자료구조란 개체들 간의 관계를 표현하는 추상적인 자료구조. 그래프는 방향이 있을수도, 없을수도 있다. 또, 순회하는 것도, 하지 않는 것도 있다.

 

트리 또한 그래프의 일종으로 볼 수도 있다. 하지만 그래프는 노드간의 관계, 트리는 노드간의 계층을 표현한다. 그래서 엄밀히는 다른 개념이다. 트리에는 그래프에는 없는 계층개념이 있기 때문이다.

object간의 관계를 표현을 할 때 유용하다(SNS 친구 추천, 도로 상의 차량 검색, 운송시스템). 그래프는 기본적으로 vert(노드 또는 정점)와 edge(간선)으로 연결되어있다.

 

2. 가중치 그래프

가중치 그래프(Weighted Graph)는 간선에 가중치가 부여되어 있는 그래프를 뜻한다.  지도를 그래프로 표현했다고 생각하면 이해가 쉽다. 예를 들어 'A도시에서 B도시는 5Km, C에서 D도시는 4Km 거리이다' 를 나타내려면 간선에 가중치를 부여하면 된다. 가중치 그래프는 네트워크(Network) 라고도 한다. (https://code-lab1.tistory.com/13)

 

[자료구조] 그래프(Graph)의 개념과 이해, 용어 | 인접행렬 vs 인접리스트 그래프 구현

 

 

3. 순회

순회는 Traversal로 명명되며, 그래프 또는 트리처럼 연결된 구조에서 노드를 한 번씩 탐색하는 개념이다. 순회의 목적은 모든 노드 또는 특정 노드를 방문하는 방법을 찾는 것이다. 전위, 중위, 후위 세가지 방법이 존재한다.

 

4. 그래프를 나타내는 방법

그래프를 나타내는 방법에는 여러가지가 있지만 컴퓨터에게 표현하는 것은 행렬과 리스트 두가지다.

 

행렬은 행과 열에 모두 각 노드를 쓴다. 그리고 간선으로 연결된 노드끼리는 1로, 연결되지 않은 노드끼리는 0으로 표기한다.

 

# 행렬 예시
self.edges = [[0,1,0,0,0,0,0],
              [0,0,1,1,0,0,0],
              [0,0,0,0,1,0,0],
              [0,0,0,0,0,1,1],
              [0,0,1,0,0,0,0],
              [0,0,1,0,0,0,0],
              [1,0,0,0,0,1,0]]

 

리스트는 각 노드마다 연결된 노드를 각각 쓴다. 보통 해시테이블 형식이다.

# 리스트 예시
self.vertices = {
                    "A": {"B"},      # 여기서 {"B"}가 set의 형태이다.
                    "B": {"C", "D"}, # {"B" : {}}의 형태는 딕셔너리
                    "C": {"E"},      # 즉, 딕셔너리 안에 set이 있는 것이다.
                    "D": {"F", "G"},
                    "E": {"C"},
                    "F": {"C"},
                    "G": {"A", "F"}
                }