목적지까지 가능 방법은 너무나도 많지 - Graph
세상에는 너무나도 많은 관계가 존재한다.
사람과 사람의 관계에서도 짝사랑같은 일방적인 관계가 있는 반면, 커플들처럼 양방향적인 관계또한 있다.
또한 인생에는 너무나도 많은 갈림길이 존재한다.
점심식사를 고를때도 중식,한식,일식 ... 그안에서도 짜장면,짬뽕,돼지불백,스시 등 등..
머릿속이 터질것 같은 이러한 고민들을 컴퓨터로 정리 할 수 있다. 바로 그래프를 통해서 말이다.
1. 그래프란?
그래프는 단순히 노드와 그 노드들을 연결하는 엣지를 모아놓은 것이다.
그 모음으로 실제 세계의 현상이나 사물 표현하는데 주로 사용한다.
그래프로 다음과 같이 사물들간의 관계와, 순서를 표현할 수 있다.
2. 용어.. 어디서 들어봤는데..
노드, 엣지.. 어디서 많이 봤던 용어 아닌가?
그렇다 트리에서 나온 용어이다.
용어의 쓰임이 비슷한 이유는 그래프가 트리의 한 종류이기 때문이다.
그런데 그래프가 트리일 때도 있고 아닐때도 있다. 이게 무슨말이지..?
3. 그래프의 특징
- 트리 일수도있고, 아닐수도 있고..
트리는 앞서 '방향성이 하나인 비순환성'을 지니고 있다고 했다.
하지만 그래프는 방향성을 지닐 수도 있고, 지니지 않을 수도 있다는 점에서 트리일 수도 있고, 아닐 수 도 있다.
짝사랑을 예로 들면, 방향성이 하나이고 비순환성을 지니고 있다. 이 때의 그래프는 트리일 수도 있지만하지만, 짝사랑의 대상이 자신
을 같이 좋아하면 순환성이 생긴다. 이때의 그래프는 트리의 어느 속성도 지니고 있지 않기 때문에 트리가 아니다.
4. 그래프의 종류
1) 엣지의 방향성에 대한 구분
2) cyclic에 대한구분
5. 그래프의 표현방법 2가지
- 인접행렬
노드간에 관계가 있으면 1, 없으면 0으로 구성된 표를 생성하여 그래프를 표현한다.
- 인접리스트
노드의 데이터를 key값으로 적어놓고, 인접한 노드들을 그 안에 정렬하는 방식
5. 의사코드를 이용해 그래프의 인자를 출력해보기
1. DFS(Depth-First Search)
// 스택을 이용하여 구현
// 스택에서 나왔거나, childNode가 없을때 자기자신을 출력하도록 한다.
// 1. 데이터를 담을 스택을 만든다.
// 2. 가장 상위에 위치한 노드를 하나씩 차례대로 스택에 넣어준다.
// 3. 단, 한 반복에 스택의 top이 하나씩 계속 출력되도록 한다.
// 4. 만약, 출력된 노드에 자식노드가 있다면, 스택에 담아주도록 한다. ==> 3번
// 5. 자식노드가 없다면 그냥 출력만 해준다.
2. BFS(Broad-First Search)
//큐를 이용하여 구현
//큐를 dequeque된 노드는 출력을 해주되, childNode의 유무를 확인해준다.
// 1. 큐에 상위 노드부터 하나씩 큐에 넣어준다.
// 2. dequeque된 노드의 데이터를 출력해주고, 출력된 노드에 자식노드가 있다면 차례대로 큐에 넣어준다. ==>1번
// 3. 출력된 노드에 자식노드가 없다면, 출력만 해준다.