목적지까지 가능 방법은 너무나도 많지 - 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. 출력된 노드에 자식노드가 없다면, 출력만 해준다.