# Synopse

iacc_thi - Using breadth first search, return the number of connected components and a list of nodes of each connected component splitted by lists.

• n,cc = iacc_thi(M)

• Output
• n: Number. Number of connected components of a graph
• cc: List. List with lists. Each list has the nodes from a connected component.
• Input
• M: Array. Weighted Adjacency matrix of a graph. 'Inf' indicates no edge.

# Description

Using breadth first search, It finds the number of connected components and create a list that has as many lists as there are connected component. Each one has all nodes from the related to the latter.

If the adjacency matrix represents a weighted graph, this matrix should have a M[i][j] equals to Inf, if there is no edge between i and j.

# Function Code

``` 1 import collections as col
2 import numpy as np
3
4 def iacc_thi(M):
5
6     nV = M.shape[0]
7     V = set(range(nV))
8     L = col.deque()
9     ccList = []
10     ccCount=0
11     label = [-1]*nV
12
13     while V:
14         ccCount+=1
15         ccList.append([])
16         L.appendleft(V.pop())
17
18         while L:
19             ccList[-1].append(L.pop())
20             neighV = np.where(M[ccList[-1][-1]] != np.inf)[0]
21             for i in neighV:
22                 if label[i] == -1:
23                     L.appendleft(i)
24                     label[i] = ccCount
25
26             V = V.difference(neighV)
27
28     return (ccCount,ccList)
```

# Examples

## Example 1

```[[ Inf  Inf  10.  Inf  Inf]
[ Inf  Inf  Inf  Inf  Inf]
[ 10.  Inf  Inf   8.  Inf]
[ Inf  Inf   8.  Inf  Inf]
[ Inf  Inf  Inf  Inf  Inf]]
Numero de componentes do grafo1:  3
Vértices de cada componente separados por listas:  [[0, 2, 0, 3], [1], [4]]
```

# Performance Tests

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

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1
Thiago iacc_thi 0.244 ms 2 14.63 ms 6 13.16 ms 500 96.397 ms 1

# References

 [Feof2009] Paulo Feofiloff. Algoritmos para Grafos em C via Sedgewick. IME-USP. http://www.ime.usp.br/~pf/algoritmos_para_grafos