[자료구조] 그래프(Graph)

그래프란?

   - 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료 구조

  - 객체간의 관계를 표현할 수 있는 자료구조
    Ex) 지도, 지하철 최단경로, 도로

  - 트리의 상위 개념

 

그래프 관련 용어

정점 (vertex)	위치 혹은 노드라고 부른다.
간선 (Edge)	정점간의 연결 선
인접 정점(adjacent vertex)	간선에 의해 직접 연결된 정점
방향 그래프 (Directed Graph)	간선에 방향성이 있는 그래프
무방향 그래프 (Undirected Graph)	방향성이 정해져 있지 않고 양방향으로 이동 가능한 그래프
가중치 그래프 (Weighted Graph)	간선에 비용이나 가중치가 할당된 그래프
연결 그래프 (Connected Graph)	무방향 그래프에 있는 모든 정점에 대해 항상 경로가 있는 경우 ex) 트리 : 사이클을 가지지 않는 그래프
비 연결 그래프 (Disconnected Graph)	무방향 그래프에서 특정 정점 사이에 경로가 존재하지 않는 경우
완전 그래프 (Complete Graph)	그래프에 모든 정점이 서로 연결된 그래프
신장 트리 (Spanning Tree)	그래프 내의 모든 정점을 포함하는 트리 N개의 정점이 정확히 (N-1)개의 간선으로 연결
순환 (Cycle)	A 정점에서 시작하여 그래프를 순회 후 다시 시작 정점인 A정점으로 돌아오는 것
정점의 차수(Degree)	무방향 그래프에서 하나의 정점에 인접한 정점의 수
진입 차수 (in-degree)	방향 그래프에서 외부에서 오는 간선의 수
진출 차수 (out-degree)	방향 그래프에서 외부로 향하는 간선의 수
경로 길이 (path-legnth)	경로를 구성하는데 사용된 간선의 수
단순 경로 (simple path)	경로 중 반복되는 정점이 없는 경우
DFS (Deep Frist Search) / BFS (Breadth First Search)	그래프를 순회하는 방식 (알고리즘)
인접 리스트 (Adjacency List)	그래프를 배열, ArrayList, LinkedList 등을 이용해 표현하는 방식
인접 행렬 (Adjacency Matrix)	그래프를 N*N로 생성한 행렬

 

   - 어디로 가야한다는 방향성이 없다
   

 

  - 정점간에 이동하는 방향이 있다.