# Teaching Kids Programming – Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph

Teaching Kids Programming – Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

### Shipping and Receiving – Sum of Costs between Pair of Vertices in Unweighted Graph

You are given a two-dimensional list of integers ports where ports[i] represents the list of ports that port i is connected to. You are also given another two-dimensional list of integers shipments where each list of the form [port_i, port_j] which means there is a shipment request from port_i to port_j.

Given that the cost to ship port_i to port_j is the length of the shortest path from the two ports, return the total cost necessary to send all the shipments. If there’s not a path between two ports, the cost is 0.

Constraints
p ≤ 100 where p is the length of ports
s ≤ 10,000 where s is the length of shipments
Example 1
Input

 ```1 2 3 4 5 6 7 8 9 10 ``` ```ports = [     [2, 3],     [2],     [1, 0],     [4],     [] ] shipments = [     [2, 4] ]```
```ports = [
[2, 3],
[2],
[1, 0],
[4],
[]
]
shipments = [
[2, 4]
]```

Output
3

### Depth First Search Algorithm on Unweighted Graph

The Depth First Search Algorithm (DFS) does not always find the optimal solutions unless we exhaust searching the entire Graph. The time complexity of the DFS is O(V+E) because we have to search all the vertices and edges. The following is the Recursive DFS to find the shortest path between a pair of vertices. The DFS to compute shortest paths only works in an unweighted Graph (or equal weights).

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ``` ```class Solution:     def solve(self, G, paths):         @cache         def dfs(i, j):               def f(i, j, seen = set()):                 if i == j:                     return 0                 if i in seen:                     return inf                 seen.add(i)                 ans = inf                                 for x in G[i]:                     ans = min(ans, f(x, j, seen) + 1)                 seen.remove(i)                 return ans               d = f(i, j, set())                 return d if d < inf else 0           return sum(dfs(i, j) for i, j in paths)```
```class Solution:
def solve(self, G, paths):
@cache
def dfs(i, j):

def f(i, j, seen = set()):
if i == j:
return 0
if i in seen:
return inf
ans = inf
for x in G[i]:
ans = min(ans, f(x, j, seen) + 1)
seen.remove(i)
return ans

d = f(i, j, set())
return d if d < inf else 0

return sum(dfs(i, j) for i, j in paths)```

For a Graph, we have to keep tracking of the vertices that have been visited so that we don’t end up visiting them again and again. This is done via a hash set.

### Depth Limit Search Algorithm on Unweighted Graph

The DLS (Depth Limit Search) Algorithm is based on Depth First Search Algorithm and with an additional requirement of a given max depth. The nodes that are beyond the depth d are ignored. So the DLS don’t end up travering a deep branch.

 ```1 2 3 4 5 6 7 8 9 10 11 12 ``` ```def dls(s, e, d, seen = set()):     if s == e:         return 0       if d < 0:         return inf     if s in seen:         return inf     seen.add(i)     ans = inf     for x in G[i]:         ans = min(ans, f(x, e, d - 1, seen) + 1)     return ans       ```
```def dls(s, e, d, seen = set()):
if s == e:
return 0
if d < 0:
return inf
if s in seen:
return inf
ans = inf
for x in G[i]:
ans = min(ans, f(x, e, d - 1, seen) + 1)
return ans       ```

### Iterative Deepening Search Algorithm on Unweighted Graph

The Iterative Deepening Search (IDS) Algorithm is the combination of DFS/DLS and BFS. The idea is to incrementally perform the Depth Limit Search (DLS) until we find the solution (which will be optimal since the depth is incremented from 0), or there is none solution. We can set the max depth equal to the number of the vertices in the Graph.

The time complexity for a IDS can be computed as:

$tex_43e43d2b1fcf6613e372e838b721b906 Teaching Kids Programming - Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph algorithms Depth First Search DFS graph Graph Algorithm graphs Iterative Deepening Search python teaching kids programming youtube video$

Which is $tex_171e29e85d9c8a13898f4c6b21d3401f Teaching Kids Programming - Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph algorithms Depth First Search DFS graph Graph Algorithm graphs Iterative Deepening Search python teaching kids programming youtube video$

The depth d is explored once, and the nodes at depth d-1 are explored twice etc.

The IDS has the same time complexity as DFS $tex_171e29e85d9c8a13898f4c6b21d3401f Teaching Kids Programming - Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph algorithms Depth First Search DFS graph Graph Algorithm graphs Iterative Deepening Search python teaching kids programming youtube video$ where b is the branching factor (the number of nodes for each node) and the d is the depth. And IDS has also the same space complexity as DFS $tex_ffa1a9c308734ab931db5fcf988b949d Teaching Kids Programming - Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph algorithms Depth First Search DFS graph Graph Algorithm graphs Iterative Deepening Search python teaching kids programming youtube video$ where d is the depth. Compared to DFS, the IDS is optimal/complete, it finds the shortest paths. The IDS has a better memory complexity than the Breadth First Search (BFS) Algorithm.

The code for Iterative Deepening Search:

 ```1 2 3 4 5 6 7 8 ``` ```def ids(G, s, e):     N = len(G) # the number of vertices in the graph aka the longest path     for i in range(N + 1):         seen = set()         ans = dls(G, s, e, d, seen)         if ans != inf:             return ans     return inf # not found```
```def ids(G, s, e):
N = len(G) # the number of vertices in the graph aka the longest path
for i in range(N + 1):
seen = set()
ans = dls(G, s, e, d, seen)
if ans != inf:
return ans

The Iterative Deepening Search Algorithm to sum the shortest paths/costs between pairs of vertices is given as follows:

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ``` ```class Solution:     def solve(self, G, paths):         @cache         def ids(i, j):             N = len(G) + 1               def dls(i, j, seen, depth):                 if i == j:                     return 0                 if i in seen:                     return inf                 if depth < 0:                     return inf                 seen.add(i)                 ans = inf                                 for x in G[i]:                     ans = min(ans, dls(x, j, seen, depth - 1) + 1)                 seen.remove(i)                 return ans               for d in range(N):                 x = dls(i, j, set(), d)                 if x < inf:                     return x             return 0           return sum(ids(i, j) for i, j in paths)```
```class Solution:
def solve(self, G, paths):
@cache
def ids(i, j):
N = len(G) + 1

def dls(i, j, seen, depth):
if i == j:
return 0
if i in seen:
return inf
if depth < 0:
return inf
ans = inf
for x in G[i]:
ans = min(ans, dls(x, j, seen, depth - 1) + 1)
seen.remove(i)
return ans

for d in range(N):
x = dls(i, j, set(), d)
if x < inf:
return x
return 0

return sum(ids(i, j) for i, j in paths)```

GD Star Rating