Week 6 - Breadth-First Search Flashcards
What is a shortest path problem?
The shortest path problem involves finding the shortest path or minimum distance between two nodes in a graph.
What is a graph?
A graph is a data structure consisting of nodes (vertices) connected by edges (links), used to represent relationships or connections between elements.
What are the neighbours of a node?
The neighbours of a node are the set of nodes directly connected to it.
What are directed edges?
Directed edges are used to represent one way connections within graphs. An undirected edge kind of acts like two directed edges!
How can a graph be implemented in python?
You can represent a graph in python using a dictionary (aka hash table!)
What are some examples of use for the graph data structure.
- Social Networks
- Web pages
- Roads
- Biology
- Computer Networks
- Economics
What is breadth-first search?
Breadth-First Search (BFS) is a search algorithm that explores a graph level by level, starting from a given node and visiting all its neighbors before moving on to their neighbors. It uses a queue to keep track of nodes to visit next, ensuring that nodes are explored in the order of their distance from the starting node.
What is a queue?
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where elements are added at the end and removed from the front.
Why do we keep track of the nodes that have been visited?
Tracking visited nodes is essential in graph traversal algorithms to prevent infinite loops caused by cycles. Without this, the algorithm could repeatedly revisit nodes and get stuck in an endless cycle.
What is the overall time complexity of BFS?
The overall time complexity of Breadth-First Search (BFS) is O(number of nodes + number of edges), as the algorithm must explore each edge at least once and maintains a queue for each node. Adding a node to the queue takes constant time, and doing so for every node contributes O(number of nodes) to the complexity. Also written as O(V + E).
