CSC 2200 Lecture Notes - Lecture 15: Spanning Tree

28 views3 pages

27 Jun 2018

School

Department

Course

Professor

For unlimited access to Class Notes, a Class+ subscription is required.

CSC 2200 Lecture 15

Spanning Trees

Prim’s Algorithm

Spanning tree

oIs a subset of graph G, which has all the vertices covered with minimum possible

number of edges

oA spanning tree does not have cycles and it cannot be disconnected

oBy definition, we can draw a conclusion that every connected and undirected

graph G has at least one spanning tree, as it cannot be spanned to all its vertices

oSpanning tree dies not have any cycles (loops)

oRemoving one edge from the spanning tree will make the graph disconnected

The spanning tree is minimally connected

oAdding one edge to the spanning tree will create a circuit or loop

The spanning tree is maximally acyclic

Prim’s algorithm

oPrim’s algorithm to find minimum cost spanning tree uses the greedy approach

oShares a similarity with the shortest path first algorithms

find more resources at oneclass.com

Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Get access