please code in c++ ------------------------ Create a function called impComponen
ID: 3755971 • Letter: P
Question
please code in c++
------------------------
Create a function called impComponent that takes as parameters two lists and returns a bool
of true if two vertices belong to the same component and false otherwise. This function
should run in linear time. Remember, when you are building an adjacency list, you are building the
list in sorted order. To determine if two lists L1 and L2 belong to the same component, if any of
their adjacent vertices, or the vertex itself, belongs to the other list, they are in the same
component. For example, if L1 contains the vertices {1, 4, 6} and L2 contains the vertices {2,
4, 7}, all vertices in L1 and L2 are in the same connected component because they both contain
the vertex 4. (please use this example when coding)
This function prototype is
//if there is a common element in both lists, return true otherwise false
// assumes lists are sorted in ascending order and elements are unique
bool impComponent ( const list<int> &, const list<int> &)
Explanation / Answer
DFS-iterative (G, s): //where G is graph and s is source vertex. let S be stack S.push( s ) // inserting s in stack mark s as visited. while ( S is not empty): // pop a vertex from stack to visit next v = S.top( ) S.pop( ) //push all the neighbours of v in stack that are not visited for all neighbours w of v in Graph G: if w is not visited : S.push( w ) mark w as visited DFS-recursive(G, s): mark s as visited for all neighbours w of s in Graph G: if w is not visited: DFS-recursive(G, w) DFS-iterative (G, s): //where G is graph and s is source vertex. let S be stack S.push( s ) // inserting s in stack mark s as visited. while ( S is not empty): // pop a vertex from stack to visit next v = S.top( ) S.pop( ) //push all the neighbours of v in stack that are not visited for all neighbours w of v in Graph G: if w is not visited : S.push( w ) mark w as visited DFS-recursive(G, s): mark s as visited for all neighbours w of s in Graph G: if w is not visited: DFS-recursive(G, w)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.