# 5 Best Ways to Check If We Can Visit Any City From Any City in Python

Rate this post

π‘ Problem Formulation: In this article, we tackle the challenge of determining whether it is possible to travel between any two cities within a network of cities and roads. We take as input a representation of cities and roads (such as a graph) and expect a boolean output indicating the connectivity of all cities (True if all cities are accessible from each other, False otherwise).

## Method 1: Using Depth-First Search (DFS)

The Depth-First Search algorithm is a straightforward technique to explore all the vertices of a graph traversing as far as possible along each branch before backtracking. This method’s function is to start from each city (vertex) and utilize a stack (either implicit with recursion or explicit) to visit all the connected cities.

Here’s an example:

```def dfs(graph, start, visited=None):
if visited is None:
visited = set()
for neighbour in graph[start]:
if neighbour not in visited:
dfs(graph, neighbour, visited)
return visited

graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}

all_cities_connected = all(dfs(graph, city) == set(graph.keys()) for city in graph)
print(all_cities_connected)```

Output: `True`

This code snippet defines a recursive `dfs` function to traverse the graph and a dictionary `graph` representing our cities. It then checks if all cities are connected through iterative application of DFS starting from each city to ensure complete connectivity.

## Method 2: Using Breadth-First Search (BFS)

Breadth-First Search is another graph traversal method that explores the neighbor nodes in layers. It uses a queue to visit cities level by level outwards from the start point. BFS is beneficial to find the shortest path on unweighted graphs.

Here’s an example:

```from collections import deque

def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
city = queue.popleft()
if city not in visited:
queue.extend(graph[city] - visited)
return visited

# Use the same graph as defined in Method 1

all_cities_connected = all(bfs(graph, city) == set(graph.keys()) for city in graph)
print(all_cities_connected)```

Output: `True`

This example uses a BFS algorithm to check city connectivity. It demonstrates how to use a queue to systematically explore each city’s neighbors, ensuring that we cover all the cities without repetitions.

## Method 3: Using Union-Find Algorithm

The Union-Find algorithm is an efficient algorithm to track a set of elements partitioned into disjoint subsets. It’s particularly good for dynamic connectivity problems in graphs, where the aim is to determine whether all nodes are connected.

Here’s an example:

```def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):
xroot = find(parent, x)
yroot = find(parent, y)
if rank[xroot]  rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1

def check_connected(edges, n):
parent = list(range(n))
rank = [0] * n
for x, y in edges:
xroot = find(parent, x)
yroot = find(parent, y)
if xroot != yroot:
union(parent, rank, xroot, yroot)
return len(set(find(parent, i) for i in range(n))) == 1

# Edges represented as (city1, city2)
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)]
print(check_connected(edges, 6))```

Output: `True`

In this code, the `find` function determines the root of a set, and `union` joins two sets if they are distinct. The `check_connected` function uses these to process a list of city connections and determines if a single connected component exists.

## Method 4: Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a classic dynamic programming approach to find the shortest paths between all pairs of vertices in a weighted graph. While it’s an overkill for just connectivity check, it serves to demonstrate the connectivity comprehensively.

Here’s an example:

```def floyd_warshall(n, edges):
dist = [[float('inf')] * n for i in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v in edges:
dist[u][v] = 1
dist[v][u] = 1  # because the graph is undirected

for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

return all(dist[i][j] < float('inf') for i in range(n) for j in range(n))

print(floyd_warshall(6, edges))```

Output: `True`

This code implements the Floyd-Warshall algorithm. It initializes a matrix with distances between all city pairs and iteratively updates the matrix with the shortest distance discovered so far. A connected graph will have finite distances between all city pairs.

## Bonus One-Liner Method 5: Using NetworkX Library

If you’re working with graphs in Python, the NetworkX library provides advanced graph algorithms in simple-to-use functions. This one-liner uses NetworkX to check if our graph is connected or not.

Here’s an example:

```import networkx as nx

# Constructing the same graph as a NetworkX graph
G = nx.Graph()
G.add_edges_from([(chr(65+i), chr(65+j)) for i, j in edges])

# One-liner to check connectivity
print(nx.is_connected(G))```

Output: `True`

The above code snippet uses NetworkX’s `is_connected` function which directly checks if the graph represented as G is connected, thus confirming if every city is reachable from any city.

## Summary/Discussion

• Method 1: Depth-First Search. Efficient for exploring all vertices in a graph. It can become slow with a very large number of cities.
• Method 2: Breadth-First Search. Can quickly determine the shortest path and connectivity. Can be memory-intensive for graphs with wide breadth.
• Method 3: Union-Find Algorithm. Highly efficient for checking connectivity on the fly as you add edges to the graph. It requires a bit of extra setup for the disjoint-set data structure.
• Method 4: Floyd-Warshall Algorithm. While exhaustive and informative, it is overkill for simple connectivity checks and has a higher time complexity, making it less efficient for large graphs.
• Bonus Method 5: NetworkX Library. Extremely simple and fast for those already using NetworkX for graph handling. It requires an additional library dependency.