Minimum Spanning Tree

Dijkstra's Algorithm

```int array[10] = {1,2,3,4,5,6,7,8,9,10};
int map[10][10];
int visit[10];
int parent[10];
int distance[10];

void Minimum_Spanning_Tree()
{
int i, j, k, min, min_value;

for (i = 0; i < 10; i++) {
distance[i] = 0x7fffffff;
}

parent[0] = 0;            // arbitrarily select one node -> select 0
distance[0] = 0;

for (i = 0; i < 10; i++) {

min_value = 0x7fffffff;
min = -1;

for (j = 0; j < 10; j++)
if (!visit[i] && distance[j] < min_value) {
min_value = distance[j];
min = j;
}

if (min == -1)
return;
visit[min] = 1;

for (k = 0; k < 10; k++) {
if (!visit[k] && map[min][k] && map[min][k] < distance[k]) {   // a little different with SP
distance[k] = map[min][k];
parent[k] = min;
}
}
}
}
```

Time Complexity

Best:
O(n) — non of the nodes are connected to each other

Avg:
O(n2)?

Worst:
O(n2) — all nodes are connected to each other

```n times {                            // for strong connected graph, we should do n times
n times searching
+
n times scanning for adjacency matrix | e times scanning for adjacency list
}
```

Floyd's Algorithm

```#define MIN(a, b) ((a) < (b))?(a):(b)
int D[10][10];               // D is used to store D_k[i][j]
int W[10][10];              // W is adjacent matrix

void Floyd()
{
int i, j, k;
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
D[i][j] = W[i][j];             // D = D0

for (k = 0; k < 10; k++)
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
D[i][j] = MIN(D[i][j], D[i][k] + D[k][j]);
}
```

Note:
Dk[i, j] =
min(Dk-1[i, j], Dk-1[i, k] + Dk-1[k, j])
page revision: 25, last edited: 17 Apr 2010 05:21