Discuss graph representation, Breadth-first search and Depth-first search. Use examples to highlight pros and cons.
Graph Representation : You can represent a graph in many ways. The two most common ways of representing a graph is as follows:
Adjacency matrix
An adjacency matrix is a VxV binary matrix A. Element Ai,j is 1 if there is an edge from vertex i to vertex j else Ai,jis 0.
Note: A binary matrix is a matrix in which the cells can have only one of two possible values - either a 0 or 1.
The adjacency matrix can also be modified for the weighted graph in which instead of storing 0 or 1 in Ai,j, the weight or cost of the edge will be stored.
In an undirected graph, if Ai,j = 1, then Aj,i = 1. In a directed graph, if Ai,j = 1, then Aj,i may or may not be 1.
Adjacency matrix provides constant time access (O(1) ) to determine if there is an edge between two nodes. Space complexity of the adjacency matrix is O(V2).
Adjacency list
The other way to represent a graph is by using an adjacency list. An adjacency list is an array A of separate lists. Each element of the array Ai is a list, which contains all the vertices that are adjacent to vertex i.
For a weighted graph, the weight or cost of the edge is stored along with the vertex in the list using pairs. In an undirected graph, if vertex j is in list Ai then vertex i will be in list Aj.
The space complexity of adjacency list is O(V + E) because in an adjacency list information is stored only for those edges that actually exist in the graph. In a lot of cases, where a matrix is sparse using an adjacency matrix may not be very useful. This is because using an adjacency matrix will take up a lot of space where most of the elements will be 0, anyway. In such cases, using an adjacency list is better.
A sparse matrix is a matrix in which most of the elements are zero, whereas a dense matrix is a matrix in which most of the elements are non-zero.
If a matrix is dense it's optimal to use adjacency matrix whereas if the graph is sparse adjacency list is preferred over adjacency matrix
Breadth first search - BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.
As the name BFS suggests, you are required to traverse the graph breadthwise as follows:
Depth First search - The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.
Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path, you move backwards on the same path to find nodes to traverse. All the nodes will be visited on the current path till all the unvisited nodes have been traversed after which the next path will be selected.
This recursive nature of DFS can be implemented using stacks.
The basic idea is as follows:
Pick a starting node and push all its adjacent nodes into a
stack.
Pop a node from stack to select the next node to visit and push all
its adjacent nodes into a stack.
Repeat this process until the stack is empty. However, ensure that
the nodes that are visited are marked. This will prevent you from
visiting the same node more than once. If you do not mark the nodes
that are visited and you visit the same node more than once, you
may end up in an infinite loop.
1 a) BFS(Breadth First Search) uses Queue data structure for finding the shortest path.
b) DFS(Depth First Search) uses Stack data structure.
2. a) BFS can be used to find single source shortest path in an unweighted graph, because in BFS, we reach a vertex with minimum number of edges from a source vertex.
b) In DFS, we might traverse through more edges to reach a destination vertex from a source
3. a) BFS is more suitable for searching verteces which are closer to the given source
b) DFS is more suitable when there are solutions away from source
4. a) BFS considers all neighbors first and therefore not suitable for decision making trees used in games or puzzles.
b) DFS is more suitable for game or puzzle problems. We make a decision, then explore all paths through this decision. And if this decision leads to win situation, we stop.
Discuss graph representation, Breadth-first search and Depth-first search. Use examples to highlight pros and cons.
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms for a graph in Java.(Can be any graph, just an example of DFS and BFS is sufficient) If it cannot be done for a graph, then just an example of DFS and BFS are enough.
From the given graph discover the structure of the graph using 1. breadth first search(BFS) a. depth first search(DFS) b. Show the steps and techniques used for each method (20 points) From the given graph discover the structure of the graph using 1. breadth first search(BFS) a. depth first search(DFS) b. Show the steps and techniques used for each method (20 points)
Depth-first Search vs Breadth-first Search Please explain the difference!
Consider the following directed graph for each of the problems: 1. Perform a breadth-first search on the graph assuming that the vertices and adjacency lists are listed in alphabetical order. Show the breadth-first search tree that is generated. 2. Perform a depth-first search on the graph assuming that the vertices and adjacency lists are listed in alphabetical order. Classify each edge as tree, back or cross edge. Label each vertex with its start and finish time. 3. Remove all the...
Write the pseudocode of the Depth First Search Algorithm DFS(G) using adjacencymatrix representation of the graph G. What is the running time of your pseudocode? Specification: start from the psedocode discussed in class and do only the modifications needed for adjacency-matrix graph representation. Below is the pseudocode discussed in class:
State whether each of the statements is true or false. Depth-first search is optimal. Depth-limited search can never find an optimal solution. Breadth-first search never reaches a dead end. Depth-limited search has a greater space complexity compared to breadth-first search. Breadth-first search expands deepest node first.
(a) Compute the Breadth-First Search tree for the following graph, using node a as the root. Please use alphabetic order to make choice when you have multiple choices. You only need to show the tree without showing the steps. (b) What is the height of the tree? Currently I have a tree of depth 3, a as the root, (b,g,h,k) as depth 1, (c,j) under b (f) under g (e) under k for depth 2, and (d) under c for...
Question 3 1 pts Select all of the following that are true: Breadth-First Search only adds each vertex to the queue once. Breadth-First Search generally uses more space compared to Depth-First search. Breadth-First Search may not find the shortest path for an unweighted graph if the graph contains a cycle. At any time during Breadth-First Search, the queue holds at most two distinct dist values from all vertices in
discrete 2 question 31 For Esercises 25.28, write the nodes in a breadth first search of the graph for Exercises 21 the node specified 25、 26, g 20. In the computer network in the accompanying figure, the same message is to be broade Dribe ( 21-24 28. e 27. to nodes 4.Е. F and G. One way to do this is to find the shortest path from C to send out multiple copies of the same message. A more etficient...