グラフィック(Graph)とDFS、BFS

グラフィックは、オブジェクト間の接続関係を表すデータ構造です。

典型的な例:地下鉄の路線図、電気部品をグラフで表す場合は、回路が正常に動作しているかどうかを分析するために接続方法を表現する必要があります.オペレーティングシステムでは、システムの効率やインタリーブ状態にあるかどうかをグラフで分析する必要があります.
グラフで表すことができるもの:道路、迷宮、選手科目(位相合わせ)

グラフィックの定義

頂点と幹線の有限集合.頂点はノードと呼ばれ、幹線はlinkと呼ばれます.

クリーンアップ用語

頂点の数:頂点に隣接する頂点の数.

の入場車数:外部幹線からの個数.

入場回数:外線数.

例:0の入場回数->3,0の入場回数->3,0の入場回数->3

無方向図では、1つの頂点の進入回数と進入回数は同じです.(双方向)

単純パス:0->1->3->

サイクル:0->1->3->024579182

接続図:すべての頂点ペアに対して、常にパスが存在するグラフィック

非接続図:非接続図

完全図:すべての頂点が接続された図

図面内のナビゲーション

深度優先検索

ナビゲーション順序

コード

#include <stdio.h>
#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0

int visited[MAX_VERTICES];

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

void graph_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) {
		printf("그래프:정점의 개수 초과");
		return;
	}
	g->n++;
}

void delete_vertex(GraphType* g, int v)
{
	if (v >= g->n || v < 0) {
		printf("error\n");
		return;
	}
	g->n--;
}
//insert edge in undirected graph(무방향 그래프)
void insert_edge(GraphType* g, int start, int end)
{
	if (start >= g->n || end >= g->n) {
		printf("그래프 :정점 번호 오류");
	}

	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
}

void delete_edge(GraphType* g, int start, int end)
{
	if (start >= g->n || end >= g->n) {
		printf("그래프 :정점 번호 오류");
	}

	g->adj_mat[start][end] = 0;
	g->adj_mat[end][start] = 0;
}


void print_graph(GraphType* g)
{
	int r, c;
	for (r = 0;r < g->n;r++)
		for (c = 0;c < g->n;c++) {
			if (g->adj_mat[r][c])
				printf("<%d , %d>", r, c);
		}

	printf("\n");
}

void dfs_mat(GraphType* g, int v)
{
	int w;
	visited[v] = TRUE;
	printf("%d ", v);
	for (w = 0;w < g->n;w++)
		if (g->adj_mat[v][w] && !visited[w])
			dfs_mat(g, w);
}

void main()
{
	int i;
	GraphType g;
	graph_init(&g);

	for (i = 0;i < 4;i++)
		insert_vertex(&g, i);
	insert_edge(&g, 0, 1);
	//	insert_edge(&g,1,0);
	insert_edge(&g, 0, 3);
	insert_edge(&g, 1, 2);
	insert_edge(&g, 1, 3);
	insert_edge(&g, 2, 3);
	print_graph(&g);

	//dfs_mat(&g,0);
	printf("\n");
	delete_edge(&g, 0, 1);
	dfs_mat(&g, 0);
	printf("\n");

	print_graph(&g);

}

幅優先ブラウズ(Breath First Search)

ナビゲーション順序

コード

include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct { // 큐 타입
	element  queue[MAX_QUEUE_SIZE];
	int  front, rear;
} QueueType;

// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// 공백 상태 검출 함수
void queue_init(QueueType* q)
{
	q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType* q)
{
	return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType* q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 삽입 함수
void enqueue(QueueType* q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType* q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}


#define MAX_VERTICES 50
typedef struct GraphType {
	int n;	// 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];

// 그래프 초기화 
void graph_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 bfs_mat(GraphType* g, int v)
{
	int w;
	QueueType q;

	queue_init(&q);     // 큐 초기화 
	visited[v] = TRUE;          // 정점 v 방문 표시 
	printf("%d  방문 -> ", v);
	enqueue(&q, v);			// 시작 정점을 큐에 저장 
	while (!is_empty(&q)) {
		v = dequeue(&q);		// 큐에 정점 추출 
		for (w = 0; w < g->n; w++)	// 인접 정점 탐색 
			if (g->adj_mat[v][w] && !visited[w]) {
				visited[w] = TRUE;    // 방문 표시
				printf("%d 방문 -> ", w);
				enqueue(&q, w); 	// 방문한 정점을 큐에 저장
			}
	}
}

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

	printf("너비 우선 탐색\n");
	bfs_mat(g, 0);
	printf("\n");
	free(g);
	return 0;
}