```python
%pylab inline
```

    Populating the interactive namespace from numpy and matplotlib



```python
from sympy import Matrix, eye, ones
from graphviz import Digraph, Graph
import graphviz
```


```python
def is_binary(M): return all([M[i,j] == 0 or M[i,j] == 1 for j in range(M.shape[1]) for i in range(M.shape[0])])
def is_symmetric(M): return M == M.T

def plot(G):
    if is_symmetric(G).all(): return plot_graph(G)
    else: return plot_digraph(G)

def plot_graph(G):
    dot = Graph(comment="Matrix graph", engine='sfdp', format='png')
    dot.attr(size='6,6')
    dot.attr(overlap='false')
    dot.attr(fontsize='12')
    is_bin = is_binary(G)
    for i in range(G.shape[0]):
        dot.node(str(i), str(i))
        for j in range(i, G.shape[1]):
            if G[i,j] != 0:
                if is_bin: dot.edge(str(i), str(j))
                else: dot.edge(str(i), str(j), str(G[i,j]))
    return graphviz.Source(dot)

def plot_digraph(G):
    dot = Digraph(comment="Matrix graph", engine='sfdp', format='png')
    dot.attr(size='6,6')
    dot.attr(overlap='false')
    dot.attr(fontsize='12')
    is_bin = is_binary(G)
    for i in range(G.shape[0]):
        dot.node(str(i), str(i))
        for j in range(G.shape[1]):
            if G[i,j] != 0:
                if is_bin: dot.edge(str(i), str(j))
                else: dot.edge(str(i), str(j), str(G[i,j]))
    return graphviz.Source(dot)

def plot_mst(G, MST):
    dot = Graph(comment="Matrix graph", engine='sfdp', format='png')
    dot.attr(size='6,6')
    dot.attr(overlap='false')
    dot.attr(fontsize='12')
    is_bin = is_binary(G)
    for i in range(G.shape[0]):
        dot.node(str(i), str(i))
        for j in range(i, G.shape[1]):
            if G[i,j] != 0:
                if is_bin: dot.edge(str(i), str(j), color='red' if MST[i, j] != 0 else 'black')
                else: dot.edge(str(i), str(j), str(G[i,j]), color='red' if MST[i, j] != 0 else 'black')
    return graphviz.Source(dot)    
    
def generate_undirect_graph(n):
    G = np.array([ np.floor(np.random.random(n)*10) for _ in range(n)])
    G = G - np.diagonal(G) * np.eye(n)
    return G * G.T
```


```python
%time

def mst(G):
    if not is_symmetrical(G):
        raise ValueError('G must be undirected.')
    n = G.shape[0]
    #G = generate_undirect_graph(n)
    V = list(range(G.shape[0]))
    D = {(x,y):G[x,y] for x in range(G.shape[0]) for y in range(G.shape[1]) if G[x,y] != 0}
    D = sorted(D.items(), key=lambda kv: kv[1], reverse=True)
    MST = np.reshape(np.zeros(n*n), (n,n))
    weight = 0
    while len(D) > 0 and not all(V):
        k, d = D.pop(); x, y = k
        if V[x] != V[y]:
            mi, ma = min(V[x], V[y]), max(V[x], V[y])
            V[x] = V[y] = mi
            MST[x,y] = d; MST[y,x] = d
            weight += d
            for i in range(len(V)):
                if V[i] == ma: V[i] = mi

    return MST, weight
```

    Wall time: 0 ns



```python
MST, weight = mst(G)
print('Weight of MST is {}'.format(weight))
```

    Weight of MST is 81.0


# Weighted undirected graph


```python
plot(G)
```




    

    




```python
plot_mst(G, MST)
```




    

    




```python
plot(MST)
```




    

    



# Unweighted undirected graph


```python
M = np.array(np.ones(n) - np.eye(n))
M
```




    array([[0., 1., 1., 1., 1., 1., 1., 1.],
           [1., 0., 1., 1., 1., 1., 1., 1.],
           [1., 1., 0., 1., 1., 1., 1., 1.],
           [1., 1., 1., 0., 1., 1., 1., 1.],
           [1., 1., 1., 1., 0., 1., 1., 1.],
           [1., 1., 1., 1., 1., 0., 1., 1.],
           [1., 1., 1., 1., 1., 1., 0., 1.],
           [1., 1., 1., 1., 1., 1., 1., 0.]])




```python
MST, weight = mst(M)
plot_mst(M, MST)
```




    

    



6eaef7a5ca72245e2898128f6d73ae93bd139cd8
ipynb
Jupyter Notebook
Applied Math/.ipynb_checkpoints/MST-checkpoint.ipynb
darkeclipz/jupyter-notebooks
5de784244ad9db12cfacbbec3053b11f10456d7e
Unlicense
2018-08-28T12:16:12.000Z
2018-08-28T12:16:12.000Z
Applied Math/.ipynb_checkpoints/MST-checkpoint.ipynb
darkeclipz/jupyter-notebooks
5de784244ad9db12cfacbbec3053b11f10456d7e
Unlicense
Applied Math/.ipynb_checkpoints/MST-checkpoint.ipynb
darkeclipz/jupyter-notebooks
5de784244ad9db12cfacbbec3053b11f10456d7e
Unlicense
Qwen/Qwen-72B
1. YES
2. YES