그래프(Graph)는 연결되어 있는 원소간의 관계를 표현하는 자료구조이다. 나와 연관된 인간 관계를 나타내는 인맥 지도, 수도 배관에 대한 배수 시스템, 물질의 분자 구조 등은 연결 구조가 다양하기 때문에 선형 자료 구조나 트리로는 표현 할 수가 없다.
그래프는 연결할 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다. 그래프 G를 _G=(V,E)_로 정의하는데, V는 그래프에 있는 정점들의 집합을 의미하고, E는 정점을 연결하는 간선들의 집합을 의미한다.
두 정점을 연결하는 간선의 방향이 없는 그래프이다. 무방향 그래프에서 정점 _Vi_와 정점 _Vj_을 연결하는 간선을 _(Vi, Vj)_로 표현하고, _(Vi, Vj)_와 _(Vj, Vi)_는 같은 간선을 나타낸다. V(G)={A,B,C,D}, _E(G)={(A,B),(A,D),(B,C),(B,D),(C,D)}_와 같이 정점의 집합 _V(G)_와 간선의 집합 _E(G)_로 나타낼 수 있다.
방향 그래프는 다이그래프(di-graph)라고도 하는데, 간선이 있는 그래프를 의미한다. 정점 _Vi_에서 정점 _Vj_를 연결하는 간선, 즉, Vi->_Vj_를 <Vi, Vj>로 표현하고 화살표로 나타낸다. 이때 _Vi_를 꼬리(tail), _Vj_를 머리(head)라고 한다. 방향 그래프 <Vi,Vj>와 <Vj,Vi>는 서로 다른 간선이 된다.
각 정점에서 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프. 정점이 _n_개인 무방향 그래프에서는 최대 간선 수가 _n(n-1)/2_개이고, 방향 그래프에서는 두 정점에 대해서 방향이 다른 두 개의 간선을 연결할 수 있으므로 최대 간선 수는 무방향 그래프의 최대 간선 수의 배가 되어 _n(n-1)_개가 된다.
정점을 연결하는 간선에 가중치(weight)를 할당한 그래프, 또는 네트워크(network)라고 부른다.
두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을 때 두 정점 Vi와 Vj를 인접(adjacent)되어 있다고 하고, 간선 (Vi,Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 한다.
정점에 부속되어 있는 간선의 수를 차수(degree)라고 한다. 방향 그래프에서는 정점에 부속된 간선의 방향에 따라서 진입 차수(in-degree)와 진출 차수(out-degree)가 생긴다.
그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것, 즉 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트를 정점 Vi에서 정점 Vj까지의 경로(path)라고 한다. 또한 경로를 구성하는 간선의 수는 경로 길이(path length)라고 한다. 모두 다른 정점으로 구성된 경로를 단순 경로(simple path)라고 하고, 경로 A-B-C는 단순 경로지만, 경로 A-B-D-C-B-C-A는 단순 경로가 아니다. 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로를 사이클(cycle)이라고 한다.
그래프에서 두 정점 Vi에서 Vj까지의 경로가 있으면 정점 Vi와 Vj가 연결(connected)되었다고 하며, 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프, 즉 떨어져 있는 정점이 없는 그래프는 연결 그래프(connected graph)가 된다.
initGraph()
isEmpty()
insertVertex(v)
insertEdge(v,u)
deleteVertex(v)
deleteEdge(v,u)
adjacent(v)