4.6. Connected Graphs¶
A graph is connected if there is a path from every node to every other node.
For many applications involving graphs, it is useful to check whether a graph is connected. Fortunately, there is a simple algorithm that does it.
You can start at any node and check whether you can reach all other nodes. If you can reach a node, v
, you can reach any of the neighbors of v
, which are the nodes connected to v
by an edge.
The Graph class provides a method called neighbors that returns a list of neighbors for a given node. For example, in the complete graph we generated in the previous section:
>>> complete.neighbors(0)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Suppose we start at node s
. We can mark s
as “seen” and mark its neighbors. Then we mark the neighbor’s neighbors, and their neighbors, and so on, until we can’t reach any more nodes. If all nodes are seen, the graph is connected.
Here’s what that looks like in Python:
def reachable_nodes(G, start):
seen = set()
stack = [start]
while stack:
node = stack.pop()
if node not in seen:
seen.add(node)
stack.extend(G.neighbors(node))
return seen
reachable_nodes
takes a Graph
and a starting node, start
, and returns the set of nodes that can be reached from start
.
Initially the set
, seen
, is empty, and we create a list called stack
that keeps track of nodes we have discovered but not yet processed. Initially the stack contains a single node, start
.
Now, each time through the loop, we:
Remove one node from the stack.
If the node is already in
seen
, we go back to Step 1.Otherwise, we add the node to
seen
and add its neighbors to the stack.
When the stack is empty, we can’t reach any more nodes, so we break out of the loop and return seen
.
As an example, we can find all nodes in the complete graph that are reachable from node 0:
>>> reachable_nodes(complete, 0)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Initially, the stack contains node 0 and seen
is empty. The first time through the loop, node 0 is added to seen
and all the other nodes are added to the stack (since they are all neighbors of node 0).
The next time through the loop, pop
returns the last element in the stack, which is node 9. So node 9 gets added to seen
and its neighbors get added to the stack.
Notice that the same node can appear more than once in the stack; in fact, a node with k neighbors will be added to the stack k times. Later, we will look for ways to make this algorithm more efficient.
We can use reachable_nodes
to write is_connected
:
def is_connected(G):
start = next(iter(G))
reachable = reachable_nodes(G, start)
return len(reachable) == len(G)
is_connected
chooses a starting node by making a node iterator and choosing the first element. Then it uses reachable
to get the set of nodes that can be reached from start
. If the size of this set is the same as the size of the graph, that means we can reach all nodes, which means the graph is connected.
A complete graph is, not surprisingly, connected:
>>> is_connected(complete)
True
In the next section we will generate ER graphs and check whether they are connected.

Q1:
 1
 Remove one node from the stack.
 2
 If the node is already in seen, we go back to Step 1.
 3
 Otherwised, we add the node to seen and add its neighbors to the stack.
 True
 Correct, is_connected chooses a starting node by making a node iterator and choosing the first element. Then it uses reachable to get the set of nodes that can be reached from start. If the size of this set is the same as the size of the graph, that means we can reach all nodes, which means the graph is connected.
 Fales
 Incorrect.
Q2: is_connected
checks to see if the set of nodes that can be reached from start is the same as the size of the graph?