[CLRS] [20-1] Representation of graphs

1. Graph?

- 두 대상 사이 관계를 나타낼 수 있는 자료구조

- 아래의 그림처럼 동그란 점들이 Node, 점끼리 이어진 선들이 edge가 됨.

1.1. wark?

- 두 Node을 잇는 edge가 존재하는 경우 둘을 인접한다고 정의한다.

-- 인접한 꼭짓점을 따라 이동한 족적을 Walk라고 한다.

- 시작점과 끝점이 동일한 경우 닫힌 walk라고 하며,

- 다른경우 열린 walk라고 한다.

 

1.2. path

- walk 가운데 중복된 꼭짓점이 존재하지 않는 것을 path라고한다.

1.3. cycle

- 닫힌 walk와 path의 조건을 모두 만족하는 경우 이를 cycle이라고 한다.

ex) 위의 그림에선 A - B - D - A 가 된다.

 

2. Directed Graph

- 엣지에 방향이 존재하는 경우 Directed Graph(유향 그래프), 방향이 존재하지 않으면 Undirected Graph(무향 그래프)라한다.

3. Graph 구현

3.1. 인접행렬로 표현하기

- 다음 그림과 같이 A는 B,D와 인접하기에 B,D에 1을 할당하고,

- B는 A,D,C와 인접하기에 A,C,D에 1을 할당하는 식으로 Matrix을 작성한다.

 

- 만약 Directed Graph라면 다음과 같이 표기하면 된다.

- 여기서 각 엣지에 가중치를 부여한다면 다음과 같이 작성이 가능하다.

 

4. Code 구현

Graph = [[0,4,0,0,0],
         [0,0,2,1,0],
         [0,0,0,0,8],
         [5,0,0,0,0],
         [0,0,0,10,0]]

Graph = {'A' : [('B',4)],
         'B' : [('C',2),('D',1)],
         'C' : [('E',8)],
         'D' : [('A',5)],
         'E' : [('D',10)]}