data structure

Part 4: Modify your implementation to traverse the graph in the posted file BiggieGraph.txt. USE NODE A as the ROOT. In addition to the default output similar to above, determine and print the LENGTH AND SEQUENCE OF THE LONGEST BRANCH in the resulting tree. There are several methods to do this: Method A: Increment a global counter in the first line of traverse, and decrement the global counter on the last line of traverse. Also keep a separate global stack, push when incrementing the counter, pop when decrementing the counter. Also keep track of the max counter value. If a new max is created, print the global stack. This method will print several stacks, each one longer than the previous one, so the last one printed will be the longest path in the tree. Method B: You should be able to omit the global stack if you use the data already pushed onto the function all stack. You can implement this in C using pointers, you just need to (somehow) determine the size of the stack frame, then you can iterate up the stack. Graph 1 Graph 2

"BiggieGraph.txt" posted below:

0100001101110110001011100101100101010011100100101111010101111010011101010010001111111001111010110010 1000101111010100100100101111111110100100000000111100100110101110001000010100100111011111010001000101 0000101001011111010111110011100111000011101111001100001111000010100110000101000100100000000011011110 0000101110000011101100100000010011010001110100100101001011000001110000010111011010100011010010111100 0111010111010011001000101000111001110111010100011000101111000001101010010000000111111000011100011010 0000100000001111101010001000110111100011111011000000000111000100101111010111011100110010111000011111 1111000010110010011100111110110111111101101001110101110101110000101111110010011101010101000101001110 1101100011101111011011110100110111010111000010111010001100110010010101001110111000110100101001101001 0101101100110110001110111010000110111100101001010010100111000111111110101100100010100000010001110010 1110100100100011011101001001000111010100010001001111101000110011101011011001111010110101110001000111 1000001111010000111000010110010100101100001001100100010010010011111000010111011011111000101110011110 1110101010100011000110001100000101111001000111100111111101000111111000100000011011010010000111010100 0010010100000000100101111100101010110000100101100011101000100111000011001000111000110100000110100111 1110010110000010000010110100011000111011000011111000010110001111110111010111001001011110001101100000 1011111111010100110101101011111011011011111101110011010100101110010101110001100010001010000001110001 0011110101010000101000000101001100000111100110110001001011010010101110111101011100001110010001011001 0101010000101011001010011101101111100010011100110100111111011001101000010011011011111011011000110001 0010001101100010000110010011110101001110001101010110010101110110111100010101000001011110010000111100 1001111111100001100011111110101111010101101001110101011001000011101101010011111000110010101111001010 0111001011011010010011110100110000100001101000011101110000110111011011000011110111000000011001001111 1010010110010100111100000100110111111001000101100110111010001101011110010000001001110100111011100111 1010000101001010001100100010110111010110101000001110011101001111100001100101100000001000101011011000 1111101110001110001101010110110010110011111111011111001011101001011001101000000001110011110100101101 0010001110101100111100101000100101100100100100010000010100010000111111111000111010000101011110010000 0100111011011010101000010000110101001111010010101111111010100110010100110011101110011111010100010001 1100001100111101101110100011111000011011101101001101000111111010010111100010100110101111100100010010 0110001010100010011001100101001011111111000001001111010001101110111001001111101100000001011000110111 1110000001000011110000000110101100100101011001100000111111100010111111110110010110010010000011011011 1110111100001010111111111101010110011011111000000011000011110001010110100010111010110110110101110100 0101111100100110010111101100100010101100101001100011000111001010101100101100001111010011001011111001 0100100000001111101000000111000000010010111101100100010000100101011001011000000001000100010110011011 1110011111110001111011011001100001101000010111010111010010010111101110111101001000001011100110101000 0111011111001010101011100010110000111000001110110111100011000100111110011001100010100110000010110110 1011111101010010111011011010000100011101010101110101000010111101001000100100000010011000110110010000 0100111010111100100110110011010110011111101011010001001010100101010100110011010010011011100000000111 1001101111011110001011100110101011100110000000100101110111100100000000010001100010000110011010000000 0000001010110110010010001110110111100011101001111110101010001011100011110101000100010110101101101000 0100101111100001011001011011010001110010011111001011101110010110100111001110011101000110011111101011 1010110100000111110001101110101000111101100000111010010001000101010101100001011111010010011100100100 1011111100010111001110101111100001101010100111111100001001101000010001101100101000100000000001100100 1011011010001011001101110100111000101011000110111010000001010110101101010110110011100101110001001001 0001110001000010100000101001101101000100001000111011101001011011110111010000011111001100110101010001 0010011010100010111101100101111010101100010011001001000110000011011001011001100100100111010011000101 1011100000011011110010110100001111000101100010011011111001001010110001011101010000111101110100010111 0010010100010101000000101000000110100101101101000011111111111111100011110011001101100100100001101100 0010011011111110011010100111011101101101001010111000100101000000000010111011010010000111110101000111 1101001100111111101010001001011011011011110001000001010000011001110001001110010000010010001111100110 0100101110000111111100110000000111101011110101001000111010110100010101110001001111001111111110111100 1110100101000100000101101110000000001111111101010111011110001110100000101001010110111011000000011100 1111001001110000111111101110001111011001000000001011011010110001100110011101110100011010011011010011 1000000111011010010011101010110110001110110110001101010110110010011010001011011100011001110000110100 1001001001011011001100101110110111110100011110101110001100101100001010000011110000001000101001100011 0100101011011000100110001001000010011100010111010000001100111110100000001000101101011010100100001001 1000001000110110111111011011001100010010000110111110000100110010110100000100000110010011111010100001 0011100101011001101011101001000000101101010110011101100000011001110011110101011000101011010110011111 1110111110010110110001010101010000010100001011001011110001110000000101100001110101011001010010110010 0111110010100101100010101101110111111100001010011110000001000000000001111001001010011000101000011100 1011111010010001111001100111110010010011110111000000000110110100100011000011100111110110101111001101 1100001101001010010100101111101001110001000010010111110101011011010010010100001101010110110101000101 1000001101100001110100010100100101000100110010110110111101100000101010010000000011011100010000101100 1100000000000110100011100110010001001001010110101001101000100100010011101100001011111000110000011110 0100010010011110010111001010001111110110100010011001100001001011010001101110000110111111000010000000 1110000111111111011101001111010100001100111110001010110000100101011100101111001100001001111110100000 0001100011111100101111100000101101101010011010100100001000100110000111101010001101100101101000101111 0011111011110101111001010011010110001100110110101100111001010000011010111010001101001001100110101000 1001000110110110010110111111101010100011011100110010011000101110100011111110011101011111100100000011 1100111011110001111110110011011111000000101000000011000000010010100011011001110000100000100011100101 1010011110000111011010011101110110100110110000010100010100000011000001100100011111110101010001100111 0010111011001101000110010101100110001100010011000111001001111001111000110111110000001010001011101110 1000011101001110001101110111001000001111111110110000001111001101011100111001011000001010011100010101 0000001010010011000001111101110101101011000011011000001110001111110111010110110011110110010000100101 1101111001100111111010011001001110111000111111010100001010110000111011100111010100000101110110011101 0000000111001001000000110010011110000101001101101110100010001111111001000101101110001011010100101010 0111010110100101010001000011010101001101100100100100011000101110010110111001001100000000110001111111 1001011100100100101100001111100000100100100011100011000001000111110010110000101011011110001101110100 0011010001100111111101001010000110111010001111011111001111000010001011011100101011100000101010111001 0100000111001010001101011110100010010001101000000101100101000000001010101011010101010000110100010000 0001011101111001101100010001100000100110110101101111001100000000011111110000100111100001110111101010 1001011101111101101010011010110100000111010010010010101010101011110101001111000001010010001000100101 1110111000000001000100001111010000001110011010011110110101100111110100011100110001111101010001110000 1101100011110010100100011101110011110010110001011000010011011100000100101011010000110100101101110110 1100101000110100110110100000011000000110110010010000100101111001110100100011111100010101110111001110 1011110111101000101010100100100010000001101110001000001001001101001100100001010110011110101010010001 1100111101111100111010101001110001101010000100101110110111111100010100100010101111101010110001111111 1100100000100111110001001100000101100000010100011111101110011110110011001010000100110011000100111010 0100001101001101010010011100101010011100111111010000000001110101010100110010000111100000100101001111 0101010000010111111000101101110110111110001001111100111001100100010011101010001000111001110100100110 1101001001000000100000111110010100100000101101011010011100000111110100011000010101001010110101111111 1000010101100000001011100100100101101000110111010011110011101011111000010101110011110111001100111000 1101110011000001110110111010101001010110111101010110011100111010000101111100110101010011001100001001 1000110100100100101111010010010000011110000000110101010011000011000011000011001010100000110011110000 0000101000111100001000111100101101001110010101110000101001100010110001011010110011001111110001101011 1011000000111000001011010001011111010100001000110100011101000110101010010001010001100000001001111001 0110001111010111001111000001110000001101111011100101000001100000001110000110010111010101001110011010 1001000110001110110010100010110110001111000010110011010100010011101110101111011110011011101110011010 1011110010110011110001011111111011000000010100011110001110001000000001010111100110111001101011100101 0011111100100001011101100001011100001100100010011000101011011001100010011101010001011101110111100001 0111011001111000010110100010100010100011001111111010001011111001001111110110001011010111000000010000 1010111011101000001110000111001010100100000101100101001100001001010110001100010011011111000101100000 0100010101001011100110101011011000100100111101000101111001100001011101110101001000110101010110011000 

This is the code we used:

#include

using namespace std;

#include

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 << char(node + 65) << endl;

int target = 0; // index 0 is node A

int size = sizeof(graph) / sizeof(*graph);

while (target < size) // count thru cols in nodes 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

cout << "The stack traversal path" << endl;

traverse(2);

cout << " The resulting tree ";

cout << "Node\t\tParent ";

for (int i = 0; i <= 7; i++)

{

int x = tree[i];

cout << char(i + 65) << "\t\t" << char(x + 65);

cout << endl;

}

//printtree(); function not defined

}