Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:56:06Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:56, 26 March 2026
Line 30:		Line 30:
	* 2차원 배열로 표현합니다. 정식 이름은 Adjacency Matrix(맞나?--;)		* 2차원 배열로 표현합니다. 정식 이름은 Adjacency Matrix(맞나?--;)
	* 먼저 Undirected Graph		* 먼저 Undirected Graph
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\|		\|
Line 76:		Line 76:
	* <1,0>, <2,1>, <3,1>, <3,2>		* <1,0>, <2,1>, <3,1>, <3,2>
	* 도표로 그리자면		* 도표로 그리자면
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\|		\|
Line 113:		Line 113:
	== 리스트 ==		== 리스트 ==
	* Adjacency List(Linked List로 표현)		* Adjacency List(Linked List로 표현)
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\| 0		\| 0
Line 192:		Line 192:
	* Dijkstra's Algorithm		* Dijkstra's Algorithm
	** 표현은 인접 행렬(Adjancey(??) Matrix)로 표현(그러니까 2차원 배열)		** 표현은 인접 행렬(Adjancey(??) Matrix)로 표현(그러니까 2차원 배열)
	** ~~cost[[i~~, j]] : i -> j 로 가는 Cost		** costi, j : i -> j 로 가는 Cost
	** 초기값 : S = { V0 } V0 : Source,		** 초기값 : S = { V0 } V0 : Source,
	** 중간 S : { 지금까지 Shortest Path가 결정된 Vertex들 } : 그러니까 결정되면 S에 넣는다는 말이다.		** 중간 S : { 지금까지 Shortest Path가 결정된 Vertex들 } : 그러니까 결정되면 S에 넣는다는 말이다.
Line 198:		Line 198:
	** 예를 들자면		** 예를 들자면
	Start Vertex : 4 -> S = {4}		Start Vertex : 4 -> S = {4}
	dist[3] = 1500		dist[3] = 1500
	dist[5] = 250 3,5 는 4에 연결되어 있음		dist[5] = 250 3,5 는 4에 연결되어 있음
	dist[others] = 무한대		dist[others] = 무한대
	-> dist[5]가 가장 작다. 5를 S에 넣는다.		-> dist[5]가 가장 작다. 5를 S에 넣는다.
	...		...

Line 211:		Line 211:
	*** dist 값중에서 최소가 되는 Vertex u 찾기		*** dist 값중에서 최소가 되는 Vertex u 찾기
	*** S = S U {u}		*** S = S U {u}
	*** dist값 갱신 : dist[w] = min { dist[w], dist[u] + ~~cost[[u~~, w]] }		*** dist값 갱신 : dist[w] = min { dist[w], dist[u] + costu, w }

	== All Pairs Shortest Path ==		== All Pairs Shortest Path ==
Line 217:		Line 217:
	** 역시 표현은 2차원 배열로 한다. 그런데 이 알고리즘은 (-) Weight 도 허용한다.(그리로 가면 이득이 된다는 말이다.) 하지만 Negative Cycle은 안된다.		** 역시 표현은 2차원 배열로 한다. 그런데 이 알고리즘은 (-) Weight 도 허용한다.(그리로 가면 이득이 된다는 말이다.) 하지만 Negative Cycle은 안된다.
	** Negative Cycle? 그 사이클을 돌면 - 가 나오는길을 말한다.		** Negative Cycle? 그 사이클을 돌면 - 가 나오는길을 말한다.
	** 초기 행렬을 A(-1)[[i, j]] 로 한다. 반복할수록 괄호 안의 값을 올려준다. 이걸 n-1까지 반복한다.		** 초기 행렬을 A(-1)i, j 로 한다. 반복할수록 괄호 안의 값을 올려준다. 이걸 n-1까지 반복한다.
	** A(k)[[i, j]] 라고 하면 i에서 j로 가는 Shortest Path 의 잠정적인 값이다.단 모든 길은 0 ~ k의 vertex만을 중간에 지날수 있다.		** A(k)i, j 라고 하면 i에서 j로 가는 Shortest Path 의 잠정적인 값이다.단 모든 길은 0 ~ k의 vertex만을 중간에 지날수 있다.
	** A(k)[[i, j]] = min { A(k-1)[[i,j]], A(k-1)[[i, k]] + A(k-1)[[k, j]] }		** A(k)i, j = min { A(k-1)i,j, A(k-1)i, k + A(k-1)k, j }

	[[DataStructure]]		[[DataStructure]]

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:05Z

