[알고리즘] 그래프, 정점, 간선, 가중치, 트리

그래프

-정점과 간선으로 이루어진 집합들

 

 

정점(vertex)

-노드라고도 부른다. 점이라고 생각하면된다.

-그래프를 형성하는 기본단위이다.

 

간선(edge)

-정점을 잇는 선을 의미한다.

-관계, 경로 등이 될수있다.

-단방향간선, 양방향간선이 있다.

-indegree(들어오는간선), outdegree(에서 출발하는 간선, 나가는간선)

 

가중치

-정점과 정점 사이에 드는 비용

-시간이던, 돈이던,

 

 

트리

-나무를 뒤집은 구조를 가지고 있는 자료구조이다.

-edge로 연결된 node의 집합이다.

-자식노드와 부모노드로 이루어진 계층적인 구조를 가진다.

-무방향그래프(방향성 없다)

-사이클이 없는 자료구조

-트리는 그래프의 일종이다.

-vertex -1 = edge

-트리내의 어떤 노드와 노드까지의 경로는 반드시 있으며, 하나밖에 없다.

임의의 두 노드 사이의 경로는 유일무이하게 존재한다.

-가장 위: 루트노드

 가장 밑: 리프 노드

 안에 있는것들: 내부 노드

-깊이: 루트노드에서 특정노드까지 최단거리로 갔을때의 거리

 높이: 루트노드부터 리프노드까지의 거리중 가장 긴 거리

-숲: 트리로 이루어진 집합