Matrices & MST Algorithms

chris cambré, Conor Desmond, Oct 2, 2018

Perform arithmetic operations on matrices by hand. Introduction to minimal spanning trees and algorithms associated with finding these.

Table of Contents

  1. Matrix Multiplication
    1. Matrix Multiplication Animated Example
  2. Prim's Algorithm
    1. Minimal spanning tree
    2. Prim's algorithm
    3. Exercise 1
    4. Exercise 2
    5. Exercise 3
  3. Kruskal's Algorithm
    1. Kruskal's algorithm

1.

Matrix Multiplication

  • 1. Matrix Multiplication Animated Example

1.1.

Matrix Multiplication Animated Example

– Norm Prokup

2.

Prim's Algorithm

  • 1. Minimal spanning tree
  • 2. Prim's algorithm
  • 3. Exercise 1
  • 4. Exercise 2
  • 5. Exercise 3

2.1.

Minimal spanning tree

Drag in the applet one or more points of the graph and look how the [url=https://en.wikipedia.org/wiki/Minimum_spanning_tree]Minimal Spanning Tree[/url] changes with it.
The Minimal Spanning Tree forms a network in which all nodes (a.k.a. vertices) are connected in such a way that the total weight (here the length of the segments) is minimal.
– Conor Desmond, chris cambré

2.2.

–

2.3.

–

2.4.

–

2.5.

–

3.

Kruskal's Algorithm

  • 1. Kruskal's algorithm

3.1.

Kruskal's algorithm

Kruskal's algorithm step-by-step
[br][list][*]Start with the edge that has the lowest weight.[/*][*]Select the edge with the lowest weight that's still left and add it to the tree.[br][u]Note[/u]: if the addition of the edge with the lowest weight creates a cycle, drop it and take the next lowest edge.[br][/*][*]Continue this way until all nodes are connected. [/*][*]The subgraph you arrived at is called the minimal spanning tree.[/*][/list]
– Conor Desmond, chris cambré

Information