New page

__TOC__

오랜만의 공백을 깨고! 자료 구조 정리를 계속 하도록 하겠습니다.^^;

= 기본 개념 =
* Vertex( 점 )
* Edge( 선 )
* Directed Graph - Edge의 방향이 있는 그래프
* Undirected Graph - Edge의 방향이 없는 그래프

= 한붓 그리기 =
* 모든 Vertex의 Edge가 짝수개 일때
* Vertex의 Edge의 수가 홀수개인 것이 2개일때

= 표현 =
요런 모양의 Undirected Graph가 있다고 가정합시다.
2
/ |
0 - 1 |
| /
3
알아 볼수 있을런지..--;
V = { 0, 1, 2, 3 }
E = { (0,1), (1,3), (1,2), (2,3) }

== 배열 ==
* 2차원 배열로 표현합니다. 정식 이름은 Adjacency Matrix(맞나?--;)
* 먼저 Undirected Graph
{| class="wikitable"
|-
|
| 0
| 1
| 2
| 3
|-
| 0
| 0
| 1
| 0
| 0
|-
| 1
| 1
| 0
| 1
| 1
|-
| 2
| 0
| 1
| 0
| 1
|-
| 3
| 0
| 1
| 1
| 0
|}
* Vertex 사이에 Edge가 존재할때 그 곳의 값을 1로 셋팅
* LeftUpper -> RightLower 대각선을 기준으로 대칭

* 다음엔 Directed Graph
2
/ |
0 <- 1 |
| /
3
* .... 화살표 표현하기가 암울하군요..--; 어쨌든 < Vertex1, Vertex2 > 요런 표현을 씁니다.
* 만약에 Vertex1 -> Vertex2의 방향으로 Edge가 있다면 < Vertex1, Vertex2 > 이렇게 쓴단 말입니다.
* 화살표를 그릴수 없는 관계로 순서쌍으로 표현하면
* <1,0>, <2,1>, <3,1>, <3,2>
* 도표로 그리자면
{| class="wikitable"
|-
|
| 0
| 1
| 2
| 3
|-
| 0
| 0
| 0
| 0
| 0
|-
| 1
| 1
| 0
| 0
| 0
|-
| 2
| 0
| 1
| 0
| 0
|-
| 3
| 0
| 1
| 1
| 0
|}
* | - 방향으로 Edge가 존재할때 1로 셋팅
* LeftUpper -> RightLower 대각선을 기준으로 대칭이 아님

== 리스트 ==
* Adjacency List(Linked List로 표현)
{| class="wikitable"
|-
| 0
| ->
| 1
| X
|
|
|
|
|
|
|-
| 1
| ->
| 0
| -
| ->
| 2
| -
| ->
| 3
| X
|-
| 2
| ->
| 1
| -
| ->
| 3
| X
|
|-
| 3
| ->
| 1
| -
| ->
| 2
| X
|
|}

== 배열로 표현한 Graph와 리스트로 표현한 Graph의 비교 ==
* 두 Vertex 사이에 Edge가 있나요?
** 배열 : θ(1) - 2차원 배열의 첨자로 ar[x][y] 단번에 접근 가능! 고로 배열이 좋단 말입니다.
** 리스트 : θ(n)
* 사용하는 메모리의 양 ( n개의 Vertices, e개의 Edges )
** 배열 : θ(n^2) - n X n 개의 배열을 잡으니 당연히 n^2 --;
** 리스트 : 위의 리스트로 된 그래프 표현을 보면 Head Node의 수는 n개가 필요하고 Head Node로부터 뻗어나오는 Node의 총 수는 2*e 개가 필요하다. θ(n+e) 고로 리스트가 유리하단 말입니다.
* 한가지더 : Weighted Graph의 표현법
** 배열 : 1대신 Weight를 넣어준다.
** 리스트 : 필드를 하나 추가하자. (귀찮다)
* 결론 : 뭐가 더 낳다 꼴았다 할 그런건 없지만.. 구현의 편리성과 같은 부수적인 것을 따져볼때 배열을 애용하는게 좋을것 같단 말입니다!

