# Minimum Spanning Tree

## Kruskal's alogrithm

**This alogorithm builds a minimum spanning tree**

**Let $G$ be any undirected ,conneted graph**

## steps
1. sort the cost of edges
2. if (the graph creates cycle) add the edge to $T$
3. delete edge
:::info
worst case $O(e\ log\ e)$
:::
****
## Prim's Alogorithm

**Like Kruskal, constucts edge by edge**

We add a least-cost edge (u,v) to $T$ s.t. $T\cup{(u,v)}$

TV = {0};
for (T=0;T contains fewer than n-1 edges;add(u,v)to T)
{
    Let(u,v) be a least-cost edge s.t. u in TV and v not in TV
    if(there is no such edge) break;
    add v to TV;
}
if(T contain fewer n-1 edges) cout<<"no spanning tree";

***
## Slollin's Alogorirhm
**slollin selects several edges at each stage .
At the start of a stage,the selects edges,from a spanning Forest.(i.e. vertices = edges)
Every vertix is a tree,then pick edge .
Constuct trees each other**
:bulb: [Sollin's Graph](https://www.csie.ntu.edu.tw/~ds/ppt/ch6/sld064.htm)

# Shortest Path
1. Single Source : Nonnegative Edge Costs
2. Single Source : General Weights
3. All-Pairs Shorest path
4. Transitive Closure

$Notation :$ $dsit[u]$ **is represent the shortest path to u**
:::info
If we want go to w,the path will be $dist[u] + length(u,w)$
and $bool$ $s[i]$ is to concern i whether or not in S
:::

void Graph::ShortestPath(const int n,const int v)
{
    for(int i=0;i<n;i++){
    s[i]=false;
    dist[i]=length[v][i];
    }
        s[v]=ture;
        dist[v]=0; //initial
    for(i=0;i<n-2;i++){
      int u=Choose(n);
      s[u]=true;
      for(int w=0;w<n;w++)
          if(!s[w] && dist[w]<dist[u]+length[u][w])
          disw[w] = dist[u] + length[u][w];
    }
}

# Activity Network
***
## Activity On Vertices
**For example: 課程的順序
predecessor and successor relationship**
## Activity On Edges
**Process manager
Concerning about Time to manager project
as what is the least amount of time in which the project may be completed.**
:::danger
$Earliest\ Time \ e(i)$ :
$Hint:$ $e(i)=ee(k)$ 往後推
:::
:::danger
$Latest\ Time\ l(i)$
$Hint:$ $l(i)=le(k)-lenth[i][i-1]$ 由後往前推
:::
## Critical Path
$e(i)=l(i)$ is Critical point or activity
**Speeding up critical path will be efficiently and effective**