Traveling Bus problem

In an imagery example of traveling between train station T1 and T2 using buses. There are three bus routes leaves from T1 which are B1, B2, and B3, but none of them goes directly to T2; instead, they connect to B4, B5, and B6 respectively. Imagine that we want to travel from T1 to T2 using all routes; that is, we need to ride all buses at least once.

DFS Graph 1

```mermaid %% DFS Traversal Example: Bus Traveling from T1 to T2 (Layered) graph TD %% Level 1 subgraph Level1 [ ] direction LR T1[“T1 (1)”] end

%% Level 2
subgraph Level2 [ ]
    direction LR
    B1["B1 (2)"]
    B2["B2 (5)"]
    B3["B3 (7)"]
end

%% Level 3
subgraph Level3 [ ]
    direction LR
    B4["B4 (3)"]
    B5["B5 (6)"]
    B6["B6 (8)"]
end

%% Level 4
subgraph Level4 [ ]
    direction LR
    T2["T2 (4)"]
end

T1 <--> B1
T1 <--> B2
T1 <--> B3

B1 <--> B4
B2 <--> B5
B3 <--> B6

B4 <--> T2
B5 <--> T2
B6 <--> T2

```

BFS Graph 1

```mermaid %% BFS Traversal Example: Bus Traveling from T1 to T2 (Layered) graph TD %% Level 1 subgraph Level1 [ ] direction BT T1[“T1 (1)”] end

%% Level 2
subgraph Level2 [ ]
    direction BT
    B1["B1 (2)"]
    B2["B2 (5)"]
    B3["B3 (7)"]
end

%% Level 3
subgraph Level3 [ ]
    direction BT
    B4["B4 (3)"]
    B5["B5 (6)"]
    B6["B6 (8)"]
end

%% Level 4
subgraph Level4 [ ]
    direction BT
    T2["T2 (4)"]
end

T1 <--> B1
B1 <--> B2
B2 <--> B3

B3 <--> B4
B4 <--> B5
B5 <--> B6

B6 <--> T2

```

DFS T1 to T2

digraph G {
  rankdir=TB;  // top-to-bottom layout

  subgraph cluster_Level1 {
    label="Level 1";
    T1 [label="T1"];
  }

  subgraph cluster_Level2 {
    label="Level 2";
    B1 [label="B1"];
    B2 [label="B2"];
    B3 [label="B3"];
  }

  subgraph cluster_Level3 {
    label="Level 3";
    B4 [label="B4"];
    B5 [label="B5"];
    B6 [label="B6"];
  }

  subgraph cluster_Level4 {
    label="Level 4";
    T2 [label="T2"];
  }

  {rank=same; T1;}
  { rank=same; B1; B2; B3; }
  { rank=same; B4; B5; B6; }
  { rank=same; T2; }

  // Undirected edges (dir=none removes arrowheads)
  T1 -> B1 [dir=none];
  T1 -> B2 [dir=none];
  T1 -> B3 [dir=none];
  B1 -> B4 [dir=none];
  B2 -> B5 [dir=none];
  B3 -> B6 [dir=none];
  B4 -> T2 [dir=none];
  B5 -> T2 [dir=none];
  B6 -> T2 [dir=none];
}

BFS T1 to T2

digraph G {
  rankdir=TB;  // top-to-bottom layout

  // --- Level 1 ---
  subgraph cluster_Level1 {
    label="Level 1";
    T1 [label="T1"];
  }

  // --- Level 2 ---
  subgraph cluster_Level2 {
    label="Level 2";
    B1 [label="B1"];
    B2 [label="B2"];
    B3 [label="B3"];
  }

  // --- Level 3 ---
  subgraph cluster_Level3 {
    label="Level 3";
    B4 [label="B4"];
    B5 [label="B5"];
    B6 [label="B6"];
  }

  // --- Level 4 ---
  subgraph cluster_Level4 {
    label="Level 4";
    T2 [label="T2"];
  }

  // Force nodes in Level 2 to share the same rank (horizontal).
  {rank=same; T1;}
  { rank=same; B1; B2; B3; }
  { rank=same; B4; B5; B6; }
  { rank=same; T2; }

  // Edges (undirected style)
  T1 -> B1 [dir=none];
  B1 -> B2 [dir=none];
  B2 -> B3 [dir=none];
  B3 -> B4 [dir=none];
  B4 -> B5 [dir=none];
  B5 -> B6 [dir=none];
  B6 -> T2 [dir=none];
}