= 기본 연산 =
* Traversal(탐색)
** Depth First Search(우리말로 깊이 우선 탐색) : 한우물을 쭉 파나간다는 말입니다. 가다가 막히면 빽. 스택 이용(또는 재귀). 처음으로 돌아오면 쫑난답니다.
** Breadth First Search(우리말로 너비 우선 탐색) : 첨 Vertex를 큐에 넣습니다. 뺍니다. 거기에 이어진 Vertex를 큐에 다 넣습니다. 앞에서부터 빼면서 그 노드에 연결된 Vertex를 계속 추가시켜줍니다. Queue가 비게 되면 쫑나는 거랍니다. 너비 우선 탐색을 트리에 적용시키면 그게 바로 Level Order가 되는 것이란 말이져.

= 최소 비용 신장 트리(Minimum Cost Spanning Trees) =
* Weighted Graph에 적용, 첫 Vertex에서 마지막 Vertex까지 끊어지지 않게 한번에 그린다.

* Kruskal's Algorithm
** Edge들을 Cost 순으로 Sort(작은것부터)
** Edge들을 순서에 따라 하나씩 연결한다. 연결하다가 Cycle이 생기면 그것은 잇지말고 제거한다. 다 이어지면 그만둔다.

* Prim's Algorithm
** Vertex를 하나 선택한다.
** 거기에 이어진 Edge중 가장 작은것을 선택한다.
** 그 Edge에 이어진 Vertex와 처음의 Vertex에 이어진 Edge중 가장 작은걸 선택한다.
** 이짓을 반복한다.

= Shortest Paths =

== Single Source, All Destination(하나의 시작점에서 모든 곳으로의 Shortest Path를 구할수 있단말이다) ==
* Dijkstra's Algorithm
** 표현은 인접 행렬(Adjancey(??) Matrix)로 표현(그러니까 2차원 배열)
** cost[[i, j]] : i -> j 로 가는 Cost
** 초기값 : S = { V0 } V0 : Source,
** 중간 S : { 지금까지 Shortest Path가 결정된 Vertex들 } : 그러니까 결정되면 S에 넣는다는 말이다.
** dist[w] : v0에서 출발하여 w까지의 Shortest Path의 값. 단 w를 제외하고는 S집합내에 있는 Vertex들만 거쳐야 한다.
** 예를 들자면
Start Vertex : 4 -> S = {4}
dist[3] = 1500
dist[5] = 250 3,5 는 4에 연결되어 있음
dist[others] = 무한대
-> dist[5]가 가장 작다. 5를 S에 넣는다.
...

....

반복한다.
** 이걸 알고리즘화 하면,
** for n-1 번 반복
*** dist 값중에서 최소가 되는 Vertex u 찾기
*** S = S U {u}
*** dist값 갱신 : dist[w] = min { dist[w], dist[u] + cost[[u, w]] }

== All Pairs Shortest Path ==
* Floyd - Warshall Algorithm
** 역시 표현은 2차원 배열로 한다. 그런데 이 알고리즘은 (-) Weight 도 허용한다.(그리로 가면 이득이 된다는 말이다.) 하지만 Negative Cycle은 안된다.
** Negative Cycle? 그 사이클을 돌면 - 가 나오는길을 말한다.
** 초기 행렬을 A(-1)[[i, j]] 로 한다. 반복할수록 괄호 안의 값을 올려준다. 이걸 n-1까지 반복한다.
** A(k)[[i, j]] 라고 하면 i에서 j로 가는 Shortest Path 의 잠정적인 값이다.단 모든 길은 0 ~ k의 vertex만을 중간에 지날수 있다.
** A(k)[[i, j]] = min { A(k-1)[[i,j]], A(k-1)[[i, k]] + A(k-1)[[k, j]] }

[[DataStructure]]

DataStructure/Graph - Revision history

Maintenance script: Repair batch-0001 pages from live compare

imported>Unknown at 05:23, 7 February 2021