그래프 이론

컴퓨터/알고리즘

한진희 2023. 6. 29. 04:03

Graph란?

- 구성요소: Vertex, Edge

- 지도상에서 각각의 도시를 Vertex(점)라고 가정함

- 각각의 도시와 도시를 연결하는 고속도로(edge)를 그려줌

- cyclical (bi-directional) or acyclical (one-directional)

- Edge에 비용이 있음 (고속도로 Toll비용의 개념)

- 수용 능력 (고속도로에 자동차를 몇대까지만 수용할 수 있는 능력, 예: 20 cars per minute)

- 그래프 중 하나의 개념임

- Root node가 있기떄문에 시작점이 명확함

- Edge가 일반적으로 아래, 단방향으로 뻗어나감 (directed acyclical)

- Leaf node: 아래로 뻗어나갈게 없는 node

- Often Balanced Nodes (무조건 그렇지는 않음)

- Often sorted in a specific order (무조건 그렇지는 않음)