본문으로 바로가기

자료구조 공부 #20 (그래프)

category 이론공부/자료구조 2021. 6. 8. 01:08

 

2021.05.25 - [전체글] - 자료구조 공부#19 (우선순위 큐, 힙)


 

그래프

  • 연결되어 있는 객체 간의 관계를 표현하는 자료구조
    ex) 앞서 배운 트리도 이와 비슷함, 전기회로 소자간 연결, 지도에서 도시들의 연결

깊게 말하면 그래프는 트리보다 좀더 넓은 의미를 포함하고 있다.

 

그래프 구조의 역사

 

그래프로 표현 가능한 예시

 

  • 그래프 G는 (V,E)로 표시
  • 정점(vertices)
    • 여러가지 특성을 가질 수 있는 객체
    • V(G) : 그래프 G의 장점들의 집합
    • 노드 라고도 불림
  • 간선(edge)
    • 정점들 간의 관계 의미
    • E(G): 그래프 G의 간선들의 집합
    • 링크 라고도 불림

그래프의 구조 그림

 

그래프 표현 방법

 

그래프 표현 방법 예시

그래프 종류

 

무방향 그래프

 

 

방향 그래프

 

 

네트워크(network)

  • 가중치 그래프는 네트워크 라고도 함
  • 간선에 비용, 혹은 가중치가 할당된 그래프
    • 예시
      • 정점 : 각 도시
      • 간선 : 도시 연결 도로
      • 가중치 : 도로 길이

네트워크, 가중치 그래프 예시

 

부분 그래프

  • 정점 집합 V(G)와 간선 집합 E(G)의 부분 집합으로 이루어진 그래프

서브트리 마냥 부분집합 느낌인거 같다

 

 

그래프 구조 예제 문제? 이미지

 

그래프의 경로

그래프의 연결 정도

연결 그래프, 완전 그래프 정리

완전 그래프는 모든 정점이 직접 연결되어 있는 그래프 이다.

 

 

C++ 로 그래프 연산, 구조 구현

그래프 ADT : 정점의 집합, 간선의 집합

연산:
create_graph() 그래프 생성
init(g) 그래프 초기화
insert_vertex(g,v) 그래프 g에 정점 v 삽입
insert_edge(g,u,v) 그래프 g에 간선 (u,v) 삽입
delete_vertex(g,v) 그래프 g에 정점 v 삭제
delete_edge(g,u,v) 그래프 g에 간선 (u,v) 삭제
is_empty(g) 공백 에러 확인
adjacent(v) 정점 v에 인점한 다른 정점 리스트 리턴
destroy_graph(g) 그래프 g 제거

 

  • 표현방법
    • 인접행렬 방법
    • 인접 리스트 방법

인접행렬 방법

인접 행렬로 구현

#define MAX_VERTICES 50

typedef struct GraphType {
	int n;
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;

void init(GraphType* g) {
	int r, c;
	g->n = 0;
	for (r = 0; r < MAX_VERTICES; r++){
		for (c = 0; c < MAX_VERTICES; c++){
			g->adj_mat[r][c] = 0;
		}
	}
}

void insert_vertex(GraphType* g, int v) {
	if (((g->n)+1) > MAX_VERTICES){
		fprintf(stderr, "그래프 정점 갯수 초과");
		return;

	}
	g->n++;
}

void insert_edge(GraphType* g, int start, int end) {
	if (start >= g->n || end >= g->n) {
		fprintf(stderr, "그래프 정점 번호 오류");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
}

void print_adj_mat(GraphType* g) {
	for (int i = 0; i < g->n; i++){
		for (int j = 0; j < g->n; j++) {
			printf("%2d", g->adj_mat[i][j]);
		}
		printf("\n");

	}
}


int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	for (int i = 0; i < 4; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 0, 3);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 3);

	print_adj_mat(g);

	free(g);

	return 0;
}

 

인접 리스트 방법

인접 리스트 방법

 

 


그래프 탐색

그래프 탐색 교재 내용

  • 깊이 우선 탐색 (DFS : Depth first search)
  • 너비 우선 탐색 (BFS: Breath first search)

탐색 방법 2가지

 

깊이 우선 탐색

무조건 제일 깊숙히 들어가서 갈수 없을때 올라가는 방식

 

알고리즘(순환 호출 방식이다)

 

 

 

깊이 우선 탐색의 경우 복잡도 분석 결과

  • 인접행렬 -> O(n^2)
  • 인접 리스트 -> O(n+e)

 

너비 우선 탐색

 

  • 너비 우선 탐색의 경우 복잡도 분석 결과
    • 인접행렬 -> O(n^2)
    • 인접 리스트 -> O(n+e)

탐색에 경우엔 인접 리스트 형식으로 구현하는게 시간 복잡도가 더 효율적이다