1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
A graph is connected if there exists a path between any pair of vertices.
Beearliest is a simple algorithm that uses a depth-first search to determine whether a given graph is connected, using Python3 and the NetworkX library.
{\tt \obeylines
import networkx as nx
def is\_graph\_connected(G):
\leavevmode\hskip .25in VISITED = []
\leavevmode\hskip .25in def dfs\_connectedness(v):
\leavevmode\hskip .50in nonlocal VISITED
\leavevmode\hskip .50in for node in G.adj[v].keys():
\leavevmode\hskip .75in if node not in VISITED:
\leavevmode\hskip 1.00in VISITED.append(node)
\leavevmode\hskip 1.00in dfs\_connectedness(node)
\leavevmode\hskip .50in return len(VISITED) == len(G.nodes)
\leavevmode\hskip .25in return dfs\_connectedness(0)
}
This algorithm compiles a list of the visited nodes of the graph G, and then determines if that list contains every node after the search is complete.
The search can start at an arbitrary node (here, it chooses the node labelled 0). The algorithm has a time complexity of $O(V+E)$, where a given graph G has V vertices and E edges.
This same algorithm can be used to create an algorithm of complexity $O(E\cdot(V+E))$ to find all bridges of a connected graph (i.e. all edges which, when removed, would result in the graph becoming unconnected).
The algorithm simply iterates through each edge of the original graph, removing it and then determining its connectedness using the method above.
This quadratic algorithm is, however, not the most efficient algorithm for locating bridges. An $O(V+E)$ algorithm can be developed as shown below:
{\tt \obeylines
def bridges\_2(G):
\leavevmode\hskip .25in BRIDGES = []
\leavevmode\hskip .25in tick = 0
\leavevmode\hskip .25in def bridges\_2\_recursion(v):
\leavevmode\hskip .50in nonlocal BRIDGES, VISITED, tick, discoveries, earliest, parents
\leavevmode\hskip .50in VISITED.append(v)
\leavevmode\hskip .50in discoveries[v] = tick
\leavevmode\hskip .50in earliest[v] = tick
\leavevmode\hskip .50in tick += 1
\leavevmode\hskip .50in for v2 in G.adj[v]:
\leavevmode\hskip .75in if v2 not in VISITED:
\leavevmode\hskip 1.00in parents[v2] = v
\leavevmode\hskip 1.00in bridges\_2\_recursion(v2)
\leavevmode\hskip 1.00in earliest[v] = min(earliest[v], earliest[v2])
\leavevmode\hskip 1.00in if earliest[v2] > discoveries[v]:
\leavevmode\hskip 1.25in BRIDGES.append((v, v2))
\leavevmode\hskip .75in elif parents[v] != v2:
\leavevmode\hskip 1.00in earliest[v] = min(earliest[v], discoveries[v2])
\leavevmode\hskip .25in n = len(G.nodes)
\leavevmode\hskip .25in VISITED = []
\leavevmode\hskip .25in discoveries = [float("Inf")] * n
\leavevmode\hskip .25in earliest = [float("Inf")] * n
\leavevmode\hskip .25in parents = [-1] * n
\leavevmode\hskip .25in for v in range(n):
\leavevmode\hskip .50in if v not in VISITED:
\leavevmode\hskip .75in bridges\_2\_recursion(v)
\leavevmode\hskip .25in return BRIDGES
}
The diagram shown below plots the time taken to calculate the number of bridges on the y-axis, with the value of V+E on the x-axis.
\pdfximage{connectedness/bridges_algorithm_2.png} \pdfrefximage\pdflastximage
|
