lesson 6: Graph

1. 이곳에서 말하는 그래프는 위의 그림과 같다.

2. 그래프의 목적은 얼마나 다른 것들이 연결되어 있는 지 보여주는 것이며, 네트워크라고 부르기도 한다.  

 

 

1. 트리구조와 비슷하며, 연결의 대상이 되는 것을 노드(Node) 또는 Vertex라고 부르며 연결을 edge라고 한다.

2, 사실 트리는 그래프의 형태 중 하나이다. 마치 바이너리 트리가 트리의 중 하나이고, BST가 바이너리 트리의 하나인 것처럼 말이다.

 

 

1. 노드 뿐만 아니라 엣지도 연결의 강도와 같은 정보를 포함할 수 있다.

 

1. 그래프는 데이터 모델링을 위한 부가적인 특성들이 있다.

2. 엣지는 방향을 가지고 있으며, 이 방향은 두 노드 사이의 관계가 일방적임을 의미한다.

 

1. 만남을 표시할 때 처럼, 방향이 필요가 없는 모델은 언디렉티드 그래프를 사용한다.

 

 

 

 

1. 트리에서는 순환이 허용되지 않았지만, 그래프에서는 허용된다.

2. 그래프에서의 순환은 알고리즘을 만들 시 굉장히 위험할 수 있다.

 

1. 우리가 자주 보게 될 그래프는 DAG다.Directed Acylic Graph이다.

 

1 그래프의 또 다른 중요한 특성은 연결성(Conectivity)이다

2. 어느 쪽 그래프가 더 연결성이 좋다고 볼 수 있을까? 당연히 오른쪽이다. 왼쪽에서는 하나의 엣지만 삭제하더라도 모든 그래프의 연결이 끊어져 버린다.

 

1. 객체지향 언어를 사용한다면, Vertex와 edge에 여러가지 특성을 담을 수 있다.

2. edge list는 말 그대로 edge의 리스트이다. 

3. 리스트의 번호는 보통 vertex의 번호와 일치한다

4. 리스트의 원소는 해당 엣지가 연결하는 두 노드의 번호를 담게 된다.

5. 엣지 리스트가 리스트의 리스트를 담고 있는 구조 있기 때문에 2D 리스트라고도 부른다.

 

1. adjacency list는 edge를 표현하는 한 형태이다

2. adjacency list는 대응하는 vertex의 id 를 가지고 있다.

 

1. 컴퓨터 과학에서 매트릭스는 본질적으로 2 d 배열이며, 리스트 안의 모든 원소의 길이는 같다.

2. Adjacency Matrix는Adajacnt list와 비슷하며, 외부 첫번째 리스트의 인덱스는 노드의 번호를 가리킨다.  그리고 내부 리스트의 인덱스는 어떤 노드와 연결되어 있는지를 표시한다.

3. adjacent list에서는 내부 리스트가 대응하는 노드의 Id를 표시했다면 matrix의 내부 리스트는 모든 노드에 대한 하나의 슬랏을 가지고 있으며 그 슬랏에 노드의 id를 map(연결)시켜 놓았다.

4. 이 행렬의 대각선은 모두 0이다.

5. 각각의 엣지는 2번 등장한다.

6. 어떤 것이 본인의 의도를 잘표현하는지에 따라 사용하는 표현 방법은 달라진다.

 

 

1. DFS는 트리 구조에서 작동했던 것과 같은 원리로 작동한다.

2. 찾으면 멈춘다!

3. 트리 구조와는 다르게, 루트가 없기 때문에 시작하는 곳이 정해저 있지 않다.

4. 하나의 방법은 Stack인데, 확인한 노드를 스택 방식으로 쌓는 것이다. 

5. 새로운 엣지가 없다면, 스택 중의 하나의 노드를 선택한 뒤, 다른 엣지를 선택한다.

 

 

1. DFS를 하는 또 다른 방법은 스택 없이 반복문을 사용하는 것이다.

2. ?? 방법은 스택 을 사용할 때와 비슷하다. 하나의 노를 선택한 뒤, 엣지가 없을 때까지 반복한 후 다른 노드를 선택하낟.

3. 런타임은 Edge의 수와 Vertex의 수를 합친 것과 같다.

 

 

 

 

1. BFS에서는 큐를 사용한다. 큐는 퍼스트인 퍼스트 아웃이다.

2. 노드 하나를 선택하고 해당 노드와 연결된 모든 노드를 방문한다. 그리고 큐에 올린다.

3. 노드가 다 떨어지면, 디큐를 하고, 그 디큐 한 노드를 가지고 다시 시작점으로 삼는다.

4. 일종의 tree BFS라고 할 수 있다.(envision, 마음속에 그려보라)

5. 런타임은 엣지와 노드의 수를 더하 는것과 같다.

 

 

1. 모든 모든 엣지를 한 번만 통과하는 길(path)를 오일리안 패쓰라고(Eulerian path)라고 한다.

2. 오일리안 사이클에서는 모든 엣지를 한번만 지나가야 하며, 시작한 노드에서 끝이 나야 한다.

3. 모든 그래프가 오일리안 패쓰를 가질 수 없다는 것이 밝혀졌다.

4. 모든 노드가 같은 수의 엣지를 가지고 있거나, 짝수개의 엣지를 가지고 있는 오일리안 사이클을 그래프가 가지고 있을 때만 오일리안 패쓰를 가질 수 있다고 한다.

5. 올일리안 팼는 약간 lentient(관대하다)한데, 두개의 노드가 시작이나 끝지점에 한해서 홀수 개의 엣지를 가지는 것을 허용한다.

 

 

1. 아무 노드에서 시작하여, 다시 그 노드로 돌아오는 순환을 한 뒤, 지나왔던 노드 중 다른 노드와 연결된 노드를 택하여 반복한다.

 

2. 그리고 공통 노드를 통해 결합한다.

 

1. 해밀토니안 패쓰도 이와 유사한 패쓰이다. 그래프가 해밀토니안 패쓰를 가지는지 여부에 대한 논쟁은 유명하다.