Fringe Node visited Fringe Size Search depth Fringe Node visited Fringe Size Sea

Question

Fringe

Node visited

Fringe Size

Search depth

Fringe

Node visited

Fringe Size

Search depth

1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 while S is not empty V : S.pop() if v is not labeled as discovered: label v as discovered for all edges from v to w in G.adjacentEdges(v) do S.push(w) Figure 2 Depth First Search DFS (Method 1) s stack s.push(initial node) add initial node to visited while s is not empty: Figure 1 Set all nodes to not visited" q new Queue(); q.enqueue (initial node); wile q empty do V s.peek() if for all E(v,u) there is one unvisited u: x q.dequeue(); mark u as visited if ( x has not been visited) s.push(u) visited[x] true; // Visit node x else for every edge (x, y) /* we are using all edges) if (y has not been visited) .pop q.enqueue(y) // Use the edge (x,y)!!! Figure 3 Depth First Search (Method 2) Figure 2: Breath First Search (BFS)

Explanation / Answer

Memory Consumption of BFS and DFS algorithms

In the above tree diagram the branchig factor is 4 and the search depth is 3 so the BFS uses more memory than the DFS method because at each level of execuion in DFS there will always be not more than 3 nodes ..where as in BFS from node F to the node U will always be in memory as shown figure.

Table as shown above

fringe node visited fringe size search depth 0 node A 0 1 node C ,D,E B 3 2 node G,H,E F 3 3

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.