그래프

일반적으로 그냥 그래프를 이야기 할 때에는 무방향 그래프를 의미한다. 그래프는 G = (V, E)와 같이 표현을 하는데, 여기서 V는 노드의 집합을, E는 엣지의 집합을 의미한다.

또한 n = 노드의 개수, m = 엣지의 개수로 표현하는 것이 일반적이다.

무방향 그래프에서 노드 사이의 엣지는 1개 이하로 가정한다. 물론 엣지가 여러 개가 존재할 수 있지만, 별도의 언급이 없는 한은 1개 이하이다.

• (무방향)그래프 G = (V, E)
  • V : 노드(node) 또는 정점(vertex)
  • E : 노드 쌍을 연결하는 엣지(edge) 혹은 링크(link)
  • 개체(object)들 간의 이진 관계를 표현

  • n =

    V

    , m =

    E

방향 그래프와 가중치 그래프

방향 그래프는 이름에서 알 수 있듯이 방향을 가지고 있다. 여기서 방향을 표현하는 (u, v)는 노드 u로부터 노드v로의 방향을 갖는데, 무방향 그래프와 다르게 (u, v)와 (v, u)는 서로 다르다.

가중치 그래프는 엣지 마다 가중치가 다르게 설정된다.

그래프의 표현

인접 행렬

그래프를 인접 행렬로 표현할 때는 위의 그림과 같이 (n x n) 2차원 배열로 표현한다. 여기서 배열의 각 요소는 1 또는 0을 갖는 것을 확인할 수 있는데, 이는 두 노드 사이의 엣지 여부를 의미한다.

또한 각 행 또는 열의 인덱스는 노드의 번호를 의미한다.

위 그림의 예를 들면 노드 1과 노드 2 사이에는 엣지가 존재하므로 [1, 2] = 1 && [2, 1] = 1이다. 반면 노드 1과 노드 7사이에는 엣지가 존재하지 않으므로 [1, 7] = 0 && [7, 1] = 0이다.

무방향 그래프를 인접 행렬로 표현했을 때에는 대각선을 기준으로 대칭 행렬이다.

2차원 배열을 이용한 인접 행렬 표현에서 그래프의 연산을 살펴보자. 어떤 노드 v에 인접한 모든 노드를 찾기 위한 연산은 v에 해당하는 행 또는 열의 모든 요소를 검사해야 하기 때문에 인접한 노드의 개수와는 상관이 없이 O(n) 이다.

반면 특정 노드 v와 u가 인접한지, 즉 엣지가 존재하는지는 [u, v] = 1 or 0의 여부를 검사하면 되므로 O(1)시간으로 찾을 수 있다.

2차원 배열로 표현하기 위해서는 위에서 언급했듯 (n x n) 크기의 배열이 필요하다. 즉, \($(n개의 노드)^2\)$ 만큼의 저장 공간이 필요하기 때문에 노드의 개수가 클 경우에는 조금 비효율 적일 수 있다.

인접 리스트

인접 행렬과 같이 자주 사용되는 그래프 표현 방법은 인접 리스트이다. 2차원 배열로 표현하는 인접 행렬과 달리 1차원 배열과 연결 리스트로 표현하는 것이 일반적이다.

인접 행렬에 비해서 인접한 모든 노드 검사 및 저장 공간에서 유리하다. 반면 두 노드 사이의 연결 여부를 검사하는 데에는 인접 행렬이 유리하다.

인접 리스트는 노드 개수만큼의 크기를 갖는 1차원 배열에서 각 인덱스가 노드의 번호를 표현하고, 해당 노드와 엣지로 연결된 다른 노드들은 연결 리스트의 요소로 저장된다. 이 연결 리스트에서 순서는 상관이 없다.

어떤 노드에 인접한 모든 노드 검사를 수행하는 연산의 시간복잡도는 연결리스트의 길이에 비례한다. 만일 이 연결리스트의 길이가 n이라면, 즉 모든 노드와 엣지로 연결되어 있다면 O(n)이다.

또한 두 노드 사이의 연결 여부에 대한 검사를 수행하는 연산의 시간 복잡도 역시 연결 리스트의 길이에 비례하는데, 어떤 노드가 갖는 연결 리스트의 요소들을 하나씩 검사하면서 연결된 특정 노드가 존재하는지 찾아야 하기 때문이다.

방향 그래프

인접 행렬로 방향 그래프를 표현할 때는 (u -> v)로 가는 엣지가 존재할 때 [u, v] = 1로 표현하고 없을 경우는 [u, v] = 0으로 표현한다. 무방향 그래프와 달리 [u, v]와 [v, u]가 서로 다를 수 있다. 즉, 대각선을 기준으로 대칭 되지 않는다.

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

가중치 그래프가 아닐 경우에는 엣지의 여부를 1과 0을 주로 이용해서 인접 행렬을 표현하는데, 가중치 그래프의 경우에는 엣지의 존재를 나타내는 값으로 1 대신 엣지의 가중치 값을 저장한다.

• 엣지의 존재를 나타내는 값으로 1대신 엣지의 가중치를 저장.

• 엣지가 없을 때 및 대각선

  • 특별히 정해진 규칙은 없으며, 그래프 가중치가 의미하는 바에 따라서 달라질 수 있다.
  • 예 : 가중치가 거리 혹은 비용을 의미하는 경우라면 엣지가 없으면 극한 값, 대각선은 0
  • 예 : 만약 가중치가 용량 등을 의미한다면 엣지가 없을 때 0, 대각선은 극한 값

경로와 연결성

보통 그래프에서 두 노드가 엣지로 직접 연결되어있는 경우 인접하다고 표현하고 직접 연결되어 있지는 않지만 노드를 타고 접근할 수 있는 경로가 존재하는 경우 연결되어있다고 표현한다.

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

• 모든 노드 쌍들이 서로 연결된 그래프를 연결 그래프라고 표현한다.

참고 및 출처

인프런 권오흠 교수님 강좌