그래프의 응용

스패닝 트리

• 부속 그래프로 다음을 만족한다.
• connect가 필요하다

스패닝 트리 종류

깊이 우선 스패닝 트리

• dfs 알고리즘을 사용하여 방문되어진 에지로 만들어진 스패닝 트리

너비 우선 스패닝 트리

• bfs 알고리즘을 사용하여 방문 되어진 에지로 만들어진 스패닝 트리

최소 스패닝 트리

• 스패닝 트리에서 각 에지의 비용 값이 주어진다면 부여된 비용 값의 합을 최소로 하는 스패닝 트리를 구할 필요가 있다
  • 가중치 그래프를 생각해야 한다

코드

while(T contains less than n—l edges && E is not empty) 
choose a least cost edge (v,w) from E; 
delete (v,w) from E; 
if((v,w) does not create a cycle in T) 
/*2*/ 
add(v,w) to T ; 
else discard (v,w); 
if(T contains fewer than n—l edges) 
printf("no spanning treeWn");