BFS - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:19:15Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:19 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Graph#Graph Traversal\|Graph]]		상위 문서: [[Graph#Graph Traversal\|Graph]]

2025년 10월 16일 (목) 05:09에 Pinkgo님의 편집

2025-10-16T05:09:55Z

← 이전 판		2025년 10월 16일 (목) 05:09 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[Graph]]		상위 문서: [[Graph#Graph Traversal\|Graph]]

	==개요==		==개요==

2025년 10월 16일 (목) 05:09에 Pinkgo님의 편집

2025-10-16T05:09:27Z

← 이전 판		2025년 10월 16일 (목) 05:09 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[Graph~~\|알고리즘 설계와 분석~~]]		상위 문서: [[Graph]]

	==개요==		==개요==

Pinkgo: Pinkgo님이 BSF 문서를 BFS 문서로 이동했습니다

2025-10-16T05:08:31Z

Pinkgo님이 BSF 문서를 BFS 문서로 이동했습니다

← 이전 판	2025년 10월 16일 (목) 05:08 판
(차이 없음)

Pinkgo: /* Finding Paths */

2025-10-16T04:16:30Z

Finding Paths

← 이전 판		2025년 10월 16일 (목) 04:16 판
83번째 줄:		83번째 줄:
	* 모든 parent 화살표를 모으면, 시작 정점을 루트 노드로 하는 “발견 트리(discovery tree)”가 생김		* 모든 parent 화살표를 모으면, 시작 정점을 루트 노드로 하는 “발견 트리(discovery tree)”가 생김
	** 이 트리는 탐색 순서를 보존함. 즉, 어떤 정점이 어떤 정점을 통해 처음 도달되었는지를 담고 있어, 경로 복원 등에 사용됨.		** 이 트리는 탐색 순서를 보존함. 즉, 어떤 정점이 어떤 정점을 통해 처음 도달되었는지를 담고 있어, 경로 복원 등에 사용됨.
	아래는 parent[]를 이용해 끝점에서 시작점으로 거꾸로 ~~따라가면~~ 경로를 복원하는 함수이다:		아래는 parent[]를 이용해 끝점에서 시작점으로 거꾸로 따라가면서 경로를 복원하는 함수이다:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	void find_path(int start, int end, int parents[]) {		void find_path(int start, int end, int parents[]) {
93번째 줄:		93번째 줄:
	}		}
	}		}
	</syntaxhighlight>		</syntaxhighlight>

	===Shortest Paths and BFS===		===Shortest Paths and BFS===

Pinkgo: /* Implementing BFS */

2025-10-16T03:27:53Z

Implementing BFS

← 이전 판		2025년 10월 16일 (목) 03:27 판
20번째 줄:		20번째 줄:
	또한 BFS는 FIFO queue를 이용하므로, 먼저 발견된 노드를 먼저 처리해야 “너비 우선” 순서가 유지된다. 이때 새로운 정점이 발견되면 discovered[y] = true로 표시하고 큐에 추가한다. 즉, queue는 처리할 정점들이 저장되는 to-do list와 같은 존재이다.		또한 BFS는 FIFO queue를 이용하므로, 먼저 발견된 노드를 먼저 처리해야 “너비 우선” 순서가 유지된다. 이때 새로운 정점이 발견되면 discovered[y] = true로 표시하고 큐에 추가한다. 즉, queue는 처리할 정점들이 저장되는 to-do list와 같은 존재이다.

	===~~Initializing~~ BFS===		===BFS Code===
	아래는 탐색을 시작하기 전에 배열을 초기화하는 함수이다.		아래는 탐색을 시작하기 전에 배열을 초기화하는 함수이다.
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
96번째 줄:		96번째 줄:

	===Shortest Paths and BFS===		===Shortest Paths and BFS===
	BFS는 간선 가중치가 모두 동일할 때, 시작 정점으로부터의 최단(간선 수 최소) 경로를 자동으로 보장한다. 이는 BFS가 레이어 순서대로 확장하기 때문이다. 거리 0(시작) → 거리 1 → 거리 2 → … 순서로 큐에서 꺼내 처리하기 때문에, 발견 트리에서 루트 내의 임의의 정점 x 로 내려가는 유일한 트리 경로는, 가능한 경로 중 간선 수가 최소이다. 이는 figure에서 알 수 있듯이 어떤 그래프가 주어졌을 때 parent[] 배열을 이용하여 발견 트리를 구성할 수 있으며, 이때 발견 트리의 어떤 정점에 대한 깊이는 루트에서의 해당 정점까지의 경로의 길이에 비례하기 때문이다.		BFS는 간선 가중치가 모두 동일할 때, 시작 정점으로부터의 최단(간선 수 최소) 경로를 자동으로 보장한다. 이는 BFS가 레이어 순서대로 확장하기 때문이다. 거리 0(시작) → 거리 1 → 거리 2 → … 순서로 큐에서 꺼내 처리하기 때문에, 발견 트리에서 루트 내의 임의의 정점 x 로 내려가는 유일한 트리 경로는, 가능한 경로 중 간선 수가 최소이다. 이는 figure에서 알 수 있듯이 어떤 그래프가 주어졌을 때 parent[] 배열을 이용하여 발견 트리를 구성할 수 있으며, 이때 발견 트리의 어떤 정점에 대한 깊이는 루트에서의 해당 정점까지의 경로의 길이에 비례하기 때문이다.

	==Applications of BFS==		==Applications of BFS==

