[자료구조,개념] 그래프, 트리 (graph,tree)

그게 뭔데 컴덕아.

Graph (그래프)

• 비트코인 차트그래프 이런거 아닙니다. 자료구조입니다.
• 어떤 Node(vertex 또는 정점)와 Node(vertex 또는 정점)의 관계를 나타내는 자료구조입니다.
• 구성: Vertex(정점),Edge(간선)
• 표현식: G(V,E) , G=(V,E) 
• 간선이 방향성을 가지면, 방향성 그래프 / 무방향이면, 무방향 그래프 혹은 양방향 그래프
• 간선에 가중치가 있으면, 가중치 그래프.
• 순환(Cycle)이 하나라도 있다? => 순환 그래프. 순환이 하나도 없다 => 비순환(Acyclic) 그래프
• DAG (Directed Acyclic Graph) => 방향성 비순환 그래프인데, VCS(version control System) ,블록체인, git의 브랜치 등 다양한 곳에 많이 쓰여서, DAG라고 많이 부름.

G(3,2)인 무방향 그래프 예시

연결요소

• 그래프 중에서는 ,하나의 그래프 안에서, 정점과 간선이 서로 모두 연결 되있는게 아니라, 각자 따로 연결되서, 그래프 안에  그래프가 있는 것처럼 보이는게 있음.  이거 하나,하나를 연결 요소라고 함.
• 연결요소는 DFS,BFS탐색을 할때, 자연스럽게 구해진다. 방문했다는 것을 표시해야하기 때문.

Tree (트리 , 나무) - Graph

• 순환성이 없는 무방향 그래프
• 어떤 노드든지, root가 될 수 있음.
• 리프노드: 가장 말단(last) 노드 , 간선이 1개만 있음.
• node A에서 node B로 가는 경로는 반드시 존재하며, 유일하다.
• 노드개수 = 간선개수 +1 (트리의 특징 )

 

Tree - 자료구조형 

• 자료구조에서 TREE는 Root가 있는, 순환하지 않고, 방향성이 있는 그래프
• 흔히 , 떠올리는 Tree는 이 형태
• 컴공에서 자주 보는 알고리즘에 사용되는 Tree는 다 이 친구임. (black-red Tree, Binary search Tree , complete binary tree  등등)
• Root에서 간선을 따라, Top->Down 갈때마다, level이 1씩 증가한다고 표현함. (level 혹은 depth(깊이)라고 표현함)