0402_ 그래프 자료구조 이론

그래프 자료구조

비선형자료구조로 정점과 간선으로 구성되어있다.
정점은 그래프 노드라고도 하며, 간선은 노드를 연결하는 라인에 해당
그래프는 G = (V, E) 로 정의
그래프는 루트노드라는 개념이 없고, 부모/자식이라는 개념도 없다.
트리가 상하계층 관계 표현이라하면, 그래프는 네트워크 모델을 구현
ㄷ연결이 단절된 부분 그래프들의 집합이 될 수도 있따.
그래프는 지도 네이게이터, 전화망, 항로, 등등에서 쓰인다.

 

 

 

---

 

키워드

 

정점 _ 그래프의 노드
간선 노드를 연결하는선
가중치 - 한 정점에서 다른 정점으로 가는 간선의 비용, 또는 가중치
인접 정점 ) 한 노드에서 간선에 의해 직접 여결된 이웃정점
부분 그래프 ) 한 그래프의 부분 영역을 가리키는 것으로 
방향그래프 ) 간선이 방향을 가지고있는 그래프
무방향 그래프 한방향이 아닌 양방향
차수 _ 한 노드의 연결된 노드들의 노드들의 수
진입차수 방향 그래프에서 밖에서 들어오는 간선의 수
진출 자수 방향그래프에서 밖으로 나가는 가선의 수
경로 _ 간선으로 연결된 정점들을 순서대로 나열
단순경 경로상에 존재하는 모든 정점이 사로 다른 경로, 즉 정점이 중복되지 않는경로
경로의 길이 _ 경로를 구성하는데 사용된 간선의수 
순산 _ 시간 노드에서 출발해 다시 그 노드로 돌아오는 경로

 

---

 

그래프의 종류

 

정점과 간선의 구조 및 연결여부에 따라서 다양한 그래프 존재

방향 그래프 // 무방향 그래프
방향 화살표가 있는것

화살표가 없는 그래프 // 양방향으로 이동할수있는 그래프

순환그래프 / 비순환그래프

비순환그래프는 사이클이 하나도없는 그래프
순환하는 그래프

연결그래프는 연결되지 안흔ㄴ 정점이 ㅇ벗는 그래프
비연결그래프 하나도 연결이 되지 않는 그래프

가중치그래프

다중그래프
정점관계 여러 간선이있ㄴ느거

방향 비순환그래프
순환반복되는 사이클이 없어서 방향성을 거스리지 않으면서 정점을 나열하는 위상정렬이 가능하다.

 

---

 

그래프의 표현
크게 인접 리스트, 인접 행렬 방식으로 나눌수잇다.

인접 리스트 방식, 가장 일반적인 방법으로, 모든 정점에 대ㅐ해 그 정점에 인접한 이웃노드를 리스트로 표현

그래프 정점은 노드클래스로 , 그래프는 그래프 클래스로 표현

노드데이타와 인접하는 이웃 노들을 동적배열로 관리
노드 ㅡㅋㄹ래스는 이웃 노드배열이외에 가중치 그래프를  표혀나가 위해 웨이트배열 옵션을 가질수잇다.