graph는 트리와 구성요소가 같지만, 사이클을 이루는 자료구조이다.
그래프에는 두가지 종류가 있는데, undirected graph와 directed graph가 있다.
undirected graph는 방향성이 없는 그래프이고, directed graph는 방향성이 있는 그래프를 말한다.
completed graph는 모든 node(vertex)들이 연결되어 있는 그래프를 뜻한다.
따라서 completed graph의 edge, 간선의 최대 개수는 undirected의 경우에는 방향이 없으므로 노드개수가 n이라고 하였을때에, n(n-1)/2로 나타낼수 있다. 방향이 있는 경우에는 최대 개수가 n(n-1)이다.
표현 같은 경우에는 아래와 같이 나타낸다.
multi graph : 두 꼭짓점 사이에 여러 간선이 허용되는 경우를 말한다.
adjacent 는 인접한 노드 관계를 나타내는 말이다.
incident는 노드 사이의 사건, 간선을 뜻한다.
subgraph는 그래프에 속하는, 부분집합 같은 느낌의 그래프이다.
Path는 경로로, path의 길이는 edge의 개수와 같다.
simple path의 경우는 처음의 vertex와 last vertex가 다르고, cycle의 경우는 두개가 서로 같다.
strongly connected graph는 undirected 일때에, 서로 물고 물리는 관계에 있을때를 뜻한다.
graph 에서의 degree 는 간선의 수인데, indegree 와 out degree가 있다.
indegree는 자신의 노드에 들어오는 간선의 개수를 뜻한다.
outdegree는 자신의 노드에서 나가는 간선의 개수를 뜻한다.
directed graph 를 digraph라고 한다.
그래프들의 관계를 2차원 배열로 나타내는데, 이를 인접행렬이라고 한다. (adjacenct matrix)
adjlist 는 outdegree를 기준으로 리스트를 구현한것이고, inverse adjlist 같은 경우에는 indegree를 기준으로 list를 작성한 것이다.
orthogonal graph는 인접행렬을 기준으로 1인 곳에 노드를 생성하고 연결한 것이다.
위와 같이 나타난다.
graph bfs, dfs