[알고리즘] - Graph Algorithms

Graphs의 기본

  - Graph : 쌍들의 집합, 쌍을 이루는 원소 사이의 관계 (두 개의 객체를 묶어 놓으면 관계가 생겨)

  - Graoh의 구성 요소 : (V,E) / V : vertex, 정점 들의 집합 / E : edge , 간선 들의 집합

   - Dirextex : 방향 그래프 

   -undirexted graphp: 방향이 없는 무향 그래프

  - simple graph : loop 혹은 mutiplae edge(같은 하나의 정점에 두개 이상의 간선이 존재하는 경우) 가 없다 

                       

 

- Neighbor : 이웃, 

- Degree : vertex에 달려있는 간선들의 갯수(정점에 달려잇는 이웃들의 개수) (차수)

- Subgraph : 부분 그래프, 주어진 그래프 G에서  vertex와 간선들의 부분집합을 꺼내와서 만든 부분그래프

 

 

그래프의 경로에 대한 개념

- 경로 : 한 정점에서 다른 정점으로 가는 길

 1) walk : 정점들의 시퀀스 , 연속된 두개의 정점들은 서로 이웃관계 여야 한다.

 2) path: walk인데, 반복되는 정점이 없는 경우 

-도달 가능성 및 연결성

 도달가능성? 정점에서 다른 정점으로 갈수 있다.

  u에서 v로 가는 path가 존재한다면, 두 정점 사이에는 도달 가능하다.

  도달 가능성을 통해서 그래프가 연결되어있는지 아닌지를 이야기 할 수 있다.

  임의의 정점들 사이에 경로가 존재한다면, 그래프는 연결 가능하다. (connectedness)

  어떤 정점 v에서 u로 가는 walk 존재한다면, v에서 u로 가는 path도 존재한다.

 - Closed walk and cycle

Closed walk : walk가 시작점과 끝점이 같은 정점인 경우

 cycle : 반복되는 정점이 없는 closed walk, 출발점과 도착지가 같아 하나의 loop을 만듦

 acyclic : 사이클이 없는 그래프, 예시 : tree ( 사이클이 존재하지 않는 연결된 그래프)

 

 그래프의 표현법

 정점은 점으로, 간선은 선으로

하나의 그래프를 그리는 방법은 무한히 많다.

 

그래프의 자료구조

- 인접 리스트 ( adjaceny list) 

 리스트의 배열 , 리스트는 각 정점들의 인접한 다른 정점들을 저장한다. 

- 인접 행렬법 

 서로 인접한 것들은 1을쓰고 그렇지 않으면 0을쓴다( 간선이 있다면 1을, 없다면0을)

  인접행렬법을 쓰는게 편해

하지만 공간(메모리를)를 많이 쓰게 된다.

리스트에 달려있는 노드의 개수는 degree의 갯수랑 같다

 

간선이 많은 그래프  -> 행렬 그래프

간선이 많지 않은 그래프 -> 리스트

 

Searching in graphs

- DFS / BFS

- DFS : 깊이 우선탐색

 

 - BFS : DFS에서 스택 대신에 큐를 쓰면 된다. 너비우선탐색

 

Spanning Tree

- simple undirected connected graph

- 모든 정점들을 포함하고 있는 트리 형태의 sub graph

- 그래프가 connected여야 스패닝 트리가 존재한다. 왜? 트리 자체가 connected graph니깐

- 스패닝 트리는  가장 적은 갯수의 간선을 포함한 연결된 그래프이다.

 

Minimum Spanning Tree

-Connected graph, undirected, weight(가중치)가 최소인 subgraph

 

Kruskal's algorithm

입력 : 가중치가 주어진 simple, undirected, connected graph G= (V,E)

출력 : minimum spanning tree

 

- greedy algorithm 활용

 각 edge를 최종 mst에 포함시킬까 말까의 결정의 연속으로 문제를 해결한다.

  greedy choice에서 뭘 기준으로해?

     -> Weight(가중치)를 기준으로 한다.

     -> weight가 작은 edge를 우선으로 선택하여 추가한다.

     -> 단 추가했을때, cycle을 만들면 안된다. 

 

슈더 코드

1. weigth가 증가하는 순서대로 정렬을 한다.

2. F라는 변수를 사용해서 , 처음에는 간선이 없는 정점들만 잇는 상태

3.  i에는 1부터 간선의 갯수를 대입

4. weigth가  i번쨰로 가장 작은애들ㄹ e라고 하면 F+e를 했을 때, 사이클이 생기지 않으면, F에다가 i를 추가한다.

5. 반복

 

문제는 사이클이 생기는지 안생기는지 어떻게 알까? 즉 Cycle test를 어떻게 할건데?