Please turn the following algorithm into a C++ program. Part 1: Implement the st
ID: 3819303 • Letter: P
Question
Please turn the following algorithm into a C++ program.
Part 1: Implement the stack traversal for the pseudocode template given below, and produce identical output (stack traversal path and the tree array). Traverse Graph 1 and USE NODE C as the ROOT.
Part 2: Modify your implementation to traverse GRAPH 2 shown below. USE NODE A as the ROOT. Output the stack traversal path and the tree array.
// A recursive solution for a stack traversal of a graph
/*
Each instance of traverse keeps track of one node’s adjacency list. The CALL to and RETURN from traverse, are similar to PUSH and POP.
//A B C D E F G H
};
static bool[] visited = {false, false, false, false, false, false, false, false};
// the resulting tree. Each node's parent is stored
// "Push" C
init target to 0 // index 0 is node A
while(not at end of node’s list) // count thru cols in node’s row
{
if(target is node’s neighbor and target is unvisited)
{
next target
}
B H C A D (G D E F Graph 1 Graph 2 E (C)1111( )Explanation / Answer
Part 1:
This is your c++ code for the given pseudo code
#include<iostream>
using namespace std;
#include<iostream>
using namespace std;
// the graph adjacency matrix
static int graph[8][8] = {
{0,1,1,0,0,0,0,0}, //A
{1,0,1,0,0,0,0,0}, //B
{1,1,0,1,0,1,0,0}, //C
{0,0,1,0,1,0,0,0}, //D
{0,0,0,1,0,1,0,0}, //E
{0,0,1,0,1,0,1,1}, //F
{0,0,0,0,0,1,0,0}, //G
{0,0,0,0,0,1,0,0}, //H
// A B C D E F G H
};
// where I've been
static bool visited[] = {false, false, false, false, false, false, false, false};
// the resulting tree. Each node's parent is stored
static int tree[] = {-1, -1, -1, -1, -1, -1, -1, -1};
void traverse(int node)
{
visited[node] = true;
cout<<node<<endl;
int target = 0; // index 0 is node A
int size = sizeof(graph)/sizeof(*graph);
while(target < size) // count thru cols in node’s row
{
if(graph[node][target] == 1 && visited[target] == false)
{
tree[target] = node;
traverse(target); // this is like a push
}
target++;
}
return; // this is like a pop
}
int main()
{
// "Push" C
traverse(2);
//printtree(); function not defined
}
Part 2:
Changes:
Please replace the adjacency matrix with the new matrix.
// the graph adjacency matrix
static int graph[8][8] = {
{0,1,1,1,0,0,1,0}, //A
{1,0,1,0,1,0,1,0}, //B
{1,1,0,0,0,1,0,1}, //C
{1,0,0,0,0,1,0,0}, //D
{0,1,0,0,0,0,0,1}, //E
{0,0,1,1,0,0,1,1}, //F
{1,1,0,0,0,1,0,1}, //G
{0,0,1,0,1,1,1,0}, //H
// A B C D E F G H
};
And replace the main by the following main method:
int main() //main method for graph B
{
// "Push" A
traverse(0);
//printtree(); function not defined
}
//Everything else remains same.
I hope this is what you needed. Please note that I found no definition for printtree() method so the method remains unimplemented. In case you need more information, please feel free to comment below.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.