๐Ÿ“ŠGraph

Tree๊ตฌ์กฐ์™€ ๋น„์Šทํ•˜๊ฒŒ Node์™€ edge๋กœ ๊ตฌ์„ฑ

Graph์—์„œ๋Š” node(์ •์ ) -> vertex, edge(๊ฐ„์„ ) -> arc์œผ๋กœ๋„ ์ง€์นญ

Graph๋Š” vertex๊ฐ„ ์—ฌ๋Ÿฌ ๊ฐœ์˜ edge๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค.

Tree๋Š” ์‚ฌ์‹ค Graph์˜ ํŠน์ˆ˜ํ•œ ํ˜•ํƒœ

- ํ•˜๋‚˜์˜ ๋ถ€๋ชจ ๋…ธ๋“œ์—์„œ๋ถ€ํ„ฐ ์•„๋ž˜ ๋ฐฉํ–ฅ์œผ๋กœ ๋‚ด๋ ค์˜ค๋Š” Graph. ์ฆ‰ ํŠธ๋ฆฌ๋Š” ๋ฃจํŠธ๊ฐ€ ์žˆ๊ณ , In-degree๊ฐ€ 1์ธ ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋ผ๊ณ  ๋งํ•  ์ˆ˜ ์žˆ๋‹ค.

Graph์˜ ์šฉ์–ด

  1. Vertex : ์œ„์น˜๋ผ๋Š” ๊ฐœ๋…(=Node)
  2. Edge : ์œ„์น˜ ๊ฐ„์˜ ๊ด€๊ณ„, Node๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์„ (link, branch๋ผ๊ณ ๋„ ๋ถ€๋ฅธ๋‹ค)
  3. Degree : ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„์—์„œ ํ•˜๋‚˜์˜ ์ •์ ์— ์ธ์ ‘ํ•œ ์ •์ ์˜ ์ˆ˜
    • ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„์— ์กด์žฌํ•˜๋Š” ์ •์ ์˜ ๋ชจ๋“  ์ฐจ์ˆ˜์˜ ํ•ฉ = ๊ทธ๋ž˜ํ”„์˜ ๊ฐ„์„  ์ˆ˜์˜ 2๋ฐฐ
  4. In-degree : ๋‹ค๋ฅธ Vertex์—์„œ ์˜ค๋Š” ๊ฐ„์„ ์˜ ์ˆ˜
  5. Out-degree : ๋‹ค๋ฅธ Vertex๋กœ ๊ฐ€๋Š” ๊ฐ„์„ ์˜ ์ˆ˜

Graph ํŠน์ง•

๊ทธ๋ž˜ํ”„๋Š” ๋„คํŠธ์›Œํฌ ๋ชจ๋ธ | ์ˆœํšŒ๋Š” DFS๋‚˜ BFS๋กœ ์ด๋ฃจ์–ด์ง„๋‹ค.

๋ถ€๋ชจ-์ž์‹ ๊ด€๊ณ„๋ผ๋Š” ๊ฐœ๋…์ด ์—†๋‹ค. | 2๊ฐœ ์ด์ƒ์˜ ๊ฒฝ๋กœ๊ฐ€ ๊ฐ€๋Šฅํ•˜๋‹ค.

Graph ์‚ฌ์šฉ

๋ฒ„์Šค๋…ธ์„ ๋„, ์ง€๋„, ๊ธธ์ฐพ๊ธฐ, Social Networks ๋“ฑ

