그래프(Graph)란?
- 정점과 간선으로 이루어진 자료구조
- 객체 사이의 연결 관계를 표현할 수 있는 자료구조
e.g. 지도, 지하철 노선도- 트리도 그래프의 특수한 종류이다.
But 사이클(cycle)이 존재하지 않는 그래프
- 정점 -> 객체
- 간선 -> 정점들 간의 관계
- G = (V,E)
V(G) = 그래프 G의 정점들의 집합
E(G) = 그래프 G의 간선들의 집합- V(G) = {0,1,2,3}
E(G) = { (0,1), (0,2), (0,3), (1,2) }
무방향 그래프와 방향 그래프
- 간선이 직선으로 형성된 그래프 -> 무방향 그래프
- 간선에 화살표 방향이 있는 그래프 -> 방향 그래프
- 무방향 그래프의 간선 집합을 표시할 때는 일반적인 괄호를 사용하고, 방향 그래프의 간선 집합을 표시할 때는 화살괄호를 사용한다.
- 무방향 그래프는 집합을 표시할 때 순서가 상관이 없지만 방향 그래프는 방향에 맞는 순서로 표시해야 한다.
가중치 그래프
- 간선들에 어떠한 값이 있는 그래프
- 어느 정점까지 가는 최단거리를 구할 때 사용되는 그래프
부분 그래프
- A그래프와 B그래프가 있다고 할 때 연결된 정점의 번호와 간선들의 관계가 동일한 부분이 있는 그래프를 부분 그래프라고 한다.
정점의 차수
- 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
- 차수(degree) : 정점에 인접한 정점의 수
- 진입 차수 : 외부에서 오는 간선의 개수
- 진출 차수 : 외부로 향하는 간선의 개수
- 모든 정점의 차수를 합하면 간선 수의 2배가 된다.
경로
- 단순 경로(simple path) : 경로 중에서 반복되는 간선이 없는 경로
- 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경로
연결 그래프
- 모든 정점이 간선으로 연결된 그래프
완전 그래프
- 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프
그래프의 표현 방법
- 인접 행렬 : 2차원 배열을 사용하여 그래프를 표현
- 인접 리스트 : 연결 리스트를 사용하여 그래프를 표현
인접 행렬
- 무방향 그래프는 순서가 상관 없기에 연결되어 있는 정점의 모든 경우를 인덱스에 저장한다.
- 방향 그래프는 연결된 순서에 맞게 인덱스에 저장한다.
- 자신과의 연결이 없는 경우는 배열의 대각선은 항상 0이다.
- 정점의 차수를 알고 싶은 경우 해당 정점의 행의 값들을 모두 더하면 차수를 알 수 있다.
- 장점
- 2차원 배열에 모든 정점들의 간선 정보가 있기 때문에, 간선을 조회할 때 O(1)의 시간복잡도를 갖는다
- 정점(i)의 차수를 구할 때는 인접행렬의 i번째 행의 값을 모두 더하면 되므로 O(n)의 시간복잡도를 갖는다
- 구현이 비교적 간단하다.
- 단점
- 간선의 수와 무관하게 항상 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
- 그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O()의 시간이 소요된다.
아래 코드는 C언어로 작성된 인접행렬 정점 삽입과 간선 삽입 함수 코드이다.
#define SIZE 100
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[SIZE][SIZE]
} GraphType;
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v){
if(((g->n) + 1) > SIZE){
return;
}
g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end){
if (start >= g->n || end >= g->n){
return;
}
g->adj_mat[start][end] = 1
g->adj_mat[end][start] = 1
}인접 리스트
- 연결 리스트를 사용하여 정점과 간선을 연결한다.
- 마지막 정점이나 다른 정점과 연결되어 있지 않은 정점은 NULL값을 가진다.
- 장점
- 연결되어 있는 간선만 사용하므로 메모리 사용 측면에서 보다 효율적이다.
- 그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더 노드부터 모든 인접리스틀 탐색해야 하므로 O(n+e)의 시간이 소요된다.
- 단점
- 두 정점을 연결하는 간선을 확인하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요하다.
- 비교적 구현이 어렵다.
아래 코드는 C언어로 작성된 인접리스트 정점 삽입과 간선 삽입 함수 코드이다.
#define SIZE 100
typedef struct GraphNode {
int vertex;
struct GraphNode* link;
} GraphNode;
typedef struct GraphType {
int n; // 정점의 개수
GraphNode* adj_list[SIZE];
} GraphType;
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v){
if(((g->n) + 1) > SIZE) {
return;
}
g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int u, int v){
GraphNode* node;
if(u >= g->n || v >= g->n){
return;
}
node = (GraphNode*)malloc(sizeof(GraphNode));
node->vertex = v;
node->link = g->adj_list[u];
g->adj_list[u] = node;
}
Android Developer