U302 SAC Notes Flashcards
What is BFS?
A traversal algorithm that visits all neighbours of the current node at the same time (LEVEL BY LEVEL APPROACH)
How does BFS work?
1) It starts from a starting vertex, enqueues it into a queue, and marks it as visited.
2) Then, it dequeues a vertex from the queue, visits it, and enqueues all its unvisited neighbors into the queue.
3) This process continues until the queue is empty.
Advantages/Applications of BFS
Applications:
- shortest path
- Maze
Advantages:
- easy to implement
- level by level approach is more efficient
- guarantee that every node in the graph is visited, so sol is def found
What is DFS and what ADT does it use?
Depth first search is a traversal algorithm that fully explores a single pathway, going all the way down, then backtracking to the other pathways until the entire graph has been traversed
What is Prim’s algorithm used for?
Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a WEIGHTED, UNDIRECTED, graph.
What ADT does prims use?
Min priority queue, to determine which edge should be connected next (greedy approach- lowest cost edge)
What is Dijikstra’s Algorithm
Algorithm that uses a greedy approach to find the shortest paths between one node andALL THE OTHER NODES in a WEIGHTED, DIRECTED graph that are NON-NEGATIVE.
Why doesn’t Dijikstra’s work on negative weights?
Since Dijkstra follows a Greedy Approach, once a node is marked as visited it cannot be reconsidered even if there is another path with less cost or distance. This issue arises only if there exists a negative weight or edge in the graph.
What is the concept of relaxation?
Updating the path distance values
What is Bellman-Ford’s used for?
Single source shortest path problem for weighted, directed graphs, and can work with negative weights.
What does WARSHALL’S algorithm find?
Warshall’s Algorithm finds the transitive closure of a graph (whether a path exists between two nodes.)
What is Floyd-Warshall’s algorithm used for?
Finds the shortest path for all pairs of nodes in the graph.
The algorithm checks if a path through an intermediate vertex offers a shorter distance between two nodes.
What is dynamic programming?
The algorithm is first broken down into sub-problems and then the sub-problems are optimised to find the overall solution
What is backtracking
generating possible solutions to a problem and then going back and regenerating a part of the solution when it reaches a dead end
What is a greedy algorithm?
One that picks the best/most optimal option or solution at each step/iteration
Advantages of BFS
- Simple to implement
- Uses a level by level approach, so is more efficient
- Guarantees that all the nodes in the graph are visited so the solution is found
Advantages of DFS
1) Memory efficient
2) time efficient
Disadvantages of BFS
2) memory intensive
3) slower for large number of nodes compared to DFS
Disadvantages of DFS
1) Not guaranteed to find solution, can potentially keep looping forever
2) may not find the SHORTEST path immediately
