Tree, Graph

그래프(Graph)

다리건너기 문제 : 정점과 간선 모음들의 결합

정점의 집합 V,  간선의 집합 E // 그래프 = G = (V,E)

인접 : 간선으로 연결 된 두 정점

/''''	- B   -	- , E
A	/	|
\....	- C ' -	- D

이 그?림에 따르면 정점 A에서 E까지는 ABE 와 ACE의 두 개의 경로를 이루고 있다.

 

그래프 내 모든 정점이 모두 연결되어 있으면 그래프가 연결되었다고 말한다. 연결된 그래프 내의 모든 정점은 하나 이상의 간선를 가지며 차수는 정점에 속한 간선들의 수를 말한다.A,B,D 는 2개의 간선을 가지므로 차수는 2이고, 정점 E,C는 간선의 수가 3개이므로 차수는 3이다.  

 

그래프는 무방향 / 방향 그래프로 나뉘며

이에 관한 예를 들자면 위의 그래프는 무방향 그래프로 (A,B), (B,A) 두 간선 모두 존재한다.

만약 A->B의 방향을 가지는 방향 그래프라면 <A,B> A가 tail이고 B가 Head인 간선을 단일로 가지며 그 역은 존재하지 않는다.

 

  그래프 이론의 정점을 자료구조로 표현할 때 노드로 표현한다. 노드의 이름과 정의가 아닌 노드의 수가 중요하다.

간선은 노드 간 연결을 의미하기에 아주 중요하다. 노드의 수와 간선을 저장하면 경로를 찾을 수 있고, 각 차수도 자동으로 계산하여 알 수 있다. 따라서 자료의 형태를 그래프로 표현 한 후 무엇을 저장할 지 결정해야 한다.

  다시말하자면 그래프 형태로 저장한다는 것은 노드와 간선이 정해진 모델에서 노드와 간선을 정의하여 저장한다. 그래프를 배열로 저장한다는 것은 노드 데이터를 배열 자료구조로 저장한다는 것이고, 간선을 데이터로 표현하여 저장한다는 것이다. 연결리스트도 마찬가지다.

  간선의 정의 방법은 연결되어 있거나 연결되지 않은 두가지 상태로 표현할 수 있으므로 연결되어 있으면 1, 아니라면 0 으로 표현할 수 있다.

 

 

 

인접 리스트

  간선이 있는 노드들을 리스트로 연결할 때, 가장 처음 리스트에 저장된 노드를 헤드 노드라고 하며, 무방향 그래프일 경우 헤드노드에 연결된 노드의 개수가 그 헤드노드의 차수가 된다.

graph_array={A:[B,C],B:[A,E],C:[A,D,E],D:[C,E],E[B,C,D]}

  하나의 예시로 dictionary 자료형을 이용하여 표현할 수 있고 이때 헤드노드는 키로, 값은 간선이 있는 노드들로 구성할 수 있다.

 

 

 

2차원배열

graph_array=[[0,1,1,0,0],[1,0,0,0,1],[1,0,0,1,1],[0,0,1,0,1],[0,1,1,1,0]]

	A	B	C	D	E
A	0	1	1	0	0
B	1	0	0	0	1
C	1	0	0	1	1
D	0	0	1	0	1
E	0	1	1	1	0

  이중 리스트 자료형을 이용하여 표현할 수 있고, 이때 저장되는 데이터는 간선에 대한 정보이다. 무방향 그래프일 경우 지정된 노드의 차수는 1의 합으로 계산할 수 있어 노드의 차수는 행의 합으로 표현한다.

 

  위의 두개의 자료구조를 통한 저장을 비교해 봤을 때 연결 리스트에서는 간선에 대한 정보가 아니라 노드에 대한 정보로 간선의 정보를 저장했으며, 배열에서는 노드에 대한 정보가 아니라 간선에 대한 정보를 젖아하여 표현한 것을 알 수 있다.

 

  이를 이용한 프림, 크러스컬, 다익스트라 알고리즘 등은 데이터를 그래프 자료구조로 저장한 후 저장된 데이터들을 이용하여 최단 거리를 찾는 알고리즘들이다. DFS, BFS 와 같은 깊이, 너비 탐색 알고리즘도 이를 통해 해결할 수 있다.

 

---

 

트리(Tree)

그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조를 말한다(뻗어 나갈 순 있으나 들어올 순 없다)

 = 노드와 연결된 노드 사이에는 부모와 자식(방향 그래프)관계로 단방향 연결 상태이며, 자식노드는 반드시 하나의 부모만 갖도록 하는 규칙이 있다. 

 

  다양한 형태의 트리는 여러 규칙들을 추가해 만들어진다.

B 트리는 자식 노드가 2개 이상을 정의할 수 있다.

이진 트리는 자식 노드가 2개 이하이다.

  완전 이진 트리는 자식 노드를 추가할 때 왼쪽부터 오른쪽으로 추가하는 규칙을 가진다.

  균형 이진 트리는 자식 노드 추가 위치는 상관없지만, 왼쪽가 오른쪽 레벨 차이가 1이하가 되도록 추가하는 트리 구조를 말한다.

 

A(Root)								level 0
B			C(Branch)		D			level 1
E	F(Slibling)				G	H	I	level 2
	J	K			J(Leaf)			level 3

D 의 degree : 3 / F의 degree : 2 (degree : 차수)

위의 트리는 레벨 3까지 정의되어 있으며, 8개의 가지 노드와 3개의 잎 노드로 구성된 트리이다.

 

  연결 리스트 자료구조로 저장할 때 각 노드는 두개의 주소값을 저장할 수 있는 영역을 갖도록 정의해야 한다. 

왼쪽 주소값 영역에는 왼쪽 자식 노드 데이터가 저장된 주소값이 저장되며, 오른쪽 주소값 영역에는 오른쪽 자식 노드 데이터가 저장된 주소값이 저장되도록 정의한다.

 

  2차원 배열 자료구조로 저장할 때는 부모 노드와 자식 노드를 연결 리스트로 연결하고, 자식 노드를 배열로 표현할 수 있다. 이때 인덱스 0에 저장된 데이터는 왼쪽 자식 노드이고, 인덱스 1에 저장된 데이터는 오른쪽 자식 노드로 정의한다.

 

  트리 자료구조는 효율적인 데이터 삽입과 삭제 방법을 제공한다. 트리 구조를 이용한 이진 탐색 알고리즘, 정렬 문제에 관한 힙 정렬 알고리즘 등이 있다. 

 

	그래프	트리
정의	노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조	그래프의 한 종류
방향성	방향/무방향 그래프 모두 존재	방향 그래프
사이클	사이클 가능 순환/비순환 그래프 모두 가능	사이클 불가능 비순환 그래프
루트 노드	루트 노드 개념이 없음	한 개의 루트 노드만 존재
부모-자식	부모-자식 개념이 없음	부모-자식 관계
모델	네트워크 모델	계층 모델
간선의 수	그래프에 따라 간선의 수가 다름 간선이 없을 수도 있음	노드가 n인 트리는 항상 n-1의 간선을 가짐 (n- root 1개)

 

---

그래프 순회

순환 != 순회 : 고리 != 돌다

  순회는 그래프 또는 트리 같은 연결 구조에서 모든 노드를 순차적으로 탐색하는 방법이다. 하나의 노드로 시작하여 차례대로 모든 노드를 한 번씩 방문하는 방법으로, 모든 노드 또는 특정 노드를 방문하는 방법을 찾기 위한 방법이다.

  예를 들면 도시와 도로를 그래프로 연결 하는 경우 특정 도시에서 다른 도시로 갈 수 있는 길이 있는지 확인할 때나 전자회로에서 단자와 연결선을 그래프로 표현하는 경우 특정 단자와 연결되어 있는지 확인할 때 순회 방법을 사용할 수 있다.

 

 

 

 

깊이 우선 순회(DSF : Depth First Search)

  시작 노드를 정하고 방문하지 않은 노드가 존재할 때까지 방문하는 방법이다.

• 현재 노드의 인접 노드 중 방문하지 않은 노드를 방문한다.
• 방문한 노드의 인접 노드 중 더 이상 방문하지 않은 인접 노드가 존재하지 않으면 방문했던 경로로 되돌아간다.
• 방문하지 않은 노드가 더 이상 존재하지 않으면 종료한다.

G---   \      \__	A --        \                \__	---         B        ------		----  E _/     |
		/             /--->       C         __/__	F ___
			___ D

  

  A 시작 가정 A[G,B,C] -> C[G,A,B,F,D] -> B[A,C,E] -> E[B,F,D] -> F[C,E] -> 

  깊이 순회 규칙에 따라 선택할 수 있는 방문하지 않은 노드가 없을 때 방문 했던 경로로 되돌아가게 되어 E[B,F,D] -> D[C,E] -> E[B,F,D] -> B[A,C,E] -> C [G,A,B,F,D] -> G[A,C] -> C[ G,A,B,F,D ] -> A[ G,B,C ] 종료

 

  깊이 우선 순회 방법은 시작 노드에서 한 방향으로 마지막 노드까지 방문하고, 방문 경로를 되돌아가면서 방문하지 않은 노드를 확인한 후 방문한다.

graph_array = {A:[B,C,G], B:[A,C,E], C:[A,B,F,D,G], D:[C,E], E:[B,F,D], F:[C,E], G:[A,C]}

graph_array = [[0,1,1,0,0,0,1],[1,0,1,0,1,0,0],[1,1,0,1,0,1,1],[0,0,1,0,1,0,0],[0,1,0,1,0,1,0],[0,0,1,0,1,0,0],[1,0,1,0,0,0,0]]

	A	B	C	D	E	F	G
A1           3	0	1	1	0	0	0	1
B3       3	1	0	1	0	1	0	0
C2       4  2	1	1	0	1	0	1	1
D    3  1	0	0	1	0	1	0	0
E4  2  2	0	1	0	1	0	1	0
F5  1	0	0	1	0	1	0	0
G        5  1	1	0	1	0	0	0	0

위와 같이 복잡하게 하기 싫으면 2차원 배열로 먼저 만들어서 1따라 가는게 편하다.

 

컴퓨터 알고리즘 동작

1.  시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상위 노드에 방문하지 않은 인접 노드가 있으면 인접 노드를 스택에 삽입하고 방문 처리한다.
3. 스택의 최상위 노드에 방문하지 않은 인접 노드가 없으면 스택에서 삭제한다
4. 스택이 빌 떄까지 수행한다.(스택의 마지막 노드는 시작 노드이다.)

[A]-> [A,C](push) -> [ACB](push) -> [ACBE](push) -> [ACBEF](push) -> [ACBE](pop) -> [ACBED](push) -> [ACBE](pop) ->  [ACB](pop) -> [AC](pop) -> [ACG](push) -> [AC](pop) -> [A](pop) -> [](pop)

 

  A는 처음 시작 노드였으며 A가 삭제된다는 것은 인접한 모든 노드가 방문되었다는 것을 의미하고, 리스트에 더 이상 값이 없다는 것은 주어진 그래프의 순회가 종료되었음을 의미한다.

 

 

 

 

너비 우선 순회(BSF: Breadth First Search)

시작 노드를 정하고 인접한 노드를 모두 방문하는 순회 방법이다.

• 현재 노드의 인접 노드를 모두 방문한다.
• 인접 노드 중 더 이상 방문하지 않은 인접 노드가 존재하지 않으면 방문했던 경로를 되돌아간다.
• 방문하지 않은 노드가 더 이상 존재하지 않으면 종료한다.

 

연결 리스트 방식 및 2차원 배열 방식

구조는 위의 구조와 동일하다고 생각하고 A를 시작지점으로 잡는다고 가정한다

A - B - C - G - B - E - C - D - F - E - D - F

 

컴퓨터 알고리즘 동작

1. 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내고 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 큐가 빌 떄까지 수행한다.(큐의 마지막 노드는 마지막으로 방문한 노드이다.)

큐 방식으로 구현한 너비우선순회BFS

 

 

P.128까지

 

다시는.. 다시는 티스토리 꾸미기 따윈 하지 않고

사진을 찍어서 글을 작성하겠다