# Synopse

This function counts the number of connected components of a graph.

• counter = iacc_rob(A)

• Output

• counter: The number of connected components. 'Inf' value means unconnected vertices.
• Input

• A: Adjacency matrix of a graph. 'Inf' value means unconnected vertices.

# Description

This function counts the number of connected components of a graph using the Depth-First-Search (DFS) algorithm. The pseudo-code is shown below.

Algoritmo 1:

# Function Code

``` 1 from  numpy import*
2
3 global visited
4 global graph
5
6 # Function that counts the number of connected components
7 def iacc_rob(A):
8
9    global visited
10    global graph
11
12    graph = A
13    visited= zeros(len(graph[0]))
14
15    counter = 0
16    label = 0
17
18    for i in range(len(graph[0])):
19       if (visited[i] == 0):
20          counter += 1
21          label += 1
23
24    return counter
25
26 # Depth First Search Algorithm
27 ##########################################################################################
28
30    global visited
31    global graph
32    visited[i] = label
33    neighbors = iafindConnectedVertices(i)
34
35    for i in neighbors:
36       if (visited[i] == 0):
38    return
39
40 # Function that finds the vertices that are connected to a vertex i
41 ##########################################################################################
42
43 def iafindConnectedVertices(i):
44    global graph
45    connected_vertices = where(graph[i,:]!=float('inf'))
46    return connected_vertices[0]
```

# Examples

This example generates a random graph and counts its connected components

## Example 1:

```1 from courseIA368Q1S2012.rob_iarandgraph import iarandGraph
3 from iacc_rob import*
4
5
6 graph1 = iarandGraph(5,0.2)
7 mmgraphviz(adj2Graph(graph1), 'Rando graph with 5 vertices')
8 print('The number of connected components is %s' %iacc_rob(graph1))
```
```The number of connected components is 2
```

## Example 2:

Example using four different graphs. The results and the processing time are diplayed in a Table.

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

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1
Roberto iacc_rob 0.263 ms 2 16.81 ms 6 11.443 ms 500 391.823 ms 1

# References

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