1. BFS (width search):

The BFS (width search) is a graph and tree path algorithm. It uses a queue (FIFO) to explore the nodes, starting with an initial node and then moving through its direct neighbours, followed by their neighbours, until all reachable nodes are visited.

          2.  Principle of operation: BFS

1.       Add the initial node to the queue.

2.       As long as the queue is not empty:

                             - Scroll a node in the queue.

                              - Mark this node as visited.

                              - Put all the neighbors not yet visited in the queue.

3.       Repeat until the queue is empty or the solution is found (in case of a search).

Example 1:

   Here is the following graph:

 ·       Represent the graph in BFS

·        The order of nodes visited could be: A – B – C- D – E - F

2. DFS (Depth-First Search):

The DFS algorithm explores a graph or tree by following each branch to a terminal node or already visited node, then it goes back to examine other branches. Start with a root node, mark it as visited, and recursively explore each adjacent unvisited node.

Example 1:

Here is the following graph:

• Represent the graph in DFS.
• The order of nodes visited could be: A, B, D, E, C, F, G.

3.IDS (Deep Iterative Search ):

The Deep Iterative Search (IDS) combines Deep Search (DFS) and Wide Search (BFS) to explore a search space when solution depth is unknown. The algorithm performs a series of limited DFS searches in depth, gradually increasing the limit until it finds the solution, starting with a depth of 0.

Example 1:

Here is the following graph: Find J

Represent the graph in IDS.

The order of nodes visited could be:

• It1: A
• It2: A B C D
• It3: A B E F C G H D
• It4: A B E I J

A → B → E → I, J

4. Two-way search

Bidirectional search is a graph or tree exploration technique that reduces the time of the search by simultaneously launching two searches: one from the starting node and the other from the objective node. The algorithm progresses in both directions until the two searches meet in the middle. 

Basic Principle:

•       Two Simultaneous Searches: One search starts from the initial node, and the other one from the target node.

•       Middle Encounter: The algorithm ends when both searches meet a common node, which means that a path has been found.

Benefits:

Two-way search is more efficient than conventional search in large graphs, because it reduces the search space by progressing from both ends.

Example 1:

Find a way between two cities:

Suppose we have to find a path between two cities in a road network, starting from city A and going to city F. The graph of connections is as follows:

•       Represent the graph in Two-way search

Steps of the Two-Way Search:

Departure from A and F:

- A search starts from city A.

- Another search is started simultaneously from city F.

Step 1: Explore neighbours:

From A, one explores its neighbors: B and D.

From F, one explores its neighbours: D and E.

Step 2: Continuation:

The search from A continues from B, while the search from F continues from D.

Meeting:

At this point, the two searches meet at D, a common node between both sides. This means that a path has been found.

Steps of the Two-Way Search:

Result

The path found by the bidirectional search is A –D- F.

UCS (Uniform Cost Search) :

Uniform cost search (UCS) is an uninformed search algorithm used to find the path with the lowest total cost in a weighted graph. Unlike DFS or BFS algorithms, UCS takes into account the costs associated with each movement, thus seeking to minimize the total cost rather than simply the distance to the starting node.

Example:

Imagine a weighted graph where each edge represents a cost:

Imagine a weighted graph where each edge represents a cost:

Objective:

•       Initial node: A

•       Objective node: E

Each edge between nodes is associated with a cost.

Steps of UCS

1. Initialization:
1. Priority file: [(A, 0)] (initial node with cost of 0).
2. Iteration 1:
1. Extract A (cost 0).
2. Explorer B (cost 1), C (cost 3), D (cost 4).
3. Priority queue: [(B, 1), (C, 3), (D, 4)].
3. Iteration 2:
1. Extract B (cost 1).
2. Explore E (cost 1 + 2 = 3).
3. Priority queue: [(C, 3), (D, 4), (E, 3)].
4. Iteration 3:
1. Extract C (cost 3).
2. Explorer E (cost 3 + 1 = 4), but the queue already contains an E with a lower cost, so we don’t update.
3. Priority queue: [(E, 3), (D, 4)].

Iteration 4:

1. Extract E (cost 3), solution found.

è The optimal path found is A B E with a total cost of 3.