graph

그래프는 노드(Node, 또는 정점 -vertex- 이라고도 부릅니다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성된다.

위에 그림은 무방향그래프를 나타낸 것인데
1,2,3,4,5,6 이 정점(Node , vertex) 이고
정점들끼리 연결하는 선을 간선(Edge, Link) 이라고 한다.
간선의 방향 유무에 따라서 단방향 그래프와 무방향 그래프(또는 양방향)로 나뉜다

가중치는 간선 위에 표시된 숫자이다. 가중치가 있는 그래프가 있고 없는 그래프가 있는데, 가중치가 없다면 모두 동일한 가중치를 가진다고 보면 된다. 해당 간선을 타고 이동할 때 필요한 비용 등을 표현하는 것에 사용된다

정점의 차수(degree)는 무방향 그래프에서 하나의 정점에 인접한 정점의 수
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선의 수의 2배이다.

위 그래프는 방향그래프를 나타낸 것인데

진입 차수(내차수)
방향 그래프에서 특정 정점에 외부로부터 오는 간선의 수
진출 차수(외차수)
방향 그래프에서 특정 정점에서 외부로 나가는 간선의 수

방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)

방향이 있는 그래프에서 정점이 서로를 가르키는 양방향성이 될 수 있다.

인접행렬

그래프를 2차원 배열로 표현한다.

인접접 행렬을 adj[][]1라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있다.

가중치가 없을 경우
adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어줄 수 있다.

노드 i에서 노드 j로 가는 간선이 있다는 말은 노드 j에서 노드 i로 가는 간선도 존재한다는 말이 된다. 따라서, 인접 행렬이 대각 성분(adj[i][j]에서 i와 j가 같은 원소들)을 기준으로 대칭인 성질을 갖게 된다.

인접행렬의 장점
노드 i와 노드 j가 연결되어 있는지 확인하고 싶을 때, adj[i][j]가 1인지 0인지만 확인하면 되기 때문에 O(1)이라는 시간 복잡도에 확인할 수 있다.

단점은 정점에 어떤 정점이 연결되어있는지 확인하고 싶을 경우에는 모든 정점을 살펴 봐야 하기 때문에 범위가 넓어 질 수록 살펴봐야될 범위가 넓어지기때문에 결국 성능저하와 직결된다.

인접 리스트

그래프를 연결리스트 (linkedList)로 표현한 방식이다.

인접리스트의 장점은
정점들의 연결 정보를 탐색할 때 O(E) 의 시간이면 가능하다. (E:간선의 개수)

인접리스트의 단점은
특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다.
간선의 존재 여부와 정점의 차수는 정점 i의 리스트에 있는 노드의 수 즉,정점 차수만큼의 시간이 필요하다.

tree

• 트리는 방향성이 있는 비순환 그래프의 한 종류이다.

• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
  즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다.

• 루트 노드는 단 한개이며 자식노드들은 모두 하나의 부모 노드를 가지고 있다.

• 트리는 이진 탐색트리 , 이진 힙 , 이진 트리 등이있다.

Binary Search Tree