C Programming The data.txt file contains an adjacency matrix in the following fo
ID: 3778695 • Letter: C
Question
C Programming
The data.txt file contains an adjacency matrix in the following format:
A,B,C,D,E,F
0,0,0,1,1,0
0,0,1,0,0,0
0,0,0,0,0,1
0,0,0,1,0,0
1,1,0,0,0,0
0,0,0,0,0,1
where the first row is a header row indicating the names of the nodes.
Using the above matrix, if we were to construct a tree of maximum depth 5, to search for a path from node A to another node, it would look like the following (assuming we do not remove cycles from the tree):
Search Tree
Depth 0: A
/
Depth 1: D E
/ /
Depth 2: D A B
/ /
Depth 3: D D E C
/ / /
Depth 4: D D A B F
/ / /
Depth 5: D D D E C F
Write a program that processes an adjacency matrix and looks for a path using breadth first search between two nodes at a maximum depth. It should work with any properly formed input file, not just the one above. The goal is to search for a given node from a starting point. Requirements:
You should pass the file name, the start node index, the destination node index, and the maximum depth to search as command line arguments (in that order). It should look something like:
$ ./a8 data.txt 0 5 4
When you parse the above command line options, the file is data.txt, the start node is index 0, the destination node is index 5, and the maximum depth to search is 4. This corresponds to a search for F, starting at A. The index for each node is simply the node’s index in the first row.
After reading in the adjacency matrix, the program should print it in the format shown in example output.
The program does not need to remember the path from the start to the destination.
The program should print the node names as it searches until it reaches the destination node or finishes searching the maximum depth. If it does not find the node within that maximum depth it will print that the no path exists.
Search each level left-to-right.
If the source or destination node does not exist (i.e. there are only 6 nodes in the adjacency list and you try to search for node index 10), the program should print an error and exit.
You do not need to build a search tree, though you are free to do so. You can do it simply by processing the adjacency matrix like we went over in class.
Explanation / Answer
#include <iostream>
#include <fstream>
using namespace std;
typedef struct node{
int data;
node* link;
} node;
node* begin(node* linkHead){
return (node*)linkHead -> link;
}
node* end(node* linkHead){
node* x = linkHead;
while(x->link != NULL){
x = x->link;
}
return x;
}
bool empty(node* linkHead){
if(linkHead == NULL){
return(true);
}
}
node* insert ( node* x , int value){
node newnode;
newnode.data = value;
newnode.link = x -> link;
x -> link = &newnode;
return x;
}
node* remove (node* linkHead, int value){
if( linkHead = NULL)
return NULL;
node*x = linkHead;
node*prev = x->link;
x=x->link;
while(x->link != NULL){
if(x->data == value){
prev ->link = x->link;
delete x;
x = prev;
prev = x->link;
x = x->link;
}
}
}
int main(){
ifstream fin("data1.txt");
ofstream fout("adjacencylist.txt");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.