14-1강. 그래프(Graph) 개념과 표현

 

 

• (무방향) 그래프. G = (V, E)

  - V : 노드(node) 혹은 정점(vertex)

  - E : 노드 쌍을 연결하는 에지(edge) 혹은 링크(link)

  - 개체(object)들 간의 이진관계를 표현

  - n = |V|, m = |E|

 

 

• 방향그래프(Directetd Graph). G=(V, E)

  - 에지(u, v)는 u로부터 v로의 방향을 가짐

 

 

• 가중치 (weighted) 그래프

   - 에지마다 가중치(weight)가 지정

 

 

 

• 그래프의 표현

  - 인접행렬 (adjacency matrix)

 

인접행렬을 이용한 그래프의 표현

 

  - 인접리스트 (adjacency list)

인접리스트를 이용한 그래프의 표현

위의 그림에서 m은 엣지의 갯수를 나타낸다..

n(:노드의 갯수) + 2m(:노드 갯수) 이어서 저장공간은 O(n+m)이다.

 

 

• 방향그래프를 표현하는 방법

방향그래프를 인접리스트와 인접행렬을 이용해 표현

 

 

• 가중치 그래프의 인접행렬 표현

   - 에지의 존재를 나타내는 값으로 1 대신 에지의 가중치를 저장한다.

   - 에지가 없을 때, 혹은 대각선 : 

      - 특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서!

      - 예) 가중치가 거리 혹은 비용을 의미하는 경우라면! 엣지가 없으면 무한대(딱히 표현할 값이 없어서..)로 하고, 대각선은 0으로 한다.

      - 예) 가중치가 용량을 의미한다면, 엣지가 없을 때는 0으로 하고, 대각선은 무한대로 한다.

 

 

• 경로와 연결성

      - 무방향그래프 G=(V, E)에서 노드 u와 노드 v를 연결하는 경로(path)가 존재할 때, v와 u는 서로 연결되어 있다고 말한다.

      - 모든 노드 쌍들이 서로 연결된 그래프를 connected graph라고 한다.

connected graph

 

 

세 개의 연결요소 (connected component)로 구성된다.