[📗c언어 쉽게 풀어쓴 자료구조10] 그래프

👑 그래프의 용어와 개념

: 객체 사이의 연결관계를 표현할 수 있는 자료구조 (정점과 간선들의 유한집합)

• 정점 (Vertex,노드): 각 노드
• 간선 (edge,링크): 정점들 간의 관계
• 인접정점: 간선에 의해 직접 연결된 정점
• 차수: 무방향 그래프에서 정점에 인접한 정점의 수
• 경로: 정점의 나열 (정점 간에는 반드시 간선이 존재해야 함)
• 단순경로: 반복되는 간선이 없는 경로
• 싸이클: 단순경로에서 시작정점과 종료정점이 같은 경로

& 그래프의 종류

1. 무방향 그래프: 양방향으로 갈 수 있음 (A, B)
2. 방향 그래프: 간선에 방향성이 존재 <A, B>
3. 네트워크 (가중치 그래프): 간선에 가중치가 할당된 그래프
4. 부분 그래프: 정점의 일부와 간선의 일부로 이루어진 그래프
5. 연결 그래프: 모든 정점 쌍에 대하여 항상 경로가 존재하는 방향그래프
   (트리는 싸이클을 가지지 않는 연결 그래프임)
6. 완전 그래프: 모든 정점이 서로 연결되어 있는 그래프
   (완전 그래프의 간선의 수: n(n-1)/2)

👑 그래프의 표현 방법과 구현

1. 인접 행렬: 간선의 수가 많을 경우 적합 (밀집 그래프)

• 대각선 성분은 모두 0 (자체 간선 허용하지 않음)
• 무방향 그래프의 인접행렬: 대칭 행렬
• 정점 i의 차수: 행렬의 열이나 행의 값을 모두 더하여

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
typedef struct GraphType {
	int n;
	int adj_mat[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");
	}
}

2. 인접 리스트: 간선의 수가 별로 없을 경우 적합 (희소그래프)

#include <stdio.h>
#include <stdlib.h>
#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) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}

//간선 삽입 연산
void insert_edge(GraphType* g, int u, int v) {
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	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");
	}
}

👑 그래프의 탐색1 (깊이 우선 탐색- 스택)

1. 인접 행렬
2. 인접 리스트

👑 그래프의 탐색2 (너비 우선 탐색- 큐)

: 거리가 가까운 정점의 순서로 탐색이 진행
1. 인접행렬
2. 인접 리스트