MST_알고리즘

The Greedy Approach

• Steps in Greedy algorithm:
  • Greedy algorithm starts with an empty set and adds items to the set in sequence until the set represents a solution to an instance of a problem.
  1. Selection procedure
     • Choose the next “best” item according to some criterion and add it to the set
  2. Feasibility check
     • Determine if the new set is feasible by checking wheter it is possibile to complete this set in such a way as sto give a solution to the instance.
     • If it is feasible, then go to next step.
     • Otherewise, discard the chosen item at step (1) from the set. Go to step(1)
  3. Soltution check 6 Determines whether the new set consitutes a solution to the instance.

Minimum Spanning Trees(MST)

• Undirected graph G = (V,E)
  • V : Set of Vertices
  • E : Set of Edges
    Udiretede : 방향성을 가지고 있지않다 도로로 따지면 양방통행
    Directed : 방향성을 가지고 있다 도로로 따지면 일방통행
    Edges : Vertices를 연결해주는 선! 도로로 따지자면 서울에서 춘천까지 고속도로! Weigh : 각 Edges마다 의미를 부여한 가중치 서울에서 춘천까지 고속도로가 있다면 거리가 Weigh이며 없는경우도 있다.
• Example
  • V = {v1,v2,v3,v4,v5}
  • E = {(v1,v2), (v1,v3), (v2,v3), (v2,v4),(v2,v5) (v3,v4), (v4,v5)}
• Subgraph

  • Subgraph G’ =(V’,E’) of a graph G =(V,E)

    1. V’는 V의 부분집합이다.
    2. E’는 V’의 원소이다.
       원래 없던 V’,E’ 이 만들어질 수 없다. 즉 기존에 있던 graph이외에 새로운 V,E는 만들어질 수 없다.
       
• Terms
  • Path : Vetices1에서 Vetices2까지 Edges를 따라 갈 수있는 경로 특별한 경우를 제외하고는 갔던 Vertices도 다시 갈 수 있다.
  • An undirected graph is connected if there is a path between every pait of vertices
  • 어떤 쌍 2개를 잡더라도 V에서 V까지의 경로가 있다면 Connected graph라고 한다.
  • Cycle : 어떤 V출발에서 다시 자기 자신으로 돌아오는 경로가 있다면 Cycle이 있다고 한다.
  • Tree : Tree is an acyclic, connected, undirected graph
• A Spanning tree for a graph G
  • A connected subgraph of G that
    • contains all the vertices of G
    • is a tree 어떤 그래프에 연결된 서브그래프이며 원래 그래프에 모든 Vertices 다 가지고 있으며 Tree 구조여야한다.
• Minimum spanning tree of G
  • A spanning tree of G that has the minimum sum of weights. 가중치 를 다 합쳤을 때 합이 최소 가 되는 S_그래프

• 알고리즘
• mst
• greedy