Graph - 편집 역사

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

2026-01-15T15:21:35Z

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

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

Pinkgo: /* Data Structures for Graphs */

2025-11-17T09:26:01Z

Data Structures for Graphs

← 이전 판		2025년 11월 17일 (월) 09:26 판
71번째 줄:		71번째 줄:
	\|리스트		\|리스트
	\|-		\|-
	\|작은 그래프에서의 메모리 사용		\|sparse 그래프에서의 메모리 사용
	\|리스트 (m+n vs n<sup>2</sup>)		\|리스트 (m+n vs n<sup>2</sup>)
	\|-		\|-
	\|큰 그래프에서의 메모리 사용		\|dense 그래프에서의 메모리 사용
	\|행렬		\|행렬
	\|-		\|-

Pinkgo: /* 개요 */

2025-11-17T08:43:48Z

개요

← 이전 판		2025년 11월 17일 (월) 08:43 판
14번째 줄:		14번째 줄:
	어떤 정점의 degree는 그 정점에 연결된 간선(친구 관계)의 수를 의미한다. 또한 clique란 모든 정점 쌍이 직접 연결되어 있는 부분을 의미한다. 이는 경로가 존재하기만 하면 되는 connected 개념과는 대비된다. 예를 들어 아래와 같은 예시를 보자:		어떤 정점의 degree는 그 정점에 연결된 간선(친구 관계)의 수를 의미한다. 또한 clique란 모든 정점 쌍이 직접 연결되어 있는 부분을 의미한다. 이는 경로가 존재하기만 하면 되는 connected 개념과는 대비된다. 예를 들어 아래와 같은 예시를 보자:
	A-B-C-D		A-B-C-D
	~~위는 A와 D 사이에 정점이 존재하여 connected 라고 볼~~ 수 ~~있지만, A와 C, D 사이를 직접 연결하는 간선이 존재하지 않아 clique라고 볼 수는~~ 없다. 정점 A, B, C, ~~D를 모두 포함하는 clique를 만들기 위해서는 각각의 정점이 모두 직접 연결되어 있어야 한다~~.		이 그래프는 A–B–C–D로 이어진 path이므로 전체적으로는 connected이다. 그러나 모든 정점 쌍이 직접 연결되어 있지 않기 때문에 전체가 clique가 될 수 없다. 이 그래프에서 가능한 clique는 “크기가 2인 clique”들뿐이며, 그것들은 {A, B}, {B, C}, {C, D}과 같이 총 3개가 존재한다.

	이러한 그래프의 개념은 사회적 네트워크, 전자 회로, 도로망, 프로그램 컨트롤 플로우 등 다양한 분야에 적용될 수 있다.		이러한 그래프의 개념은 사회적 네트워크, 전자 회로, 도로망, 프로그램 컨트롤 플로우 등 다양한 분야에 적용될 수 있다.

Pinkgo: /* 개요 */

2025-11-17T08:39:46Z

개요

← 이전 판		2025년 11월 17일 (월) 08:39 판
11번째 줄:		11번째 줄:
	* <math>E</math>: 정점들을 잇는 간선들의 집합 (Edges set)		* <math>E</math>: 정점들을 잇는 간선들의 집합 (Edges set)
	이때 간선들의 집합 E는 <math>E=\{(u,v),(x,y)\}</math>와 같이 정점의 쌍(pair)로 이루어진 원소들의 집합이며, 각 간선 <math>(A, B)</math>는 정점 A에서 정점 B 방향으로 연결되어 있음을 의미한다.		이때 간선들의 집합 E는 <math>E=\{(u,v),(x,y)\}</math>와 같이 정점의 쌍(pair)로 이루어진 원소들의 집합이며, 각 간선 <math>(A, B)</math>는 정점 A에서 정점 B 방향으로 연결되어 있음을 의미한다.

			어떤 정점의 degree는 그 정점에 연결된 간선(친구 관계)의 수를 의미한다. 또한 clique란 모든 정점 쌍이 직접 연결되어 있는 부분을 의미한다. 이는 경로가 존재하기만 하면 되는 connected 개념과는 대비된다. 예를 들어 아래와 같은 예시를 보자:
			A-B-C-D
			위는 A와 D 사이에 정점이 존재하여 connected 라고 볼 수 있지만, A와 C, D 사이를 직접 연결하는 간선이 존재하지 않아 clique라고 볼 수는 없다. 정점 A, B, C, D를 모두 포함하는 clique를 만들기 위해서는 각각의 정점이 모두 직접 연결되어 있어야 한다.

	이러한 그래프의 개념은 사회적 네트워크, 전자 회로, 도로망, 프로그램 컨트롤 플로우 등 다양한 분야에 적용될 수 있다.		이러한 그래프의 개념은 사회적 네트워크, 전자 회로, 도로망, 프로그램 컨트롤 플로우 등 다양한 분야에 적용될 수 있다.

