그래프
정점과 간선으로 이루어진 자료구조를 뜻한다.
연결된 정점간의 관계를 표현할 수 있는 자료구조를 뜻하며,
주로 사용되는 용도는 지하철 노선도, 통신 네트워크 등등이 있다.
그래프의 구조
그래프의 구조에는 크게 간선 , 정점 으로 나뉘고 있지만 이러한 두 개로 여러가지 명칭들이 있다.
명칭
- 정점(Vertex) : 각 노드를 뜻한다.(파란색 원을 의미!!)
- 간선(Edge) : 노드와 노드를 연결하는 선 무 방향이든 방향이든 선으로 연결이 되어있다면 간선으로 취급을 한다.
- 인접 정점(Adjacent vertex) : 간선 하나를 두고 바로 연결된 정점
Ex) 무 방향 그래프를 기준으로 A의 인접 정점은 B , D이다. - 정점의 차수
무 방향 그래프에서 하나의 정점에 인접한 정점의 수! A는 B , D 를 연결하고 있으므로 2개!!
무방향 그래프 모든 정점 차수의 합은 그래프 간선의 수 2배를 의미한다. - 경로의 길이 : 경로를 구성한느데 사용되는 간선의 수
- 단순 경로 : 경로 중에서 반복되는 정점이 없는 경우의 수를 의미!
- 사이클 : 단순 경로의 시작 정점과 끝 정점이 동일한 경우
방향 그래프 기준 명칭
- 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수!
A를 기준으로는 진입 차수가 하나만(B) 있으므로 1개이다. - 진출 차수 : 방향 그래프에서 외부로 나가는 간선의 수!
A를 기준으로는 1개
이러한 그래프는 매우 트리와 유사한 구조를 띄고 있다. 하지만 트리도 마찬가지로 그래프의 한 종류이다. 즉 , 우리 코딩언어로 말씀드린다면 그래프 > 트리 가 더 큰 구조를 띈다. 그렇지만 명확하게 차이점을 알고가자!!
트리와 그래프의 차이
| 그래프 | 트리 | |
|---|---|---|
| 명확한 이론의 차이 | 노드와 간선으로 짜여진 자료구조 | 그래프의 한 종류 |
| 방향성 | 방향 그래프 , 무방향 그래프 | 방향 그래프 |
| 루트 노드 | 루트 노드란 계념이 없음 | 최상위 노드 |
| 간선의 수 | 그래프에 따라 간선 개수가 다름 | N개의 노드로 구성된 트리의 간선 수는 N - 1 |
| 순회 | DFS , BFS | Pre-Order,In-Order,Post-Order / Level-Order |
| 경로 | 두개 이상의 경로 가능 | 두 노드 간의 경로는 1개 |
그래프의 종류
1. 무방향 그래프
- 간선이 방향이 없는 그래프를 의미하고, 정점 A - B 간선의 표현으로는 (A,B) = (B,A)
2. 방향 그래프
- 간선에 방향이 있는 그래프를 뜻하며 해당 방향으로만 이동이 가능하다. 즉 무방향 그래프서 (A,B) != (B,A)나 같았지만 방향 그래프에서는 성립할 수 없다.
3. 가중치 그래프
- 그래프에서 정점과 정점을 연결하는 간선에서 값이 할당된 경우를 뜻한다. 즉 통행료와 비슷하다.
4. 완전 그래프
- 모든 정점이 서로 연결된 그래프를 의미한다. 그렇기 때문에 정점의 개수를 통해서 간선의 수를 구할 수 있다. n(n - 1)/2
그래프의 탐색
사실상 이러한 그래프의 알고리즘에서 가장 어려운 부분은 이 부분이다. 위에서는 간단히 그래프의 구조와 개념에 대해서 알아봤지만 이에 대한 탐색은 이해하기 어려울 뿐만 아니라 이것을 코드로 만들기에는 처음에 어려움이 있다.
그렇다면 우리는 어렵지만 그래프의 "탐색"이라는 단어에 걸맞게 탐색에 있어서는 방문했는지에 대한 여부가 필요로 하다. 는 것을 알고 공부에 들어가자!
그렇다면 여기서 알아가야 할것은!!
깊이 우선 탐색
1. DFS(Depth First Search) - Stack
- 시작점인 노드에서 시작해서 다음 노드들을 보고 갈 수 있는 방향으로 이동한다. 그다음으로 만약 선택한 방향으로 갈 수 있다면 계속 가지만 만약 없다면 다시 돌아와서 갈 수 있는 방향을 찾고 모든 노드를 탐색하는 방법이다.
즉 위와 같은 방식은 미로에 가깝다!
그렇다면 위와 같은 DFS에서도 마찬가지로 특징을 알아보자
- 자기 자신을 호출하는 순환 알고리즘 형태
- 전위 순회를 폼함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
- 마찬가지로 위에서 강조 했듯이 어떤 노드를 방문했는지 여부를 반드시 검사해야 한다.
순회 방법
1. 먼저 시작 지점을 선택을 하고 순회를 시작한다. - DFS의 순회를 할때는 일반적으로 Stack을 활용한다.
- 0이라는 시작 지점에서는 갈수 있는 경로가 1 , 4 정점이 있지만 1을 먼저 타고(어떻게 하냐에 따라 달라짐!!) - stack = {1, 4} -> {4}
- 그 다음으로 이제는 2 , 3 을 순서대로 타고 여기서 탈 때마다는 무조건 해당 노드를 방문했다는 배열이 필요로 하다. - stack = {2 , 3 ,4} -> {4}
- 그다음으로 stack의 남은 정점 4를 꺼내고, 순회가 끝난다.
- 순회가 끝난다면 다시 백트래킹을 통해서 방문할 수 있는 노드들이 있는지 확인하고 갈 수 없다면 이렇게 순회가 종료된다.
2. BFS(Breath-First Search) - Queue
- 위에서는 깊게 들어가서 탐색할 수 있을 때 까지 간선을 통해 정점을 탐색을 한다. 하지만 BFS는 넓게 탐색을 한다. 여기서 넓게에 포커스를 맞추고 이해를 해보자!!
앞서 말한 DFS에서는 깊게 깊게 타다가 탈수 있는 정점이 없다면 다시 돌아와 간선을 통해 탈 수 있는 노드들을 순회를 한다 하지만 BFS는 현재 노드에서 1 , 2 ,3 이라는 노드가 있다고 가정하자 BFS는 여기 1,2,3를 다 순회를 해보고 더 깊게 들어갈 수 있는지 여부를 찾는 형식이다.
BFS 특징
- 직관적이지 않은 면이 있다. 넓게 탐색을 하기 때문!
- BFS는 재귀적으로 동작하지 않는다.
- 마찬가지로 어떤 노드를 방문했는지 여부를 반드시 검사해야한다.
- 선입서출 - Queue를 사용
- Prim, Dijkstra 알고리즘과 유사하다.
순회 방법
1. 마찬가지로 시작 지점을 선택을 하고 순회를 시작한다. - Queue 구조
- 먼저 해당 0이라는 시작 지점에서 갈수 있는 정점들을 확인하고, 그 정점들을 queue구조에 넣는다. 당연히 이때는 방문했다는 표스릴 해줘야 한다. Queue -> {1, 2, 4}
- 그 다음 1부터 차근차근 꺼내면서 들어 갈수 있는 노드들이 있는지 확인을 한다.
- 하지만 꺼낸 정점이 막상 들어갈 수 있는 정점이 없다면 해당 정점 순회를 끝내고 다음 Queue에 있는 2, 4를 꺼낸다.
- 2 에서 갈수 있는 정점은 3 , 4 이지만 4는 이미 방문을 했기 때문에 3만을 방문하고 모든 방문을 종료하게 된다. 그렇게 된다면 방문의 순서는 최종적으로 -> 0 , 1 , 2, 4, 3
그래프 구현
그렇다면 이러한 순회 방법을 알아봤지만 정작 그래프의 구현은 제대로 알아보진 못했다. 우리가 일반적으로 생각을 한다면 이차원 배열이 있다. 하지만 나는 그래프를 구현하면서 인접리스트 형식으로도 그래프를 구성할 수 있다는 것을 알게 됐다. 그렇기에 다음으로는 그래프 구현에 알아보자!
인접 행렬
거창한 말이다. 하지만 우리가 자주 쓰는 new int[][]를 의미한다.
이러한 구성에 있어 장점은 일단 구현이 쉽고 간선 정보만 확인하기 때문에 빠른 장점을 가지고 있지만 단점 또한 명확하게 존재 한다. 전체 노드의 개수를 V 간선의 수를 E라고 가정했을 때 모든 노드를 다 확인해야 하므로 노드의 개수에 비례해서 그래프는 이야기는 달라집니다.
인접 리스트
하나의 노드에 여러개의 노드가 연결되어 있는 구조를 뛰고 있다는 구조이다. 즉 연결리스트 구조!
그래프의 각 정점에 인접한 정점들을 연결리스트로 표현하는 방법이다.
단!! 여기서 그래프가 무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접리스트에 반대편 정점의 노드를 추가해야 한다. - 즉 양방향
이러한 인접 리스트 방식에도 장단점이 있다. 메모리 사용량이 상대적으로 적고, 노드의 추가 삭제 빠르다. 실제로 지금 위 사진을 본다면 간선이 있는 부분만 추가가 되는 것을 볼 수 있는데 이 부분이 메모리적으로 이점이 있다. 하지만 이러한 빠른 접근 방식과 다르게 치명적인 단점을 가지고 있다. 간선 정보 확인이 상대적으로 오래 걸린다는 단점을 가지고 있다. 해당 간선에 대해서 무식하게 찾아야 하는 단점을 가지고 있기 때문이다.
시간 복잡도
그래프의 모든 간선을 조회한다.(N : 정점의 수 , E : 간선의 수)
- 인접 리스트로 표현된 그래프 : O(N + E)
- 인접 행렬로 표현된 그래프 : O(N^2)
마치면서
개인적으로 이렇게 내가 어려워한 부분들을 정리하면서 공부하는 방식이 제일 내 머릿속에 여운이 남는 거라는 것을 알지만 이렇게 정리하는 것은 시간이 그만큼 소요된다.
나는 강의 -> 알고리즘 문제 풀이 이렇게 넘어간 다음에 블로그에 정리를 함으로써 한 단계 더 알게 됐고,
기존에는 그저 아 이렇게 흘러간다는 것만을 알았지만 이번에 이렇게 탐색을 효율적으로 하는 거라는 것을 알게 돼서 기분이 매우 좋다.
해당 지식을 나눠준 사람들에게 감사함을 느낀다.
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://sarah950716.tistory.com/12
