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

이론공부/자료구조

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

한반가 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;
}