Graph์˜ ์ข…๋ฅ˜

  • ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„

    • ๊ฐ„์„ ์— ๋ฐฉํ–ฅ์„ฑ์ด ์กด์žฌํ•˜๋Š” ๊ทธ๋ž˜ํ”„
    • A -> B๋กœ๋งŒ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ฐ„์„ ์€ <A, B>๋กœ ํ‘œ์‹œ // <B, A>์™€ ๋‹ค๋ฅธ ๊ฒฝ๋กœ
  • ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„

    • ๋ฐฉํ–ฅ์„ฑ์ด ์—†๋Š” ๊ทธ๋ž˜ํ”„๋กœ ๊ฐ„์„ ์„ ํ†ตํ•ด์„œ ์–‘๋ฐฉํ–ฅ์œผ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋‹ค.
    • <A, B> = <B, A> ๊ฐ™์€ ๊ฒฝ๋กœ
  • ๊ฐ€์ค‘์น˜ ๊ทธ๋ž˜ํ”„(Weighted Graph)

    • ๊ฐ„์„ ์— ๋น„์šฉ์ด๋‚˜ ๊ฐ€์ค‘์น˜๊ฐ€ ํ• ๋‹น๋œ ๊ทธ๋ž˜ํ”„
    • Network ๋ผ๊ณ ๋„ ํ•œ๋‹ค. ex) ๋„์‹œ - ๋„์‹œ์˜ ์—ฐ๊ฒฐ, ๋„๋กœ์˜ ๊ธธ์ด ๋“ฑ

      ๊ณ ์†๋„๋กœ ํ†จ๊ฒŒ์ดํŠธ๋น„์šฉ?

  • ์—ฐ๊ฒฐ/๋น„์—ฐ๊ฒฐ ๊ทธ๋ž˜ํ”„

    • ์—ฐ๊ฒฐ : ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„์— ์žˆ๋Š” ๋ชจ๋“  ์ •์ ์Œ์— ๋Œ€ํ•ด์„œ ํ•ญ์ƒ ๊ฒฝ๋กœ๊ฐ€ ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ
    • ๋น„์—ฐ๊ฒฐ : ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„์—์„œ ํŠน์ • ์ •์ ์Œ ์‚ฌ์ด์— ๊ฒฝ๋กœ๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ
  • ์ˆœํ™˜/๋น„์ˆœํ™˜ ๊ทธ๋ž˜ํ”„

    • ์ˆœํ™˜ : ๋‹จ์ˆœ ๊ฒฝ๋กœ์˜ ์‹œ์ž‘ ์ •์ ๊ณผ ์ข…๋ฃŒ ์ •์ ์ด ๋™์ผํ•œ ๊ฒฝ์šฐ

      ๋‹จ์ˆœ๊ฒฝ๋กœ : ๊ฒฝ๋กœ ์ค‘์—์„œ ๋ฐ˜๋ณต๋˜๋Š” ์ •์ ์ด ์—†๋Š” ๊ฒฝ์šฐ

    • ๋น„์ˆœํ™˜ : ์ˆœํ™˜์ด ์—†๋Š” ๊ทธ๋ž˜ํ”„
  • ์™„์ „ ๊ทธ๋ž˜ํ”„

    • ๊ทธ๋ž˜ํ”„์— ์†ํ•ด ์žˆ๋Š” ๋ชจ๋“  ์ •์ ์ด ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๊ทธ๋ž˜ํ”„

Graph์˜ ํƒ์ƒ‰

- ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ์‹œ์ž‘ํ•ด์„œ ๋‹ค์Œ ๋ถ„๊ธฐ(branch)๋กœ ๋„˜์–ด๊ฐ€๊ธฐ ์ „์— ํ•ด๋‹น ๋ถ„๊ธฐ๋ฅผ ์™„๋ฒฝํ•˜๊ฒŒ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•
- ์ฆ‰, ๋„“๊ฒŒ ํƒ์ƒ‰ํ•˜๊ธฐ ์ „์— ๊นŠ๊ฒŒ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์ด๋‹ค.
- ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ : ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธ ํ•˜๊ณ ์ž ํ•˜๋Š” ๊ฒฝ์šฐ์— ์ด ๋ฐฉ๋ฒ•์„ ์„ ํƒ(DFS๊ฐ€ BFS๋ณด๋‹ค ๊ฐ„๋‹จ)

dfs.PNG

- ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ์‹œ์ž‘ํ•ด์„œ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋ฅผ ๋จผ์ € ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•
- ๊นŠ๊ฒŒ ํƒ์ƒ‰ํ•˜๊ธฐ ์ „์— ๋„“๊ฒŒ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์ด๋‹ค.
- ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ : ๋‘ ๋…ธ๋“œ ์‚ฌ์ด์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ ํ˜น์€ ์ž„์˜์˜ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๊ณ  ์‹ถ์„ ๋•Œ
: ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์˜ ๊ฒฝ์šฐ - ๋ชจ๋“  ์นœ๊ตฌ ๊ด€๊ณ„๋ฅผ ๋‹ค ์‚ดํŽด๋ณธ๋‹ค.
: ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์˜ ๊ฒฝ์šฐ - Ash์™€ ๊ฐ€๊นŒ์šด ๊ด€๊ณ„๋ถ€ํ„ฐ ํƒ์ƒ‰

bfs.PNG

Graph์˜ Pseudo Code