๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๊ทธ๋ž˜ํ”„1

14-1๊ฐ•. ๊ทธ๋ž˜ํ”„(Graph) ๊ฐœ๋…๊ณผ ํ‘œํ˜„ (๋ฌด๋ฐฉํ–ฅ) ๊ทธ๋ž˜ํ”„. G = (V, E) - V : ๋…ธ๋“œ(node) ํ˜น์€ ์ •์ (vertex) - E : ๋…ธ๋“œ ์Œ์„ ์—ฐ๊ฒฐํ•˜๋Š” ์—์ง€(edge) ํ˜น์€ ๋งํฌ(link) - ๊ฐœ์ฒด(object)๋“ค ๊ฐ„์˜ ์ด์ง„๊ด€๊ณ„๋ฅผ ํ‘œํ˜„ - n = |V|, m = |E| ๋ฐฉํ–ฅ๊ทธ๋ž˜ํ”„(Directetd Graph). G=(V, E) - ์—์ง€(u, v)๋Š” u๋กœ๋ถ€ํ„ฐ v๋กœ์˜ ๋ฐฉํ–ฅ์„ ๊ฐ€์ง ๊ฐ€์ค‘์น˜ (weighted) ๊ทธ๋ž˜ํ”„ - ์—์ง€๋งˆ๋‹ค ๊ฐ€์ค‘์น˜(weight)๊ฐ€ ์ง€์ • ๊ทธ๋ž˜ํ”„์˜ ํ‘œํ˜„ - ์ธ์ ‘ํ–‰๋ ฌ (adjacency matrix) - ์ธ์ ‘๋ฆฌ์ŠคํŠธ (adjacency list) ์œ„์˜ ๊ทธ๋ฆผ์—์„œ m์€ ์—ฃ์ง€์˜ ๊ฐฏ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค.. n(:๋…ธ๋“œ์˜ ๊ฐฏ์ˆ˜) + 2m(:๋…ธ๋“œ ๊ฐฏ์ˆ˜) ์ด์–ด์„œ ์ €์žฅ๊ณต๊ฐ„์€ O(n+m)์ด๋‹ค. ๋ฐฉํ–ฅ๊ทธ๋ž˜ํ”„๋ฅผ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ• ๊ฐ€์ค‘์น˜ ๊ทธ๋ž˜ํ”„์˜ ์ธ์ ‘ํ–‰๋ ฌ ํ‘œํ˜„ .. 2020. 12. 1.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”