0401 FreeCodeCamp Python Certification — Graphs and Trees Review
A graph is a set of nodes (vertices) connected by edges (connections). Each node can connect to multiple other nodes, forming a network.
Graph Traversals
- Breadth-First Search (BFS)
- Uses a queue.
- Explores level by level.
- Finds shortest path in unweighted graphs.
- Depth-First Search (DFS)
- Uses a stack (or recursion).
- Explores a branch fully before backtracking.
- Useful for cycle detection and path finding.
Graph Representations
- Adjacency List
- Each node has a list of its neighbors.
- Space efficient for sparse graphs.
- Easy to iterate over neighbors.
- Adjacency Matrix
- A 2D array where rows and columns represent nodes.
- Space intensive for large graphs.
- Fast to check if an edge exists between two nodes.
Priority Queues
A priority queue is an abstract data type where each element has a priority.
Queues and stacks consider only the order of insertion, while priority queues consider the priority of elements.
Standard queues follow FIFO (First In First Out) and stacks follow LIFO (Last In First Out).
However, in a priority queue, elements with higher priority are served before those with lower priority, regardless of their insertion order.
18 out of 20 questions correct.