Graph Algorithms: Depth-First Search, Bellman-Ford, and Euler

Posted on Jan 24, 2025 in Computer Engineering

Depth-First Search (DFS)

Code:

def _dfs(G, node, verts):

• # Add node to visited
• verts.add(node)
• # For each neighbor
• for neigh in G[node]:
• # If neighbor not visited
• if neigh not in verts:
• # Start exploration from neighbor
• verts = _dfs(G, neigh, verts)
• return verts

Connected Components

Code:

def cnx(G):

• components = []
• visited = set()
• # For every node (so we guarantee that every node is visited even if not connected)
• for node in G:
• if node in visited: continue # If already visited, next
• # Explore (e.g. with DFS) from the given node
• comp = _dfs(G, node, set())
• # Update visited from that exploration
• visited.update(comp)
• # If DFS finished, a connected component has already been found
• components.append(list(comp))
• return components

Bellman-Ford Algorithm

Code:

def bellman_ford(G, origin, destination):

• distance = dict()
• parent = dict()
• # Initialize structures
• for node in G.nodes:
• distance[node] = float('inf')
• parent[node] = None
• distance[origin] = 0
• # Relax the edges node-1 times
• for _ in range(len(G)-1):
• for u,v in G.edges:
• new_dist = G[u][v]['weight']
• if distance[u] + new_dist < distance[v]:
• distance[v] = distance[u] + new_dist
• parent[v] = u
• # If when trying to relax the edges one more time we succeed, there is a negative cycle
• for u,v in G.edges:
• new_dist = G[u][v]['weight']
• if distance[u] + new_dist < distance[v]:
• print("Negative cycle detected!")
• return {
• 'path': [],
• 'distance': float('inf')
• }
• # Reconstruct the path
• path = []
• node = destination
• while node != None:
• path.append(node)
• node = parent[node]
• if path[0] != destination or path[-1] != origin:
• print("The destination node is not reachable from the origin")
• return {'path': [],
• 'distance': float('inf')}
• return {
• 'path': path[::-1],
• 'distance': distance[destination]
• }

Euler Algorithm

from random import choice

Code:

def euler(G):

• # Check if has euler cycle
• for node in G.nodes:
• if G.degree(node) % 2: return []
• # Visited EDGES
• visited = set()
• # Random starting node
• cycles = []
• path = [choice(list(G))]
• while len(visited) is not len(G.edges):
• node = path[-1]
• for neigh in G.neighbors(node):
• edge = tuple(sorted([node, neigh]))
• # Pick unvisited edge
• if edge not in visited:
• path.append(neigh)
• visited.add(edge)
• break
• # Closed loop
• if path[0] == path[-1]:
• cycles.append(path)
• # Search next node on path
• for node in path:
• edges = set([tuple(sorted([node, n])) for n in G.neighbors(node)])
• unvisited = edges - visited
• if unvisited:
• path = [node]
• break
• # Reconstruct path from cycles
• path = []
• for c in cycles:
• if not path: path = c # First
• else:
• idx = path.index(c[0])
• path = path[:idx] + c + path[idx+1:]
• return path