Pinkgo: /* Embedded vs. Topological Graphs */

2025-11-17T08:30:28Z

Embedded vs. Topological Graphs

← 이전 판		2025년 11월 17일 (월) 08:30 판
43번째 줄:		43번째 줄:
	===Embedded vs. Topological Graphs===		===Embedded vs. Topological Graphs===
	Topological 그래프는 그래프의 모양보다는 연결 구조만 중요한 그래프이다. 즉, 간선이 교차하든 구부러지든 관계없고, 단지 정점 사이의 연결 관계만을 따지는 그래프이다. 반면, embedded 그래프는 그래프의 “그림” 또는 “좌표 위치”가 중요한 그래프이다. 이에 따라 도로망, 회로망, 지리적 네트워크처럼 실제 공간에 배치되는 경우에 사용된다.		Topological 그래프는 그래프의 모양보다는 연결 구조만 중요한 그래프이다. 즉, 간선이 교차하든 구부러지든 관계없고, 단지 정점 사이의 연결 관계만을 따지는 그래프이다. 반면, embedded 그래프는 그래프의 “그림” 또는 “좌표 위치”가 중요한 그래프이다. 이에 따라 도로망, 회로망, 지리적 네트워크처럼 실제 공간에 배치되는 경우에 사용된다.

			===Connected/Strongly Connected Graphs===
			그래프의 어떤 두 정점 사이에도 경로(path)가 존재한다면 그 그래프는 연결되어 있다고 한다. 이때 "connected"라는 말은 "간선 방향을 무시하면(undirected로 바꾸면) 연결되어 있다"는 것을 뜻한다. 따라서 화살표 방향은 신경 안 쓰고, 단순히 서로 닿을 수만 있으면 connected라고 할 수 있다.

			Directed 그래프에 대해서는 모든 정점 쌍 u,v에 대해 u→v, v→u 두 방향 경로가 모두 존재하는 경우 이를 strongly connected 그래프라고 한다. 이때 정의에 의해서 strongly connected 그래프는 반드시 cycle을 포함한다.

	==Data Structures for Graphs==		==Data Structures for Graphs==

Pinkgo: /* 개요 */

2025-11-17T08:22:56Z

개요

← 이전 판		2025년 11월 17일 (월) 08:22 판
10번째 줄:		10번째 줄:
	* <math>V</math>: 그래프를 구성하는 정점들의 집합 (Vertices set)		* <math>V</math>: 그래프를 구성하는 정점들의 집합 (Vertices set)
	* <math>E</math>: 정점들을 잇는 간선들의 집합 (Edges set)		* <math>E</math>: 정점들을 잇는 간선들의 집합 (Edges set)
	이때 간선들의 집합 E는 <math>E=\{(u,v),(x,y)\}</math>와 같이 정점의 쌍(pair)로 이루어진 원소들의 집합이며, 각 간선 <math>(A, B)</math>는 정점 A에서 정점 B 방향으로 연결되어 있음을 의미한다.		이때 간선들의 집합 E는 <math>E=\{(u,v),(x,y)\}</math>와 같이 정점의 쌍(pair)로 이루어진 원소들의 집합이며, 각 간선 <math>(A, B)</math>는 정점 A에서 정점 B 방향으로 연결되어 있음을 의미한다.

	이러한 그래프의 개념은 사회적 네트워크, 전자 회로, 도로망, 프로그램 컨트롤 플로우 등 다양한 분야에 적용될 수 있다.		이러한 그래프의 개념은 사회적 네트워크, 전자 회로, 도로망, 프로그램 컨트롤 플로우 등 다양한 분야에 적용될 수 있다.

Pinkgo: /* 각주 */

2025-10-17T02:37:38Z

각주

← 이전 판		2025년 10월 17일 (금) 02:37 판
156번째 줄:		156번째 줄:
	# 해당 정점의 모든 간선을 검사한 뒤에는 “processed” 상태로 바꾼다.		# 해당 정점의 모든 간선을 검사한 뒤에는 “processed” 상태로 바꾼다.
	# to-do list 가 빌 때까지 계속 반복한다.		# to-do list 가 빌 때까지 계속 반복한다.

			==[[Minimum Spanning Trees]]==
			자세한 내용은 [[Minimum Spanning Trees]] 문서를 참조하십시오.

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