Pinkgo: /* Initializing BFS */

2025-10-05T22:03:49Z

Initializing BFS

@@ 65번째 줄: / 65번째 줄: @@
 </syntaxhighlight>
+===Finding Paths===
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">

Pinkgo: /* 개요 */

2025-10-05T21:21:11Z

개요

← 이전 판		2025년 10월 5일 (일) 21:21 판
4번째 줄:		4번째 줄:

	==개요==		==개요==
			BFS(Breadth-First Traversal) 알고리즘의 핵심은 그래프를 체계적으로(순서 있게) 탐색하는 것이다. BFS는 모든 vertex와 edge를 한 번씩 방문한다. 이는 아래와 같은 규칙을 따른다.
			* “Breadth-First”는 탐색 시 가까운 노드(이웃)를 먼저 방문하고, 그 후에 더 멀리 있는 노드를 탐색하는 방식이다.
			** 예를 들어, 루트 노드로부터 거리 1인 정점들을 모두 방문한 뒤, 그 다음으로 거리가 2인 정점, 3인 정점...을 방문하는 방식이다.
			* BFS는 queue(큐)를 이용해 이 순서를 보장한다.
			이에 따라 BFS는 특히 unweighted 그래프에서 최단 경로(shortest path)를 찾는 데 적합하다. 이는 DFS(깊이 우선 탐색)와 달리, BFS는 각 vertex까지의 최단 거리(간선 개수 기준)를 자연스럽게 구할 수 있기 때문이다.

			==Implementing BFS==
			===Data Structures for BFS===
			BFS를 구현하기 위해 필요한 자료구조는 3가지이다:
			<syntaxhighlight lang="c">
			bool processed[MAXV+1]; // 이미 완전히 처리된 정점
			bool discovered[MAXV+1]; // 방문은 했지만 아직 다 보지 않은 정점
			int parent[MAXV+1]; // 해당 정점을 방문하기 전의 부모 노드
			</syntaxhighlight>
			또한 BFS는 FIFO queue를 이용하므로, 먼저 발견된 노드를 먼저 처리해야 “너비 우선” 순서가 유지된다. 이때 새로운 정점이 발견되면 discovered[y] = true로 표시하고 큐에 추가한다. 즉, queue는 처리할 정점들이 저장되는 to-do list와 같은 존재이다.

			===Initializing BFS===
			아래는 탐색을 시작하기 전에 배열을 초기화하는 함수이다.
			<syntaxhighlight lang="c">
			void bfs(graph *g, int start) {
			queue q; /* 방문할 정점들을 담는 큐 */
			int v; /* 현재 방문 중인 정점 */
			int y; /* 인접(후속) 정점 */
			edgenode p; / 인접 리스트를 순회하기 위한 포인터 */

			/* 초기화 단계 */
			init_queue(&q); // 큐 초기화
			enqueue(&q, start); // 시작 정점을 큐에 넣기
			discovered[start] = true; // 시작 정점을 "발견됨"으로 표시

			/* BFS 메인 루프 */
			while (!empty_queue(&q)) {
			v = dequeue(&q); // 큐에서 정점을 하나 꺼냄
			process_vertex_early(v); // 방문 직후 처리 (예: 출력)
			processed[v] = true; // 완전히 처리된 정점으로 표시

			/* 인접 정점 순회 */
			p = g->edges[v]; // v의 인접 리스트의 첫 노드
			while (p != NULL) {
			y = p->y; // 인접 정점 번호

			/* 간선 (v, y) 처리 */
			if ((!processed[y]) \|\| g->directed) {
			process_edge(v, y); // 간선 처리 (예: 출력, 트리 생성 등)
			}

			/* 새로운 정점 발견 시 */
			if (!discovered[y]) {
			enqueue(&q, y); // 큐에 추가
			discovered[y] = true; // 발견됨 표시
			parent[y] = v; // BFS 트리 상의 부모 설정
			}

			p = p->next; // 다음 인접 정점으로 이동
			}

			process_vertex_late(v); // 정점 처리 완료 후 작업
			}
			}
			</syntaxhighlight>



			<syntaxhighlight lang="c">
			</syntaxhighlight>
			<syntaxhighlight lang="c">
			</syntaxhighlight>
			<syntaxhighlight lang="c">
			</syntaxhighlight>
			<syntaxhighlight lang="c">
			</syntaxhighlight>
			<syntaxhighlight lang="c">
			</syntaxhighlight>
			<syntaxhighlight lang="c">
			</syntaxhighlight>

	==각주==		==각주==

Pinkgo: 새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== ==각주==

2025-10-05T20:32:17Z

새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== ==각주==

새 문서

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[Graph|알고리즘 설계와 분석]]

==개요==

==각주==