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

data structure1

[graph] ๊ธฐ๋ณธ ๊ฐœ๋… ์ •๋ฆฌ 1. ๊ทธ๋ž˜ํ”„ G = (V, E) V(vertex) ์ •์  : ์—ฐ๊ฒฐํ•  ๊ฐ์ฒด๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๊ฒƒ E(edge) ๋ชจ์„œ๋ฆฌ : ํ•œ์Œ์˜ ์ •์ ์„ ์ด์€ ๊ฒƒ graph๋ž€? ์—ฐ๊ฒฐ๋˜์–ด์žˆ๋Š” ์›์†Œ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ํ‘œํ˜„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ ์ฆ‰, ์ •์ ๊ณผ ๊ฐ„์„ ์˜ ์ง‘ํ•ฉ 2. ๊ทธ๋ž˜ํ”„์˜ ์ข…๋ฅ˜ ์ข…๋ฅ˜ ์„ค๋ช… ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(undirected graph) ๊ฐ„์„ ์— ๋ฐฉํ–ฅ์ด ์—†๋Š” ๊ทธ๋ž˜ํ”„ ์ž„์˜์˜ ๋ชจ์„œ๋ฆฌ (x, y)∈E ์ด๋ฉด (y, x)∈E ๋ฅผ ๋งŒ์กฑํ•œ๋‹ค. ์ฆ‰, (x, y)์™€ (y, x)๋Š” ๊ฐ™์€ ๊ฐ„์„ ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(directed graph) = ๋‹ค์ด๊ทธ๋ž˜ํ”„(digraph) ๊ฐ„์„ ์— ๋ฐฉํ–ฅ์ด ์žˆ๋Š” ๊ทธ๋ž˜ํ”„ = i → j = ๋กœ ํ‘œํ˜„ ์ž„์˜์˜ ๋ชจ์„œ๋ฆฌ (x, y)∈E ์ด๋ฉด (y, x)∈E ๋ฅผ ๋งŒ์กฑํ•˜์ง€ ์•Š๋Š”๋‹ค. ์™„์ „ ๊ทธ๋ž˜ํ”„(complete graph) ํ•œ ์ •์ ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ์ •์ .. 2023. 3. 3.
728x90

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