Pinkgo: /* Graph Traversal */

2025-10-16T05:07:18Z

Graph Traversal

← 이전 판		2025년 10월 16일 (목) 05:07 판
138번째 줄:		138번째 줄:

	==Graph Traversal==		==Graph Traversal==
	그래프 탐색(Graph Traversal)은 그래프에 있는 모든 정점과 간선을 체계적으로 방문하는 과정을 의미한다. 이를 위해 쓰이는 주요한 알고리즘은 [[DFS\|DFS(Depth-First Search, 깊이 우선 탐색)]]와 [[~~BSF~~\|BFS(Breadth-First Search, 너비 우선 탐색)]]이다.		그래프 탐색(Graph Traversal)은 그래프에 있는 모든 정점과 간선을 체계적으로 방문하는 과정을 의미한다. 이를 위해 쓰이는 주요한 알고리즘은 [[DFS\|DFS(Depth-First Search, 깊이 우선 탐색)]]와 [[BFS\|BFS(Breadth-First Search, 너비 우선 탐색)]]이다.

	[[~~BSF~~]]에 대한 자세한 내용은 해당 문서를 참조하십시오.<br>		[[BFS]]에 대한 자세한 내용은 해당 문서를 참조하십시오.<br>
	[[~~DSF~~]]에 대한 자세한 내용은 해당 문서를 참조하십시오.		[[DFS]]에 대한 자세한 내용은 해당 문서를 참조하십시오.

	그래프 탐색에서 중요한 것은 효율성(Efficiency)과 정확성(Correctness)이다. 먼저 효율성이란 각 간선(edge)을 최대 한 번 또는 두 번까지만 방문해야 한다는 것이다. 만약 방문을 여러 번 반복하면 시간 낭비가 생기고, 알고리즘이 비효율적이다. 또한 정확성이란 체계적(systematic) 으로 탐색을 하여 “방문하지 않은 정점이 남지 않게” 하는 것이다. 이를 위해서 미로 탐색(maze)과 마찬가지로, 한 번 간 길은 표시해두고, 어디까지 갔는지 기록해야 한다.		그래프 탐색에서 중요한 것은 효율성(Efficiency)과 정확성(Correctness)이다. 먼저 효율성이란 각 간선(edge)을 최대 한 번 또는 두 번까지만 방문해야 한다는 것이다. 만약 방문을 여러 번 반복하면 시간 낭비가 생기고, 알고리즘이 비효율적이다. 또한 정확성이란 체계적(systematic) 으로 탐색을 하여 “방문하지 않은 정점이 남지 않게” 하는 것이다. 이를 위해서 미로 탐색(maze)과 마찬가지로, 한 번 간 길은 표시해두고, 어디까지 갔는지 기록해야 한다.

Pinkgo: /* Graph Traversal */

2025-10-05T20:43:45Z

Graph Traversal

@@ 142번째 줄: / 142번째 줄: @@
 [[BSF]]에 대한 자세한 내용은 해당 문서를 참조하십시오.<br>
 [[DSF]]에 대한 자세한 내용은 해당 문서를 참조하십시오.
 ==각주==

2025년 10월 5일 (일) 20:37에 Pinkgo님의 편집

2025-10-05T20:37:52Z

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

	==개요==		==개요==
			[[파일:Figure 1. Directed Graph.png\|섬네일\|200x200픽셀\|Figure 1. Directed Graph]]
	그래프는 알고리즘, 네트워크, 데이터 구조 등 컴퓨터 과학의 여러 분야에서 핵심적인 개념이다. 그래프의 정의를 수학적으로 표현하면 아래와 같다:		그래프는 알고리즘, 네트워크, 데이터 구조 등 컴퓨터 과학의 여러 분야에서 핵심적인 개념이다. 그래프의 정의를 수학적으로 표현하면 아래와 같다:
	A graph <math>G=(V,E)</math> is defined by a set of vertices <math>V</math>, and a set of edges <math>E</math> consisting of ordered or unordered pairs of vertices from <math>V</math>.		A graph <math>G=(V,E)</math> is defined by a set of vertices <math>V</math>, and a set of edges <math>E</math> consisting of ordered or unordered pairs of vertices from <math>V</math>.
