# Synopse

Brief function synopse: This function returns the Minimum Spanning Tree (MST) of a connected graph G.

• array= imstk_fra(A)
• Output
• Array: MST A.
• Input
• A: Array. Adjacency matrix.

# Description

Given an adjacency matrix A representing a connected graph G, the function returns the A´s MST, using kruskal algorithm. For each vertex v a list of visited vertex exists in order to check for cycles.

Note: G must be fully connected.

# Function Code

``` 1 from numpy import *
2 from iacc_fra import ianeighvert
3
5    # matrix form W U V
6    n = max([max(L[::,1]),max(L[::,2])])+1
7    A = ones((n,n)) * float('inf')
8    # symmetric matrix
9    A[L[::,1],L[::,2]]=L[::,0]
10    A[L[::,2],L[::,1]]=L[::,0]
11    return A
12
13 # transforms adjacency matrix into list with weights
15     vx=L.shape
16     v=vx[0]
17     ind=arange(v)
18     tam=0;
19     lista=[]
20     i=0
21     for r in ind:
22         lv=ianeighvert(L,r)
23         for nbv in lv:
24             if nbv>r:
25                 lista.append((L[r,nbv],int(r),int(nbv)))
26     return array(lista)
27
28
29 # Kruskal algorithm
30 def iamstk_fra(L):
31    n=L.shape[0]
32    b=ones((n,n),float)*float('inf')
33    d=diag(diag(b))
34    L=L+d
36    edges=[]
37    edgen=0
38    for i in arange(G.shape[0]):
39      edges.append((float(G[i,0]),int(G[i,1]),int(G[i,2])))
40    Q = sorted (edges)
41    T = []
42    clusters = [[] for i in range(n)]
43    for i in arange(n):
44      clusters[i].append(i)
45    i = 0
46    T_weight = 0
47    while len (T) < n - 1:
48         w=Q[i][0]
49         u=Q[i][1]
50         v=Q[i][2]
51         if clusters[u] != clusters[v]:
52             T.append ((int(w),int(u),int(v)))
53             clusters[u].extend(clusters[v])
54             for l in clusters[v]:
55                clusters[l] = clusters[u]
56             T_weight += w
57             edgen+=1
58         i = i + 1
59
60    return T_weight,T
```

# Example

## Example 1

Simple graph with 5 vertex

``` 1 from iamstk_fra import *
2 from courseIA368Q1S2012.wen_lib import adj2Graph
3
4 d=ones((5,5),int)
5 d=d*float("inf")
6 d[0,1]=1
7 d[0,2]=1
8 d[0,3]=1
9 d[1,0]=1
10 d[1,4]=1
11 d[2,0]=1
12 d[2,4]=1
13 d[3,0]=1
14 d[3,4]=1
15 d[4,1]=1
16 d[4,2]=1
17 d[4,3]=1
19 mmgraphviz(graph, 'Graph with 5 vertex')
20 r1=iamstk_fra(d)
21 print ("Sum:")
22 print (r1[0])
```
```Sum:
4.0
```

## Example 2

Greater 15 vertex graph

``` 1 import courseIA368Q1S2012.fra_lib as lib
2
3 M=array([[7,0,1],[5,0,4],[1,0,3],[2,1,2],[1,2,4],[2,4,5],[9,5,11],[2,11,10],
4 [1,10,12],[2,14,12],[1,14,13],[2,9,13],[1,9,8],[2,7,8],[1,7,6],[5,3,6],[1,2,8],
5 [4,4,10],[8,5,9],[3,3,9],[4,3,4],[6,6,10]])
8 mmgraphviz(graph1, 'Graph with 15 vertex')
9 r1=iamstk_fra(f)
10 print ("Sum:")
11 print (r1[0])
12 a,b=lib.list2array(r1[1])
15 mmgraphviz(mst, 'MST Graph' )
```
```Sum:
22.0
```

## Test:

Test using four different graphs. The results and the processing time are diplayed in a Table. See also MST performance test comparisson

gravando arquivo: /home/rubens/www/media/Attachments/iaOPF/iamstk_fra/testperf.pkl

Autor Funcao A simple   A: rand(6,6)   100 nodes, complete   100 nodes, 0.5   Grafo MST
Francisco iamstk_fra 0.352 ms 9.0 0.36 ms 21.0 46.726 ms 318.055294457 22.973 ms 624.679654926 0.394 ms 139.0

# References

 [Feof2009] Paulo Feofiloff. Algoritmos para Grafos em C via Sedgewick. IME-USP. http://www.ime.usp.br/~pf/algoritmos_para_grafos
 [Naha2011] Nahla Ibrahim. Optimal Spanning Trees. Stellenbosch University, South Africa

Algoritmo 1: