Bridges

Definition

Definition

Bridges Algorithm, also known as the "Bridges of Konigsberg" problem, is a classic graph theory problem that aims to determine whether it is possible to traverse all the bridges of a city's river system exactly once and return to the starting point without crossing any bridge twice. This algorithmic problem is essential in understanding Eulerian paths and circuits

Explanation

Start by creating a graph depicting the city's bridges. Calculate the degree of each node, representing the number of bridges connected to it. If there are more than two nodes with odd degrees, it's impossible to cross all bridges exactly once without retracing steps. In the case of exactly two nodes with odd degrees, begin the journey from one and conclude at the other. When all nodes have even degrees, any node can serve as the starting point for the route

Guidance

• Identify the nodes and edges in the graph
• Calculate the degree of each node by counting the number of incident edges
• Determine if there are any nodes with odd degrees
• If there are more than two nodes with odd degrees, it's impossible to solve the problem
• If there are exactly two nodes with odd degrees, start the path from one of these nodes and end it at the other
• If all nodes have even degrees, any node can be chosen as a starting point
• Traverse the graph using depth-first search or breadth-first search to find a path that crosses each bridge exactly once
• Backtrack if necessary to explore alternative paths
• If a path exists that traverses all bridges exactly once, return it as the solution

Tips

• use graph representation techniques such as adjacency lists or matrices for efficient traversal
• employ backtracking to explore alternative paths when necessary
• validate the solution by ensuring that all bridges are traversed exactly once

Practice

Practice

function BridgesAlgorithm(graph):
  odd_degree_nodes = []
  for node in graph.nodes:
    if degree(node) % 2 != 0:
      odd_degree_nodes.append(node)

  if length(odd_degree_nodes) > 2:
    return "No solution exists"
  else if length(odd_degree_nodes) == 2:
    start_node = odd_degree_nodes[0]
    end_node = odd_degree_nodes[1]
  else:
    start_node = any_node
    end_node = any_node

  path = find_path(graph, start_node)
  return path

function find_path(graph, node):
  path = []
  stack = [node]
  while stack is not empty:
    current_node = stack.pop()
    path.append(current_node)
    for neighbor in graph.neighbors(current_node):
      if edge(current_node, neighbor) not in path:
        stack.push(neighbor)
  return path

Solution

package main

type Graph struct {
    vertices int
    edges    map[int][]int
}

func NewGraph(v int) *Graph {
    return &Graph{
        vertices: v,
        edges:    make(map[int][]int),
    }
}

func (g *Graph) addEdge(u, v int) {
    g.edges[u] = append(g.edges[u], v)
    g.edges[v] = append(g.edges[v], u)
}

func dfs(u, parent int, disc, low []int, visited []bool, bridges *[][]int, time *int, g *Graph) {
    visited[u] = true
    disc[u] = *time
    low[u] = *time
    *time++

    for _, v := range g.edges[u] {
        if !visited[v] {
            dfs(v, u, disc, low, visited, bridges, time, g)
            low[u] = min(low[u], low[v])
            if low[v] > disc[u] {
                *bridges = append(*bridges, []int{u, v})
            }
        } else if v != parent {
            low[u] = min(low[u], disc[v])
        }
    }
}

func findBridges(g *Graph) [][]int {
    disc := make([]int, g.vertices)
    low := make([]int, g.vertices)
    visited := make([]bool, g.vertices)
    bridges := [][]int{}
    time := 0

    for i := 0; i < g.vertices; i++ {
        if !visited[i] {
            dfs(i, -1, disc, low, visited, &bridges, &time, g)
        }
    }
    return bridges
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

import java.util.ArrayList;
import java.util.List;

class Graph {

  int vertices;
  List<List<Integer>> edges;

  Graph(int v) {
    vertices = v;
    edges = new ArrayList<>();
    for (int i = 0; i < v; i++) {
      edges.add(new ArrayList<>());
    }
  }

  void addEdge(int u, int v) {
    edges.get(u).add(v);
    edges.get(v).add(u);
  }
}

public class BridgeInGraph {

  static int time = 0;

  static void dfs(int u, int parent, int[] disc, int[] low, boolean[] visited, List<List<Integer>> bridges, Graph g) {
    visited[u] = true;
    disc[u] = time;
    low[u] = time;
    time++;

    for (int v : g.edges.get(u)) {
      if (!visited[v]) {
        dfs(v, u, disc, low, visited, bridges, g);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > disc[u]) {
          bridges.add(List.of(u, v));
        }
      } else if (v != parent) {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }

  static List<List<Integer>> findBridges(Graph g) {
    int[] disc = new int[g.vertices];
    int[] low = new int[g.vertices];
    boolean[] visited = new boolean[g.vertices];
    List<List<Integer>> bridges = new ArrayList<>();

    for (int i = 0; i < g.vertices; i++) {
      if (!visited[i]) {
        dfs(i, -1, disc, low, visited, bridges, g);
      }
    }
    return bridges;
  }
}

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.edges = new Array(vertices).fill().map(() => []);
  }

  addEdge(u, v) {
    this.edges[u].push(v);
    this.edges[v].push(u);
  }
}

let time = 0;

function dfs(u, parent, disc, low, visited, bridges, g) {
  visited[u] = true;
  disc[u] = time;
  low[u] = time;
  time++;

  for (let v of g.edges[u]) {
    if (!visited[v]) {
      dfs(v, u, disc, low, visited, bridges, g);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > disc[u]) {
        bridges.push([u, v]);
      }
    } else if (v !== parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

function findBridges(g) {
  const disc = new Array(g.vertices).fill(0);
  const low = new Array(g.vertices).fill(0);
  const visited = new Array(g.vertices).fill(false);
  const bridges = [];

  for (let i = 0; i < g.vertices; i++) {
    if (!visited[i]) {
      dfs(i, -1, disc, low, visited, bridges, g);
    }
  }
  return bridges;
}

class Graph(private val vertices: Int) {
    private val edges: Array<MutableList<Int>> = Array(vertices) { mutableListOf() }

    fun addEdge(u: Int, v: Int) {
        edges[u].add(v)
        edges[v].add(u)
    }

    fun getEdges(): Array<MutableList<Int>> {
        return edges
    }
}

var time = 0

fun dfs(u: Int, parent: Int, disc: IntArray, low: IntArray, visited: BooleanArray, bridges: MutableList<List<Int>>, g: Graph) {
    visited[u] = true
    disc[u] = time
    low[u] = time
    time++

    for (v in g.getEdges()[u]) {
        if (!visited[v]) {
            dfs(v, u, disc, low, visited, bridges, g)
            low[u] = minOf(low[u], low[v])
            if (low[v] > disc[u]) {
                bridges.add(listOf(u, v))
            }
        } else if (v != parent) {
            low[u] = minOf(low[u], disc[v])
        }
    }
}

fun findBridges(g: Graph): List<List<Int>> {
    val disc = IntArray(g.vertices) { 0 }
    val low = IntArray(g.vertices) { 0 }
    val visited = BooleanArray(g.vertices) { false }
    val bridges = mutableListOf<List<Int>>()

    for (i in 0 until g.vertices) {
        if (!visited[i]) {
            dfs(i, -1, disc, low, visited, bridges, g)
        }
    }
    return bridges
}

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.edges = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.edges[u].append(v)
        self.edges[v].append(u)

def dfs(u, parent, disc, low, visited, bridges, g):
    global time
    visited[u] = True
    disc[u] = time
    low[u] = time
    time += 1

    for v in g.edges[u]:
        if not visited[v]:
            dfs(v, u, disc, low, visited, bridges, g)
            low[u] = min(low[u], low[v])
            if low[v] > disc[u]:
                bridges.append([u, v])
        elif v != parent:
            low[u] = min(low[u], disc[v])

def find_bridges(g):
    global time
    disc = [0] * g.vertices
    low = [0] * g.vertices
    visited = [False] * g.vertices
    bridges = []
    time = 0

    for i in range(g.vertices):
        if not visited[i]:
            dfs(i, -1, disc, low, visited, bridges, g)
    return bridges

struct Graph {
    vertices: usize,
    edges: Vec<Vec<usize>>,
}

impl Graph {
    fn new(vertices: usize) -> Graph {
        Graph {
            vertices,
            edges: vec![Vec::new(); vertices],
        }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.edges[u].push(v);
        self.edges[v].push(u);
    }
}

static mut TIME: usize = 0;

fn dfs(u: usize, parent: isize, disc: &mut [usize], low: &mut [usize], visited: &mut [bool], bridges: &mut Vec<Vec<usize>>, g: &Graph) {
    unsafe {
        visited[u] = true;
        disc[u] = TIME;
        low[u] = TIME;
        TIME += 1;

        for &v in &g.edges[u] {
            if !visited[v] {
                dfs(v, u as isize, disc, low, visited, bridges, g);
                low[u] = std::cmp::min(low[u], low[v]);
                if low[v] > disc[u] {
                    bridges.push(vec![u, v]);
                }
            } else if v != parent as usize {
                low[u] = std::cmp::min(low[u], disc[v]);
            }
        }
    }
}

fn find_bridges(g: &Graph) -> Vec<Vec<usize>> {
    let mut disc = vec![0; g.vertices];
    let mut low = vec![0; g.vertices];
    let mut visited = vec![false; g.vertices];
    let mut bridges = Vec::new();
    unsafe {
        TIME = 0;
    }

    for i in 0..g.vertices {
        if !visited[i] {
            dfs(i, -1, &mut disc, &mut low, &mut visited, &mut bridges, g);
        }
    }
    bridges
}

class Graph {
  vertices: number;
  edges: number[][];

  constructor(vertices: number) {
    this.vertices = vertices;
    this.edges = new Array(vertices).fill(null).map(() => []);
  }

  addEdge(u: number, v: number) {
    this.edges[u].push(v);
    this.edges[v].push(u);
  }
}

let time = 0;

function dfs(
  u: number,
  parent: number,
  disc: number[],
  low: number[],
  visited: boolean[],
  bridges: number[][],
  g: Graph,
) {
  visited[u] = true;
  disc[u] = time;
  low[u] = time;
  time++;

  for (let v of g.edges[u]) {
    if (!visited[v]) {
      dfs(v, u, disc, low, visited, bridges, g);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > disc[u]) {
        bridges.push([u, v]);
      }
    } else if (v !== parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

function findBridges(g: Graph): number[][] {
  const disc: number[] = Array(g.vertices).fill(0);
  const low: number[] = Array(g.vertices).fill(0);
  const visited: boolean[] = Array(g.vertices).fill(false);
  const bridges: number[][] = [];

  for (let i = 0; i < g.vertices; i++) {
    if (!visited[i]) {
      dfs(i, -1, disc, low, visited, bridges, g);
    }
  }
  return bridges;
}