티스토리 뷰
1. 개요
그래프는 데이터간 연관관계를 시각화하는데 초점을 맞춘 자료구조이다.
자료구조는 2가지 목적을 가지고있다. 데이터 저장/표현이다. 그 중 그래프는 특히 데이터 표현에 특화됐다.
일상적인 예시로 지하철 노선을 생각해보면 아래와 같은 방식으로 경로를 생각할 수 있다.
1) A지역에서 B지역까지 갈 수 있는 모든 경로
2) 그 중 노선(열차 방향)에 맞게 경로를 탐색할때 효율적인 경로
3) 그 중 사람수(밀집도/혼잡도)를 고려해서 경로를 탐색할 때 효율적인 경로
이런식으로 한 데이터에서 다른 데이터에 접근할 때 효율적인 경로를 탐색하는데 그래프가 많은 도움을 줄 수 있다.
물론 그래프는 여러 곳에서 활용될 수 있고 필자는 아직 경험이 없어서 어디에 활용될 수 있는가에 대한 전문적인 예시를 줄 순 없지만 적어도 왜 사용하는가에 대해서는 짚고 넘어가야될거 같아서 개요에 다음과 같은 내용을 포함했다.
그러면 그래프를 구성하는 요소는 무엇일까?
이렇게 그래프는 노드들이 간선으로 연결되어있는 형태이다.
이런 그래프를 G=(V,E)로 정의할 수 있다.
그래프 용어는 다음과 같이 정리할 수 있다.
- 정점(노드, Vertex) : 연결한 객체들을 의미
- 간선(Edge) : 정점들을 연결하는 선
- 경로(Path) : 정점A에서 정점B까지 간선을 따라 갈 수 있는 길을 순서대로 나열한 것을 의미
- 사이클(Cycle) : 경로의 시작 정점과 마지막 정점이 같은 경로를 의미
- 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
- 차수(Degree) : 정점에 연결되어 이는 간선의 수, 방향 그래프에서 진입/진출 차수의 합
- 진입차수(In-Degree) : 방향 그래프에서 정점을 머리로 하는 간선의 수, 정점으로 들어오는 간선
- 진출차수(Out-Degree) : 방향 그래프에서 정점을 꼬리로 하는 간선의 수, 정점에서 나가는 간선
2. 그래프 종류
트리는 그래프의 한 종류이다.[1] 트리의 형태에서 방향성을 가지고, 싸이클을 가지는 식으로 자료구조를 표현한 형태가 그래프이다. 더 자세히 다루면 트리는 계층을 도식화, 그래프는 관계를 도식화하는 정도로 이해할 수 있다.
1) 무방향 그래프(Undirected Graph)
무방향 그래프는 두 데이터를 연결하는 간선이 방향성을 가지지 않는 그래프를 의미한다. 이때 관계는 간선(A, B) == (B, A)라고 볼 수 있다.
주로 공간의 구성요소 중 인과관계가 없는 표현시 자주 사용할 수 있다.
2) 방향 그래프 (Directed Graph)
방향 그래프는 두 데이터를 연결하는 간선이 방향성을 가지는 그래프를 의미한다. 이때 관계는 간선<A, B> != <B, A>일 수 있다.
간선에 방향을 가짐으로 인해서 여러 가지 특성이 생긴다.
- 방향이 맞지 않다면 해당 데이터로 연결할 수 없음. 위 그림 중 [B, A]는 존재하지 않는 간선
- 써클이 생길 수 있음. 이로인해 데이터 탐색 시 미로처럼 본인이 간 곳을 저장하고 다음 방향을 체계적으로 분석해서 진행해야함
3) 가중치 그래프(Weight Graph)
가중치 그래프는 간선에 가중치 정보를 두어서 구성한 그래프를 의미한다. 위 예시에서 혼잡도를 기반으로 경로를 탐색할때 사용하는 그래프 정도로 이해할 수 있다. 간선에 숫자를 통해 중요도/비용 등을 표현한다.
주로 활용되는 곳은 네트워크로 데이터 전송시 라우터가 효율적인 경로를 탐색할때 주로 사용되는 알고리즘의 기반 자료구조이다. 필자는 이 부분때문에 궁금해서 체계적으로 정리하기 위해 본 포스터를 작성했다.
3. 그래프 표현
그래프는 2가지 방식으로 구현할 수 있다.[2]
1) 인접 행렬 (Adjacent Matrix)
노드를 2차원 배열로 표현하는 형태이다. 무방향/가중치 없는 그래프일 시 사용 가능한 표현이다.
모든 정점들의 연결 여부를 저장하므로 O(V2)의 공간을 요구하므로 공간 효율이 떨어지지만 정점이 서로 연결되어있는지 확인하는데 O(1)의 시간을 요구한다는 특징이 있따.
2) 인접 리스트 (Adjacency List)
주로 방향/가중치 그래프가 주어졌을 때 연결되어있는 상황을 리스트로 출력이 필요할때 사용되는 표현법이다.
연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하므로 공간 효율성이 우수하지만, 두 정점이 서로 연결되어있는지 확인하기 위해 O(v)의 시간이 요구된다.
말 그대로 리스트를 통해 표현한다.
그래프를 표현할때 행렬/리스트 중 선택하는 기준은 아직 체험해봐서 모르지만 절대적인 것은 없고 상황에 맞게 선택해야한다는 것으로 알고있다. 즉, 리스트로 표현하면 좋을때가 있고 행렬로 표현하면 좋을때가 있는데, 이는 각 표현 방법에 따른 장단점과 본인이 그래프를 사용하고자하는 분야에 맞게 적용해서 생각해야한다. 이후에 공부하면서 관련 노하우가 있다면 추가로 작성하도록 하겠다.
4. 그래프 구현(Method)
그래프 구현시 아래와 같은 메소드가 포함될 수 있다.
| 항목 | 설명 |
| .addNode() | 새로운 node를 생성하여 그래프에 추가한다. |
| .contains() | node.value가 존재하는 지 확인하고 boolean 값을 출력한다. |
| .removeNode() | node를 삭제하고, 연결되어 있는 간선 또한 제거한다. |
| .addEdge() | 새로운 edge 를 생성하여 두 개의 노드를 연결한다. |
| .hasEdge() | node가 서로 연결되어 있는 지 확인하여 boolean 값을 출력한다. |
| .removeEdge() | node를 연결하는 edge를 제거한다. |
| .forEachNode() | 각 노드를한 번씩 호출하여 그래프를 통과한다. |
5. 그래프 탐색
그래프의 탐색은 자칫 잘못하면 써클에 빠져 무한루프에 빠질 수 있으므로 효율적이고 체계적인 알고리즘 선택이 중요하다.
- BFS / DFS
- Minimum Spanning Tree
- Kruskal Algorithm
등이 있으며 이는 알고리즘 카테고리 [https://war2house-goodbye.tistory.com/34]에서 확인 가능하다.
6. 결론
결국 그래프는 데이터 저장 자체보다는 표현을 중요시하는 자료구조이며 노드와 간선을 통해 표현할 수 있다.
종류는 무방향/방향/가중치로 나눠지며 이에 대한 표현은 인접 행렬/인접 리스트를 통해 표현할 수 있다.
탐색은 특히 방향/가중치 그래프는 고려할 사항이 많으므로 상황에 따라 적절한 알고리즘을 선택하는것이 매우 중요하다.
6. 참고
[1] https://www.youtube.com/watch?v=fVcKN42YXXI
[TIL] 자료구조 Graph 이해하기
Graph
medium.com