그래프는 기본적으로 두가지 요소로 표시되며, V(vertices)와 E(edge)로 이루어진다.
Vertices는 정점을 말하며 Edge는 이어주는 다리라고 생각하면 되겠다.
그래프에서는 정점(Vertices)들은 객체나 다른 요소들로 의미 부여가 가능하며, 연결(Edge)는 정점과의 관계 혹은 연결이라고 생각하여
이를 추상화하여 생각한 다음 만들어 이를 생성하면 그것이 바로 그래프가 되는 것이다.
이를 두고 그래프에서도 방향성(directed) 을 가지고 있느냐, 아니면 무방향성(undricected) 인가에 따라, 그래프의 종류가 나뉘어지며,
1.4 Graph의 연결성과 순환성 (connectivity)
방향성 그래프와 무방향성 그래프는 연결성의 성질이 다르며, 이부분에 대해 좀 정확히 구분하기 위해서
이를 추상화하여 생각한 다음 만들어 이를 생성하면 그것이 바로 그래프가 되는 것이다.
- 그래프의 구조
이를 두고 그래프에서도 방향성(directed) 을 가지고 있느냐, 아니면 무방향성(undricected) 인가에 따라, 그래프의 종류가 나뉘어지며,
방향성(directed) 그래프는 때로는 arch라고도 말한다.
Graph Wiki
https://en.wikipedia.org/wiki/Directed_graph
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Undirected_graph
1.1 기본 그래프 표시
기본개념을 알았으니, 그래프를 어떻게 수식으로 표현을 하는지를 알아봐야겠다.
아래와 같이 기본 그래프들은 아래와 같이 표시한다.
G = (V,E)
G의 두개(V,E) 의 수식이 정점을 표현을 하기때문에 상위 G는 연결(Edge)를 표현을 해준다고 생각하면 되겠다.
예를 들면, 방향성 그래프에서 한 Edge가 정점 u에서 정점 v로 간다면 이를 (u,v)로 표시
1.2 그래프 표시 적용 예
아래의 그래프는 무방향성(undirected) 그래프로 이를 표현하기 위해서는 무방향성 그래프의 특징을 알아야한다.
무뱡향 그래프는 (u,v)와 (v,u) 가 동일하며, 이 중복된 부분들은 생략을 한다.
아래의 그림과 같이 정점(V)은 총 6개로 구성된다.
V={1,2,3,4,5,6}
그리고 아래와 같이 현재 무방향성이기 때문에 G를 표현을 하면 아래와 같이 연결된 노드는 7개로 구성이 된다.
E={ (1,5) , (1,2) (2,5) , (2,3) , (3,4) , (4,5) , (4,6) }
Graph 이론
https://en.wikipedia.org/wiki/Graph_theory
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)
1.3 Graph의 기본 용어 정리
이제 그래프의 기본 표현방식과 관련된 부분을 알아봤으니 관련용어들을 알아보자.
Graph Wiki
https://en.wikipedia.org/wiki/Directed_graph
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Undirected_graph
1.1 기본 그래프 표시
기본개념을 알았으니, 그래프를 어떻게 수식으로 표현을 하는지를 알아봐야겠다.
아래와 같이 기본 그래프들은 아래와 같이 표시한다.
G = (V,E)
G의 두개(V,E) 의 수식이 정점을 표현을 하기때문에 상위 G는 연결(Edge)를 표현을 해준다고 생각하면 되겠다.
예를 들면, 방향성 그래프에서 한 Edge가 정점 u에서 정점 v로 간다면 이를 (u,v)로 표시
1.2 그래프 표시 적용 예
아래의 그래프는 무방향성(undirected) 그래프로 이를 표현하기 위해서는 무방향성 그래프의 특징을 알아야한다.
무뱡향 그래프는 (u,v)와 (v,u) 가 동일하며, 이 중복된 부분들은 생략을 한다.
아래의 그림과 같이 정점(V)은 총 6개로 구성된다.
V={1,2,3,4,5,6}
그리고 아래와 같이 현재 무방향성이기 때문에 G를 표현을 하면 아래와 같이 연결된 노드는 7개로 구성이 된다.
E={ (1,5) , (1,2) (2,5) , (2,3) , (3,4) , (4,5) , (4,6) }
 |
