1.) 정의: 정점(vertex)와 간선(edge)으로 구성되며, 사이클을 형성할 수 있는 데이터구조
2.) 용어: adjancy : 그래프에서 2개의 정점이 간선으로 연결
path : 한 정점에서 임의의 정점에 이르는 경로를 의미
length :각 간선의 값을 의미하며, 전체경로의 값을 의미
loop : 정점 자기 자신의 경로이며, 1의 값을 가진다
cycle : 한 정점에서 시작하여 임의 정점을 지나 시작정점으로 오는 경로가 존재
distance : 최단경로의 길이
degree : in-degree - 진입 차수 out-degree - 진출 차수
3.) 종류: Undirected Graph (무방향 그래프)
directed Graph (방향 그래프)
multiple graph (다중 그래프)
sub graph (서브 그래프)
regular graph (정규 그래프) : 모든 정점의 차수가 동일한 그래프
complete graph (완전 그래프): 무방향 그래프에서 간선의 수가 2분의 n(n-1)
isomorphic graph 2개의 그래프가 정점의 수, 간선의 수, 차수의 수가 동일
hamilton graph 한정점에서 시작하여 모든 정점을 2번이상 지나지 않고 사이클을 형성하는 그래프
euler graph 모든 정점의 차수가 짝수인 그래프
4.) 표현
1. Adjency matrix (인접행렬) : n개의 정점으로 구성된 그래프 G를 2차원 배열로 나타내고, 임의의 점점 v1에서 vj가 인접하면 1, 그렇지 않은 경우 0 으로 표시하는 방법
2. Adjency list : 인접 행렬을 n개의 링크드 리스트로 표현하는 방법으로 한정적인 1개의 링크를 가진 노드로 표현
3. adjency multiple list: 중복되는 간선을 고유한 노드에 저장하여 여러 리스트로 하여금 공유하는 방법5.) 운행(순회)
1. Depth First Search
dfs방식은 인접리스트로 그래프를 표현한 다음 각 정점을 방문
algorithm : 1. 시작정점 v를 결정하고 방문한다
2. v 에 인접한 정점 가운데 방문되지 않은 정점을 방문한다
3. 모든 인접한 정점을 방문하게 되면 방문되지 않은 인접한 정점을 방문한다
4. 방문되지 않은 정점이 없을때까지 못을 반복한다
- Breadth First Search
인접 행렬과 큐를 이용하여 구현
algorithm : 1. 시작정점 v를 결정하고 방문한다
2. v에 인접한 정점을 큐에 저장하고 큐의 내용을 출력하면서, 인접한 정점이 없을때까지 2.를 수행한다
3. 큐가 언더 플로우 될때까지 2를 반복한다.
6.) Spanning tree:
신장 트리
그래프 G의 모든 정점을 포함한트리
7.) Shortest Path
한 정점에서 다른 암의 정점에 가는 최단 경로를 구하는 방법