22번째 줄:		23번째 줄:

	===Weighted vs. Unweighted Graphs===		===Weighted vs. Unweighted Graphs===
	가중치(Weighted) 그래프는 각 간선(혹은 정점)에 가중치(weight)를 부여하는 그래프이다. 가중치는 거리, 비용, 시간, 용량 등 수량적인 값이다. Figure 의 경우, 각 간선마다 있는 숫자들은 각 경로의 “비용”을 나타낸다. 이는 실제 도로 등에서 거리, 운전 시간, 정체 등을 나타내는 데 사용된다. 또한 가중치가 있으면 Dijkstra, Bellman-Ford 등의 알고리즘을 사용할 수 있다.		[[파일:Figure 2. Weighted Graph.png\|섬네일\|200x200픽셀\|Figure 2. Weighted Graph]]
			가중치(Weighted) 그래프는 각 간선(혹은 정점)에 가중치(weight)를 부여하는 그래프이다. 가중치는 거리, 비용, 시간, 용량 등 수량적인 값이다. Figure 2의 경우, 각 간선마다 있는 숫자들은 각 경로의 “비용”을 나타낸다. 이는 실제 도로 등에서 거리, 운전 시간, 정체 등을 나타내는 데 사용된다. 또한 가중치가 있으면 Dijkstra, Bellman-Ford 등의 알고리즘을 사용할 수 있다.

	반면 가중치가 있지 않은 그래프를 비가중치 그래프(unweighted)라고 하며, 해당 그래프에서는 모든 간선이 동일한 ‘비용’을 가지므로 단순히 “연결 여부”만 중요하다. 이런 그래프에서는 BFS 알고리즘 등을 활용할 수 있다.		반면 가중치가 있지 않은 그래프를 비가중치 그래프(unweighted)라고 하며, 해당 그래프에서는 모든 간선이 동일한 ‘비용’을 가지므로 단순히 “연결 여부”만 중요하다. 이런 그래프에서는 BFS 알고리즘 등을 활용할 수 있다.

	===Simple vs. Non-simple Graphs===		===Simple vs. Non-simple Graphs===
	간선에는 self-loop와 multi-edge와 같은 특수한 간선들이 존재한다. Self-loop란 <math>(A,A)</math>와 같이 자기 자신으로 향하는 간선을 의미한다. 또한 multi-edge란 동일한 정점 쌍 사이에 여러 간선들이 존재하는 것을 의미한다. Figure 에서 자기 자신으로 연결된 붉은 고리는 self-loop에 해당하고, 두 정점 사이의 여러 선은 multi-edge에 해당한다.		[[파일:Figure 3. Non-simple Graph.png\|섬네일\|200x200픽셀\|Figure 3. Non-simple Graph]]
			간선에는 self-loop와 multi-edge와 같은 특수한 간선들이 존재한다. Self-loop란 <math>(A,A)</math>와 같이 자기 자신으로 향하는 간선을 의미한다. 또한 multi-edge란 동일한 정점 쌍 사이에 여러 간선들이 존재하는 것을 의미한다. Figure 3에서 자기 자신으로 연결된 붉은 고리는 self-loop에 해당하고, 두 정점 사이의 여러 선은 multi-edge에 해당한다.

	이때 simple 그래프란 self-loop와 multi-edge가 없는 그래프이다. 반면 Non-simple 그래프란 둘 중 하나라도 포함하는 그래프를 의미한다.		이때 simple 그래프란 self-loop와 multi-edge가 없는 그래프이다. 반면 Non-simple 그래프란 둘 중 하나라도 포함하는 그래프를 의미한다.
35번째 줄:		38번째 줄:

	===Cyclic vs. Acyclic Graphs===		===Cyclic vs. Acyclic Graphs===
	그래프에서 사이클(cycle)이란, 같은 정점으로 되돌아오는 경로가 존재하는 경우를 의미한다. 이때 사이클이 존재하는 그래프는 cyclic 그래프라고 하며, 반면 사이클이 존재하지 않는 그래프는 acyclic 그래프라고 한다. 예를 들어 트리(Tree) 자료구조는 connected acyclic undirected 그래프이다. 또한 Figure 는 directed acyclic 그래프인데, 이러한 그래프를 DAG라고 한다.		[[파일:Figure 4. Acyclic Graph.png\|섬네일\|200x200픽셀\|Figure 4. Acyclic Graph]]
			그래프에서 사이클(cycle)이란, 같은 정점으로 되돌아오는 경로가 존재하는 경우를 의미한다. 이때 사이클이 존재하는 그래프는 cyclic 그래프라고 하며, 반면 사이클이 존재하지 않는 그래프는 acyclic 그래프라고 한다. 예를 들어 트리(Tree) 자료구조는 connected acyclic undirected 그래프이다. 또한 Figure 4는 directed acyclic 그래프인데, 이러한 그래프를 DAG라고 한다.

	===Embedded vs. Topological Graphs===		===Embedded vs. Topological Graphs===