[알고리즘] - 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를 어떻게 할건데?