| https://en.wikipedia.org/wiki/Graph_theory |
Graph 이론
https://en.wikipedia.org/wiki/Graph_theory
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)
1.3 Graph의 기본 용어 정리
이제 그래프의 기본 표현방식과 관련된 부분을 알아봤으니 관련용어들을 알아보자.
- 무방향성(undirected) 그래프의 용어
무뱡향성 그래프에서 생각할 것은 정점과 연결이 되었는지 혹은 연결된 갯수는 몇개인지가 중요하다
- 차수(degree) : Vertex에서 연결되는 Edge의 수, 쉽게생각하면 한 정점에서 연결된 노드수
- 인접(adjacent or adjacency): 두개의 Vertex가 사이에 Edge 있다면 이를 Adjacent라고 한다, 즉 연결된 노드가 있다면 이를 인접
- 방향성(directed) 그래프의 용어
들어오는 노드 혹은 나가는 노드를 생각해야한다.
아래용어참조
- 정점(vertex)의 입력차수(in-degree): Vertex에 들어오는 Edge의 갯수
- 정점(vertex)의 출력차수(out-degree): Vertex에 나가는 Edge의 갯수
아래용어참조
1.4 Graph의 연결성과 순환성 (connectivity)
방향성 그래프와 무방향성 그래프는 연결성의 성질이 다르며, 이부분에 대해 좀 정확히 구분하기 위해서
아래와 같이 조건과 용어를 구분하여 설명하였다.
https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
https://en.wikipedia.org/wiki/Connected_component_(graph_theory)
개인적으로 볼때, 그래프에서 잊지 말아야할 부분은 그래프의 순환성이며,
https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
https://en.wikipedia.org/wiki/Connected_component_(graph_theory)
개인적으로 볼때, 그래프에서 잊지 말아야할 부분은 그래프의 순환성이며,
연결된 그래프를 구성하여 이를 동작할 때 루프에 빠질 수 있기 때문이다.
컴포넌트 개념은 정점의연결이며 이를 확장 및 또 다른 Graph의 연결하고,
컴포넌트 개념은 정점의연결이며 이를 확장 및 또 다른 Graph의 연결하고,
상위 순환성 문제에서 Loop를 빠지는 것을 방지하기 위해서,
방문한 장소를 기록하는 방법이 있다.
https://en.wikipedia.org/wiki/Directed_acyclic_graph (DAG , directed)
https://en.wikipedia.org/wiki/Tree_(graph_theory)#Forest (Forest, undirected)
1.조건-A
모든점(Vertex)들이 어떤 경로 즉, Edge를 걸쳐 서로 도달 할 수 있고 연결되어있다.
2. 조건-B
component의 정의가 다른 것 같다.
-용어: 연결된 객체 (connected component)
아래는 3개의 연결되지 않은 component를 보여준다.
https://en.wikipedia.org/wiki/Connected_component_(graph_theory)
-용어: 강하게 연결된 객체(strongly connected component)
아래의 예를 들어보자. 3개의 strongly connected component 존재한다
https://en.wikipedia.org/wiki/Strongly_connected_component
위 그래프를 간단히 분석해보면,
두 component 사이에 (b,c) dashed edge가 연결이되어 component가 연결이 된다.
a -> f 까지 연결이 가능하다 하지만, a->f 걸쳐 -e로 가지 못한다.
(f,g) 와 (c,d), (d,h)는 순환성을 가지고 기본적인 두 정점사이의 순환성을 가지고 있고,
a->b->e도 역시 순환성을 가지고 있다.
참고: C로 구현한 알고리즘 책
2. Graph 구현 방법
2.1 Adjacency Matrix ( Array 구현)
배열이 1부터 시작
Graph를 2차원 배열로도 표현이 가능하며 이를 Matrix로 표현이 가능하다.
2차원 배열로 표현을 한다면, 우선 중요한 것은 정점의 갯수로 NxN 배열을 구성하는 것이다.
그리고 상위 그림과 같이 정점의 입/출력차수를 2차원배열로 표현을 하는 것이다.
2차원배열로 구성할 경우에는 기본적으로 방향성그래프로 표현이 가능하기에, 무뱡향성 그래프도 표현이 가능하다.
상위 2차원 배열을 간단히 분석하면, X축과 Y축는 Vertex를 의미하고 배열 안의 값이 0,1,2 에따라 Edge의 상태가 표시된다.
좌표 (1,1)=2 // 동일한 정점 두개가 연결이 되었기 때문에 이를 2로 정의
좌표 (2,2)=0,
좌표 (3,3)=0
좌표 (4,4)=0
좌표 (5,5)=0
좌표 (6,6)=0
상위 그래프가 무향성 그래프이며 Matrix 대각선(상위왼쪽->하단오른쪽) 기준으로 대칭을 이루고 있어서 대각선 기준으로 한쪽부분 만 보면된다.
좌표 (1,2) (2,1) = 1
좌표 (1,5) (5,1) = 1
좌표 (2,3) (3,2) = 1
....
위 Matrix는 기본적으로 단방향성을 가지고 있어서 방향성(direct)을 표현이 가능하기 때문에 아래와 대각선 기준으로 위/아래를 입/출력으로 생각을 하면 쉽게 이해가 간다.
각 2차원 배열은의 값들은 Vertex 의미한다 (배열 1부터시작)
위에서 보았듯이 X축이 시작점이기 때문에 구현을 할때에도, column 기준으로 검색을 해야한다.
https://en.wikipedia.org/wiki/Adjacency_matrix
http://mathworld.wolfram.com/AdjacencyMatrix.html
2.2 Linked List 로 표현
위는 Matrix로 표현하기에 한정적으로 표현이 가능하지만, Set or Linked List로 표현을 하게되면 동적으로 확장이 마음대로 가능하다.
Set도 내부적으로 보면 Linked list로 구현하기때문에, Linked List로 표현했다.
확장개념은 위에서 본 컴포넌트 개념을 보면되겠다.
간단한 표현방법은 개별 Vertex는 Linked List를 가지고 있으며, 각 Edge 값들을 이곳에 보관하는 방법이다.
이곳에서 다루기에는 좀 소스가 커진다.
3. Graph의 탐색(Search) 방법
일반적으로 Graph에서 Search 하는 방법은 너비 우선(Breadth-first) or 깊이 우선(Depth-first)
DFS와 BFS는 Graph에만 한정되는 것이 아니라, Binary Tree에도 적용이 되며 다중으로 연결된 Graph 에도 적용이 된다.
3.1 Depth First Search
현재 근처 노드의 연결상태를 확인한 다음 근처 노드로 진행을 하고,
지나간 기록하면서 이를 찾아가는 방식이다.
아래의 예제는 방향성이 없는 DFS (Depth First Search)의 예제
http://cyberlingo.blogspot.kr/2015/03/depth-first-search-adjacency-matrix.html
http://www.thecrazyprogrammer.com/2014/03/depth-first-search-dfs-traversal-of-a-graph.html
https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm
DFS (Adjacency Matrix가 아닌 경우를 이용하여 사용)
http://blog.eairship.kr/268
3.2 Breadth First Search
Queue에 있는 Node에 연결된 모든 Edge 찾아가는 방식이지만,
구지 Edge가 아니여도 좋다.
https://en.wikipedia.org/wiki/Breadth-first_search
https://namu.wiki/w/BFS
https://www.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm
BFS ( Adjacency Matrix가 아닌 경우를 이용하여 사용 )
http://blog.eairship.kr/269
방문한 장소를 기록하는 방법이 있다.
- DAG(directed acyclic graph) : 방향성 비순환 그래프 ( Loop가 존재 하지 않는 Graph)
- acyclic : 비순환성 의미한다
https://en.wikipedia.org/wiki/Directed_acyclic_graph (DAG , directed)
https://en.wikipedia.org/wiki/Tree_(graph_theory)#Forest (Forest, undirected)
1.조건-A
모든점(Vertex)들이 어떤 경로 즉, Edge를 걸쳐 서로 도달 할 수 있고 연결되어있다.
- 무방향성 그래프
- 방향성 그래프
2. 조건-B
component의 정의가 다른 것 같다.
- 무방향성(undirected) 그래프
-용어: 연결된 객체 (connected component)
아래는 3개의 연결되지 않은 component를 보여준다.
https://en.wikipedia.org/wiki/Connected_component_(graph_theory)
- 방향성 (directed) 그래프
-용어: 강하게 연결된 객체(strongly connected component)
아래의 예를 들어보자. 3개의 strongly connected component 존재한다
- Vertex : {a, b, e}
- Vertex: {f, g}
- Vertex: {c, d, h}
https://en.wikipedia.org/wiki/Strongly_connected_component
위 그래프를 간단히 분석해보면,
두 component 사이에 (b,c) dashed edge가 연결이되어 component가 연결이 된다.
a -> f 까지 연결이 가능하다 하지만, a->f 걸쳐 -e로 가지 못한다.
(f,g) 와 (c,d), (d,h)는 순환성을 가지고 기본적인 두 정점사이의 순환성을 가지고 있고,
a->b->e도 역시 순환성을 가지고 있다.
참고: C로 구현한 알고리즘 책
2. Graph 구현 방법
2.1 Adjacency Matrix ( Array 구현)
배열이 1부터 시작
Graph를 2차원 배열로도 표현이 가능하며 이를 Matrix로 표현이 가능하다.
2차원 배열로 표현을 한다면, 우선 중요한 것은 정점의 갯수로 NxN 배열을 구성하는 것이다.
그리고 상위 그림과 같이 정점의 입/출력차수를 2차원배열로 표현을 하는 것이다.
2차원배열로 구성할 경우에는 기본적으로 방향성그래프로 표현이 가능하기에, 무뱡향성 그래프도 표현이 가능하다.
상위 2차원 배열을 간단히 분석하면, X축과 Y축는 Vertex를 의미하고 배열 안의 값이 0,1,2 에따라 Edge의 상태가 표시된다.
- 배열의 값 0: 미 연결
- 배열의 값 1: 단방향 연결 됨
- 배열의 값 2: 대각선만 이 값을 소유가능 (자신 Loop) (서로의 edge 더하여 2표시)
- Matrix 대각선
좌표 (1,1)=2 // 동일한 정점 두개가 연결이 되었기 때문에 이를 2로 정의
좌표 (2,2)=0,
좌표 (3,3)=0
좌표 (4,4)=0
좌표 (5,5)=0
좌표 (6,6)=0
상위 그래프가 무향성 그래프이며 Matrix 대각선(상위왼쪽->하단오른쪽) 기준으로 대칭을 이루고 있어서 대각선 기준으로 한쪽부분 만 보면된다.
좌표 (1,2) (2,1) = 1
좌표 (1,5) (5,1) = 1
좌표 (2,3) (3,2) = 1
....
- 방향성 (directed) 그래프
위 Matrix는 기본적으로 단방향성을 가지고 있어서 방향성(direct)을 표현이 가능하기 때문에 아래와 대각선 기준으로 위/아래를 입/출력으로 생각을 하면 쉽게 이해가 간다.
각 2차원 배열은의 값들은 Vertex 의미한다 (배열 1부터시작)
- matrx[1][2] (1,2) = 1 이는 1 -> 2 연결
- matrx[2]1] (2,3) = 1 이는 2 -> 3 연결
- X,Y축의 갯수는 Vertex의 출력차수이며, 동일하다
- X축은 시작점(Vertex)과 Y축은 종료점(Edge)
위에서 보았듯이 X축이 시작점이기 때문에 구현을 할때에도, column 기준으로 검색을 해야한다.
https://en.wikipedia.org/wiki/Adjacency_matrix
http://mathworld.wolfram.com/AdjacencyMatrix.html
2.2 Linked List 로 표현
위는 Matrix로 표현하기에 한정적으로 표현이 가능하지만, Set or Linked List로 표현을 하게되면 동적으로 확장이 마음대로 가능하다.
Set도 내부적으로 보면 Linked list로 구현하기때문에, Linked List로 표현했다.
확장개념은 위에서 본 컴포넌트 개념을 보면되겠다.
간단한 표현방법은 개별 Vertex는 Linked List를 가지고 있으며, 각 Edge 값들을 이곳에 보관하는 방법이다.
이곳에서 다루기에는 좀 소스가 커진다.
3. Graph의 탐색(Search) 방법
일반적으로 Graph에서 Search 하는 방법은 너비 우선(Breadth-first) or 깊이 우선(Depth-first)
DFS와 BFS는 Graph에만 한정되는 것이 아니라, Binary Tree에도 적용이 되며 다중으로 연결된 Graph 에도 적용이 된다.
3.1 Depth First Search
- Adjacency Matrix를 이용하여, DFS 를 구현
현재 근처 노드의 연결상태를 확인한 다음 근처 노드로 진행을 하고,
지나간 기록하면서 이를 찾아가는 방식이다.
아래의 예제는 방향성이 없는 DFS (Depth First Search)의 예제
http://cyberlingo.blogspot.kr/2015/03/depth-first-search-adjacency-matrix.html
http://www.thecrazyprogrammer.com/2014/03/depth-first-search-dfs-traversal-of-a-graph.html
https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm
DFS (Adjacency Matrix가 아닌 경우를 이용하여 사용)
http://blog.eairship.kr/268
3.2 Breadth First Search
- Adjacency Matrix를 이용하여, BFS 를 구현
Queue에 있는 Node에 연결된 모든 Edge 찾아가는 방식이지만,
구지 Edge가 아니여도 좋다.
https://en.wikipedia.org/wiki/Breadth-first_search
https://namu.wiki/w/BFS
https://www.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm
BFS ( Adjacency Matrix가 아닌 경우를 이용하여 사용 )
http://blog.eairship.kr/269