[자료구조] 그래프2

최단 경로 찾기(BFS)

- 경로 : 인접한 정점들의 수열

- 단순 경로 : 경로상의 정점들의 모두다른경우

- 경로의 길이 : 경로상의 간선의 개수

- 정점 V에서 W까지의 최단 경로의 길이는 V를 시작 정점으로 너비 우선 탐색(BFS)을 수행해서 W를 처음 방문할 때의 단계 수

 

최소비용신장트리(MST)

: 네트워크에 있는 모든 정점들을 가장 적은 비용으로 연결하는 신장트리 ( 도로건설, 전기 회로, 통신)

• 대표알고리즘
• 1. kriskal 알고리즘
• 2. Prim의 알고리즘

 

• 탐욕적인 방법
• ㅗㅗ
• ㅠㅠ
• ㅜㅜ
• ㅎㅎ
• ㅋㅋ