DISCRETE QUIZ (Terminologies only!)

still study the shit

Graph Traversal

refers to the process of visiting vertices and edges in a graph in s systematic manner Traversal is essential in computer science as it forms the basis for solving many real-world problems, such as searching, pathfinding, and network analysis.

Algorithm

is a step-by-step procedure used to systematically explore all the nodes (vertices) and edges of a graph, defines a clear set of rules for visiting nodes to achieve a specific goal, such as finding a path, determining connectivity, or analyzing relationships within the graph.

Depth-First Search (DFS)

explores as far as possible along one branch before backtracking.
It uses a stack (either explicitly or through recursion) to keep track of nodes to visit next.

uses a stack to manage vertices:

Analogy: Exploring a maze by following one path until you reach a dead end, then backtracking to try another route.

Breadth-First Search (BFS)

explores all neighbors of a node first before moving to nodes at the next level. ensures that all nodes at a distance of n from the starting node are visited before any nodes at a distance of n + 1.

It uses a queue to maintain the order of nodes to visit.
Analogy: Visiting all nearby locations in a city before exploring areas further away.

Maze Solving, cycle detection and topological sorting

Applications of DFS

Maze-solving

can find a path from the start to the end in a maze by exploring one possible route at a time.
Backtracking allows it to handle dead ends efficiently.

Cycle Detection

In undirected graphs, DFS can detect cycles by checking if a node has been visited and is not the direct parent.

Topological Sorting

organizes tasks with dependencies in a linear order.
Example: Course scheduling, where prerequisites dictate the order of courses.

Web crawling, social media connections, shortest path in unweighted graphs

Application of BFS

BFS use cases

Navigation systems: Find the shortest route in city maps.

Social network analysis: Discover the shortest connection between two people.

Level-wise processing: Analyze nodes level by level, e.g., finding all employees at the same management level.

Choose BFS

Choose DFS

Web Crawling

search engines use BFS to crawl web pages, starting from a webpage systematically visits all connected links

Social Media Connections

Finding mutual friends or suggesting people you may know

Breadth First Search

What does BFS mean?

Depth First Search

What does DFS mean?

stacking

What does DFS use?

what does BFS mean?