[자료구조] 그래프 개념 및 구현(인접 리스트)

1. 그래프의 개념

그래프(Graph)란, 노드(N)과 노드를 연결하는 간선(E)을 하나로 모아 놓은 자료 구조이다. 

 

2. 대표적인 용어

• 정점(Vertex) : 노드의 위치
• 엣지(Edge) : 간선, 즉 노드들을 연결하는 선
• 분지, 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 사이클(Cycle) : 시작 정점과 종료 정점이 동일한 경우
• 연결 성분(Connected component) : 서로 연결되어 있는 각각의 그래프의 개수(부분 그래프의 개수)

3. 그래프 종류

• 방향 그래프 : 간선에 방향이 있는 그래프(간선에 화살표가 있으면 방향그래프)
• 무방향 그래프 : 간선에 방향이 없는 그래프
• 연결 그래프 : 두 정점 사이에 경로가 존재하는 그래프
• 완전 그래프 : 한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프

완전 그래프

• 단순 그래프 : 두 정점 사이의 연결선이 최대 한 개인 그래프
• 다중 그래프 : 두 정점 사이의 연결선 개수가 제한이 없는 그래프
• 부분 그래프 : 원래의 그래프에서 일부 정점이나 간선을 제거해서 만든 그래프

4. 그래프 구현

1) 인접 리스트

- 인접 리스트는 각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것

 

🔷 구현 방식

ⓐ 각 연결 리스트의 노드들은 인접 정점을 저장한다.

ⓑ 각 연결 리스트들은 헤더 노드를 가지고 있고, 헤더 노드들은 하나의 배열로 구성되어 있다.

ⓑ 무방향 그래프인 경우, 정점 i와 j를 연결하는 간선 (i, j)는 정점 i의 연결리스트에 인접 정점 j로서 한번 표현되고,

반대로 정점 j의 연결리스트에 i가 추가 되어 표현된다. 

* 배열에 저장되는 방식은 오름차순으로 저장됨을 가정함

 

인접 리스트 그림

 

🔷 구현

1) 인접 리스트

#include <iostream>
using namespace std;

#define MAX_VERTICES 50

//노드를 정의할 구조체
typedef struct GraphNode {
	int vertex; //정점
	struct GraphNode* link;
}GraphNode;

//노드가 저장되는 리스트를 정의할 구조체
typedef struct GraphType {
	int n; //정점의 개수
	GraphNode* adj_list[MAX_VERTICES];
}GraphType;

//그래프 초기화
void init(GraphType* g) {
	int v;
	g->n = 0;
	for (v = 0; v < MAX_VERTICES; v++) {
		g->adj_list[v] = NULL;
	}
}

//정점 삽입 연산
void insert_vertex(GraphType* g, int v) {
	if (((g->n) + 1) > MAX_VERTICES) {
		cout << "그래프 최대 정점 개수 초과!\n";
		return;
	}
	g->n++;
}

//간선 삽입 연산, v를 u의 인접 리스트에 삽입함
void insert_edge(GraphType* g, int u, int v) {
	GraphNode* node;
	//정점 u의 번호나 정점 v의 번호가 그래프 정점의 개수 이상일 때
	//그래프의 정점의 개수가 n이면 간선의 개수는 n-1이다.
	if (u >= g->n || v >= g->n) {
		cout << "그래프 정점 번호 오류!\n";
	}

	//새로운 노드 동적 생성, node에는 시작 메모리 주소가 저장
	node = (GraphNode*)malloc(sizeof(GraphNode));  
	node->vertex = v;
	node->link = g->adj_list[u]; 
	g->adj_list[u] = node;  
}

void print_adj_list(GraphType* g) {
	for (int i = 0; i < g->n; i++) {
		GraphNode* p = g->adj_list[i];
		printf("정점 %d의 인접 리스트 ", i);
		while (p != NULL) {
			printf("-> %d ", p->vertex);
			p = p->link;
		}
		printf("\n");
	}
}


int main() {
	GraphType *g;
	g = (GraphType *)malloc(sizeof(GraphType));
	init(g);

	int v_num;
	cout << "삽입할 정점의 개수를 입력하세요 : ";
	cin >> v_num;
	for (int i = 0; i < v_num; i++) {
		insert_vertex(g, i);
	}
	int e_num;
	cout << "삽입할 간선의 개수를 입력하세요 : ";
	cin >> e_num;
	for (int i = 0; i < e_num; i++) {
		int x, y;
		cout << "정점 u와 v를 입력하세요(u-v) : ";
		cin >> x >> y;
        //무방향 그래프기준 반대도 삽입함, 방향그래프면 (x, y)만
		insert_edge(g, x, y);
		insert_edge(g, y, x);
	}
	print_adj_list(g);
	free(g);
	return 0;

}

- 시간 복잡도

ⓐ 노드를 추가하는 연산 : O(1)

ⓑ 엣지를 추가하는 연산 : O(1)

 

- 공간 복잡도 : O(n(정점)+m(엣지))

 

 

ps. 다른 구현방법으로 인접 행렬이 있다.