자료구조 Graph

그래프(Graph)

 단순히 노드(N, Node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아놓은 자료 구조이다. 연결 되어있는 객체 간의 관계를 표현할 수 있고, 여러개의 고립된 부분 그래프로 구성될 수 있다.

 

그래프의 특징

• 그래프는 네트워크 모델이다
• 2개 이상의 경로가 가능하다.(노드들 사이에 무방향/방향 또는 양방향 경로를 가질 수 있다)
• 루트 노드라는 개념이 없다
• 부모-자식 관계개념이 없다.
• 간선의 유무는 그래프에 따라 다르다.

그래프와 트리의 차이

	그래프(Graph	트리(Tree)
정의	노드와 그 노드를 잇는 간선을 하나로 모아 놓은 자료구조	그래프의 한 종류 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한종류
방향성	방향 그래프(Directed)와 무방향 그래프(Undirected) 모두 존재.	방향 그래프(Directed Graph)
사이클	사이클(Cycle)가능 자체 간선(self-loop) 가능 순환 그래프(Cyclic), 비순환 그래프(Acyclic) 모두 존재	사이클 불가능 자체간선 불가능 비순환 그래프
루트 노드	루트 노드의 개념이 없다.	한 개의 루트 노드만이 존재. 모든 자식 노드는 한 개의 부모 노드만을 가진다.
부모-자식	부모-자식 개념이 없다.	부모-자식 관계 top-bottom또는  bottom-top으로 이루어진다.
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS안의 pre, in, post-order
간선의 수	그래프에 따라 간선의 수가 다르다. 간선이 없을 수도 있다.	노드가 N인 트리는 항상 N-1의 간선을 가짐
경로		임의의 두 노드 간의 경로는 유일

그래프 구조

• 정점(Vertex): 그래프(Graph)의 각 노드는 정점이라 부른다. 각 정
• 간선(Edge):  두 정점 사이의 경로 또는 선을 나타낸다. 
• 인접 정점(Adjacency): 두 노드, 정점이 서로 연결되어 있는 관계를 인접 정점이라 한다.
• 경로(Path): 경로는 두 정점 사이의 가장자리를 나타낸다. 
• 사이클(Cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

인접 리스트(Adjacency List)

모든 정점을 인접 리스트에 저장한다. 각각의 정점에 인접한 정점들을 리스트로 표시한 것

 

 

장점

• 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있다.
• 그래프에 존재하는 모든 간선의 수는 O(V + E) 안에 알 수 있다.(인접리스트 전체조사)

단점

• 간선의 존재여부를 알기 위해 노드를 탐색하는데 정점의 차수만큼의 시간이 필요하다.

인접 행렬(Adjacency Array)

인접행렬은 간선과 접점의 관계를 2차원 배열로 나타내는 방식이다. 인접 행렬을 V  x V 불린 행렬(Boolean Matrix)이며, Matrix[i][j]가 true라면 i -> j로 간선이 있다는 뜻이다.

//만약 노드 i가 j로 가는 간선이 존재하면?
matrix[i][j] = 1;
//아니면
matrix[i][j] = 0;
//양방향 그래프일 경우
matrix[i][j] = matrix[i][j]

인접행렬 예시(무,유 방향)

무방향 그래프와 그래프의 구현

 

방향그래프와 구현

무방향의 경우에는 [ i ] 에서 [ j ]로 가는 간선과 그반대로의 간선도 존재한다. 즉 방향이 없는 간선으로 서로 대칭이 된다.

 

인접행렬의 장 단점

장점

• 두 정점을 연결하는 간선의 존재 여부를 O(1)안에 즉시 알 수 있다.
• 장점의 차수는 O(N) 안에 알 수 있다.

단점

• 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야한다.
• 간선의 수를 구할경우 인접 행렬전체를 조사하기 때문에 시간복잡도는 O(N^2)가 된다.

정점의 개수가 N인 그래프를 인접 행렬로 표현특징.

무방향 그래프를 인접행렬로 표현한다면 대칭행렬이 된다.

 

그래프의 탐색

깊이우선 탐색(DFS, Depth-First Search)

루트 노드에서 시작해서 연결된 노드의 가지 하나의 최하단 노드까지 탐색 하고, 그다음 노드의 최하단까지 탐색한다. 전체적으로 깊게 탐색 한다고 해서 깊이 우선 탐색이라불린다.

 

특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 전위 순회(Pre-Order)를 보함한 다른 형태의 트리순회는 모두 DFS의 한 종류이다.
• 그래프 탐색의 경우 반드시  어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 그렇지 않을경우 무한루프에 빠질 위험이 있다.

 

너비우선탐색(BFS, Breadth-First Search)

루트 노드에서 시작해 탐색한 노드의 가장 인접한 노드들부터(좌우로) 먼저 탐색 한다음, 그 다음 자식 노드들을 넓게 탐색한다.

 

특징

• 직관적이지 않은 면이 있다.
• BFS는 재귀적으로 동작하지 않는다.
• 그래프 탐색의 경우 반드시  어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 그렇지 않을경우 무한루프에 빠질 위험이 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.

 

 

gmlwjd9405.github.io/2018/08/13/data-structure-graph.html