자료구조(그래프)

🤔  그래프란?

점과 선(정점과 간선)으로 이루어진 자료구조를 의미한다.
이때 각 점인 정점(vertex)는 데이터가 저장되는 노드를 의미한다. 선인 간선(edge)는 각 정점을 연결하는 선이며 이때 이것을 링크, 브랜치라고도 한다. 그래프는 각 간선이 방향이 있는 방향그래프와 방향이 없는 무방향그래프가 있다.

 

방향그래프(Directed Graph)

정점과 이를 연결하는 간선 사이의 방향이 일련의 순서로 정해져 있는 그래프를 의미한다.

1) 각 정점은 고유한 간선을 가진다
2) 정점 사이를 잇는 간선의 방향이 향하는 곳에 따라 방향성을 가진다

vertex	edge
S,V,U,A,B	S->V, V->U, U->B, B->V, V->A, A->S

 


무방향그래프(UnDirected Graph)

정점과 이를 연결하는 간선 사이의 방향이 일련의 순서로 정해져 있는 그래프를 의미한다.

1) 각 정점은 고유한 간선을 가진다
2) 정점 사이를 잇는 간선의 방향이 향하는 곳에 따라 방향성을 가진다

vertex	edge
S,V,U,A,B	non Direct

 

🤔 그 외에도 다양한 그래프들이 있다.

1) 가중그래프 : 노드를 연결하는 각각의 간선에 가중치(숫자)가 부여된 그래프를 말한다. 이것은 한 정점에서 다른 정점으로 이동하는 이동비용을 뜻한다.
2) 양방향그래프 : 무방향 그래프와 비슷하며 방향이 지정되지 않은 간선이 두 사이의 정점에 연결된 형태를 말한다. 다만 두 정점 입장에서 가장자리는 두개이다.
3) 무한그래프 : 무한그래프의 경우 무한한 수의 노드와 모서리를 가진다. 
4) 널 그래프 : 간선이 존재하지 않고 정점만 존재하며 이때 G = (V,E)일때 널 그래프는 G = (N, null)을 의미한다.
5) 간단한 그래프 : 노드가 단 하나만 존재하는 그래프이다.
6) 멀티 그래프 : 두 정점 사이에 연결된 간선이 하나가 아닌 여러개가 존재하는 경우의 그래프를 말한다. 또한 정점이 자기 자신을 직접 가르키는 자체 루프가 있을 수도 있다.
7) 완전한 그래프 : 각 노드(정점)가 다른 노드들과 모든 간선으로 이루어진 형태의 그래프를 말한다.
8) 연결된 그래프 : 각 노드나 정점에서 시작해 시작노드에서 모든 노드를 이동할 수 있는 연결된 경우의 그래프를 말한다.
9) 순환 그래프 : 각 정점간 모든 순환이 가능한 경우의 그래프를 말한다.
10) 방향성 비순환 그래프 : 9번 순환 그래프와 다르게 각 정점 사이에서 순환이 하나라도 없을 경우 방향성 비순환 그래프라고 한다.
11) 사이클 그래프 : 순환그래프와 다르게 각 정점이 앞뒤 두개만의 연결 구조를 갖는 그래프이다. 원형 연결과 같이 각 정점은 점 기준으로 두 개의 가장자리만이 연결된 그래프이다!
12) 이분 그래프 : 각 정점이 두가지의 분류로 나눠져 쌍을 이루듯 이분하여 연결된 그래프를 말한다. 좌정점 <-> 우정점 별로 각 연결된 그래프이다.
13) 오일러 그래프 : 모든 정점이 짝수인 차수를 만족하는 경우 이때 오일러 그래프라고 할 수 있다.
14) 해밀턴 그래프 : 똑같은 정점을 재방문하거나 똑같은 간선을 다시 사용하지 않고서 주어진 모든 정점에 방문 가능한 연결 그래프이다. 이때 이것을 해밀턴 경로라고 하며 해밀턴 경로의 유무를 가지고 해밀턴 그래프인지 아닌지 확인 가능!

 

🤔 다음에는 트리를  정리!