2023-11-27

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time

---

Huffman Coding

Characters that are more frequent needs less code.

Minimum Cost Spanning Tree

finding the spanning tree that has minimum cost.

Spanning Tree

• The tree that touches all the nodes with minimum number of edges

• Do not have any loops.

The # of edges = (# of nodes) -1

representation of a Graph

G = (V,E), where V = {1,2,3,4,5,6} , E = {(1,2),(2,3),(3,4),(4,5),(5,6),(6,1)}

• There is only one minimum cost spanning tree.

• There is only one minimum cost

Prim's Minimum Cost Spanning Tree

1. select the minimum cost edge

2. Select the next minimum cost edge among already connected nodes.

3. repeat stage 2 until the number of edges become (# nodes -1)

Kruskal's Minimum Cost Spanning Tree

Select the next minimum, but not if you make up a cycle. In that case, take the next minimum instead.

time complexity $O(E*E)$

If you take the heap, it can be reduced to $O(E \log{E})$

Use case on Non-Connected Graphs

Kruskals. The Prims will not able to discover the other isolated nodes.

Dijkstra's Algorithm

Single Source shortest path problem

The shortest path weight from a selected source node to the each other nodes.

• initialize the not-directly-connected paths with infinity.

• Relaxation : exchanging/taking the less costed path.