Graph
개념
그래프 G=(V, E)
V : 노드 혹은 정점
E : 노드쌍을 연결하는 에지 혹은 링크
개체(object)들 간의 이진관계를 표현한다.
노드의 개수 n=|V|, 에지의 개수 m = |E|
보통은 노드와 에지는 중복되지 않는다.
서로 다른 두 노드를 연결하는 에지가 2개 이상이 되거나 셀프 에지는 고려하지 않는 것을 기본으로 한다.
다만, 방향그래프의 경우는 다를 수 있다.
종류
무방향 그래프 vs. 방향 그래프
cyclic graph vs. acyclic graph
무방향 그래프, undirected graph
방향 그래프, directed graph
에지(u, v))는 u로부터 v로의 방향을 가진다.
트리도 방향 그래프의 일종이다.
가중치 그래프
에지마다 가중치(weight)가 지정되어있다.
그래프의 표현
인접행렬, adjacency matrix
인접리스트, adjacency list
1. 인접행렬
서로 다른 두 노드간의 에지를 0과 1로 표현한 2차원 행렬이다.
무방향그래프를 기본으로 두고 말을 하자면,
대각선은 자기 자신과 연결되는 셀프 에지이므로, 0으로 채워진다.
대각선을 기준으로 양쪽은 대칭을 이룬다. 1-> 2로 연결되는 에지와 2->1로 연결되는 에지는 같은 것이기 때문이다.
저장공간은 N*N행렬이므로 N^2 이 필요하고
어떤 노드 v와 인접한 모든 노드를 찾는 것은 행렬의 한 행을 모두 검사해야할 수 있으므로, O(n) 의 시간이 소요된다.
어떤 에지(u, v)가 존재하는지 검사하는 것은 두 지점의 요소가 0인지 1인지만 체크하면 되므로, O(1)의 시간이 소요된다.
2. 인접리스트
각 노드를 모아놓은 하나의 배열을 두고, 그 정점과 연결된 노드들을 연결한 리스트로 표현하는 방법
저장공간의 경우, 각 노드별로 두 번씩 반복해서 나타날 것이기 때문에 n+2m -> O(n+m)
물론 m은 최악의 경우 (n개의 노드가 서로 모두 연결된 상태) n^2이 될 수 있지만, 항상 그렇다고 할 수는 없다.
어떤 노드 v에 인접한 모든 노드를 찾을 때는 O(degree(v))의 시간이 소요될 것이다. 여기서 degree(v)는 연결리스트의 길이를 의미한다.
어떤 에지 (u, v)가 존재하는지 검사하는 시간은 O(degree(u)) 의 시간이 소요된다. 예를 들면 3번과 4번이 연결되어있는지 확인하고자 한다면, 3번 연결 리스트를 모두 체크해보아야 한다. 역시 연결리스트의 길이만큼 시간이 소요되는 것이다.
방향그래프의 표현 - 인접행렬, 인접리스트
인접행렬은 무방향 그래프와 달리 비대칭이다. 셀프 엣지도 있을 수 있기 때문에 대각선에도 0이 아닌 1이 올 수 있고, 한 노드에서 다른 노드로 향하는 방향 엣지가 존재하느냐에 따라서 1이 표시되기 때문에 대각선을 기준으로 대칭이 아니다.
인접 리스트는 m개의 노드를 가지게 된다. 한 노드에서 다른 노드로 향하는 경우에만 연결 리스트로 구성되기 때문에 중복없이 m개의 노드만 표시된다.
가중치 그래프의 인접행렬 표현
가중치그래프는 여러가지 방법으로 표현할 수 있는데, 일반적으로는 에지의 존재를 나타내는 값으로 1대신에 가중치를 저장하는 방법이 많이 쓰인다. 에지가 없을 때나 대각선일 경우, 그래프와 가중치가 의미하는 바에 따라서 값을 넣으면 된다.
예를 들면, 가중치가 거리 혹은 비용을 의미한다면 에지가 없으면 무한대, 대각선이면 0 을 넣을 수 있고
가중치가 용량을 의미한다면, 에지가 없을 때 0, 대각선일 경우 무한대를 넣을 수 있겠다.
경로와 연결성
무방향그래프 G=(u, v)에서 노드 u와 노드 v를 연결하는 경로가 존재할 때, v와 u는 서로 연결되어있다고 말할 수 있다.
모든 노드 쌍들이 서로 연결된 그래프를 연결된 그래프라고 한다. 그리고 연결된 노드들의 덩어리를 연결 요소라고 한다.
Last updated
