ㅇTL
Graph 1 본문
* 선형 자료 구조 : array, linked list, stack, queue
비선형 자료구조 : tree, graph, hash !
Concepts
• graph 정의 : 하나 이상의 노드들의 집합 V와 두 노드)의 쌍으로 구성된 edhe들의 집합 E로 이루어진 자료구조
( 노드와 엣지의 집합으로 구성된 자료구조. pair(V, E) )
- tree는 graph의 특수한 경우 ! (Graph가 더 큰 범위)
• 종류
Directed graph ( = digraph )
- 화살표 있는거
- self-loop 있음
Undirected graph
- 화살표 없는거
- self-loop 없음
Weighed graph
- 각 엣지에 가중치가 부여되는 것 (거리를 의미~~ 거리가 서로 다름~~ 노드사이의 거리)
• 용어
Degree
• directed 에서
- out-degree : 나가는 엣지 개수
- in-degree : 들어오는 엣지 개수
- degree : out-degree + in-degree (다합친거)
• undirected 에서
- degree : 걍 edge 개수 (in, out이런 개념없음)
Adjacency
- (u,v) 가 edge일때 vertex v는 u와 adjacent 함
- directed ; not symmetric. 1->2 일 때 2는 1에 adj아님,, 1는 2에 adj (화살표 대상과만 인접)
- undirected ; symmetric. 1-2일 때 2와 1은 서로에게 인접(adj)
- 해당 엣지는 두 노드에 incident
Path
- 엣지 길 따라 가는거 순서 (인접한거끼리 갈 수 있다) <1,2>,<2,4>,<4,5> / <1,2,4,5> 이런거
- length : path에서 edge 개수 <1,2,4,5> 에서는 3 (weight잇으면 weight의 합!)
- path를 통해서 어떤 vertex에 도달할 수 있으면 reachable 하다고 한다
- u -> v 로 path를 통해 도달 가능하면 그 두 노드는 connected !
Simple path
- path에서 가는 점들에서 중복된게없는거. 다 distict . <1,2,4>는 맞고 <1,2,4,1,2>는 아님
Cycle and Simple cycle
- cycle : 자기 자신에게 돌아오는거 - 처음 노드와 마지막노드가 같은 simple path!
- simple cycle : 다 distict 인 cycle
An acyclic graph
: cycle이 없는 graph
A connected graph
: 모든 점들이 path로 연결되어있다 -> connected graph ( undirected 그래프에만 있는 개념 )
(하나 도달불가능하게 동떨어진게 없고 서로 어떻게든 길로 연결되어잇는거^^)
Connected component
: 최대의 connected graph 부분. 그림에서는 두개
Strongly connected (connected의 directed 그래프 버전^^)
: directed graph 에서 모든 점들이 서로 reachable 한 상태
Strongly connected component
: directed graph에서 최대로 strongly connected 한 subset
A complete graph
: 모든 점들이 서로서로 다 adjacent 한거
( 걍 해당점을 본인빼고 모든점이랑 연결하면 됨, undirected)
- n개의 점이 있을 때의 edge 개수 ; n(n-1)/2
Tree
: connected, acycle(사이클없음), (undirected?) graph
Graph representation (그래프 표현방법^^)
1. Adjacency List (인접 리스트)
: 바로 각 노드마다 인접한 노드를 저장한다 (딱 인접한친구들만. connected까지 가는거 절대 x^^)
- directed ; V+E 의 space 필요
- undirected ; edge가 두배 필요함. !!
- Weighted graph representation
* find하는 복잡도 : O(n+e) (n은 노드 개수, e는 엣지 개수)
2. Adjacency Matrix
: VxV matrix를 만들고, 엣지가 잇는 곳에 1표시함!
- directed는 1->2이면 row가 1이고 c가 2인 곳에만 1표시함!!
- undirected는 둘다 표시! -> 대칭형태 !! (당연) -> transpose해도 값이 같다~
- weighted는 해당 칸에 weight값을 씀! (대체로 w값은 거리니까, 엣지없는칸에는 무한대씀.0쓰면 아주가깝다는거니깐^^)
3. Adjacency multi list
=> path로 표현
핵심! 이미 쓴 정보는 지운다!
굳굳
Elementary Graph Operations (그래프 기본 동작)
Graph Searching
: 시작점에서 끝점까지 연결된 경로 찾음 (weighted면 최단경로찾음. 근데일단 우리는 weight없을경우)
= 한 노드 -> 다른 노드 path탐색하기 ^^
시작점에서 그래프 노드 다잇는 path탐색하는 것. 다연결해야함!! 모든 점!!
= 한 점에서 reachable한 모든 점 연결하는 것!
• Depth First Search (DFS) ; 깊이 우선 탐색
: D질때까지 간다. 끝까지 간다
시작 점과 연결되고&탐색안된 점중 임의로 하나 선택. 그렇게 쭉쭉쭉쭉쭉가다가
해당 vertext와 연결된거중 탐색안된게 없으면
이전노드로가서 쭉쭉쭉
이전노드로가서 쭉쭉쭉
끗~
알고리즘 -> stack 구조를 이용해 탐색할 Vertex들을 저장!!
1. 시작 vertext를 기준으로 연결된거중탐색안된걸 stack에 저장함
2. 더이상 연결된거중 탐색안된점 없으면 stack에 저장된거 하나를 빼서 1번과정 반복
3. stack비워지면 끝!
stack에서 나온노드가 현재 노드
a. 더이상 저장할게없으면 상위 노드를 뺀다 - 이게 그다음의 현재노드가 된다
b. 현재노드에서 연결노드들을 넣는다 그리고 a 반복
코드는
1. visited = true
2. 프린트
3. 다음노드찾아서(for문) dfs()돌림 끝
• Breadth First Search (BFS) ; 넓이 우선 탐색
: 레벨별로.가까운거부터 쭉쭉다 연결하고감 (이미연결된건 무시)
해당 vertext에 연결된 &탐색안된 모든 노드 연결함 - 그리고 다음
알고리즘 -> 큐 이용!!!
큐쓰는게 BTS !! BTS 큐^^
1. 시작 vertex기준으로 연결되고 탐색안된 점들을 queue에 저장
2. 더이상 그런 점 없으면 큐에서 그거빼서 1반복
3. 큐가 비면 끝
* 이렇게 DFS / BFS 한거의 결과 = spanning tree !
Spanning tree for G
: undirected 그래프에서 cycle없고 connected 이도록 고른거 -> spanning tree!
= 그래프의 최소 connected 그래프
점이 n개면 무조건 n-1개의 엣지가 존재하게됨!
모든 점+몇개의 edge 포함하도록. 그리고 모든 점은 connected
-> 여러유형의 spanning tree가 나올 수 있다
- cost of a spanning tree = 모든 edge의 weight의 합
- minimum-spanning-tree : cost가 최소인거
