Graph -Adjaceny matrix
1 Answer
Graph -Adjaceny matrix
| Flag | PURGE
Please help me urgently with this question.The code has to be in C.
I am confused how to read the file and store it in a 2d array which may be of varying size depending on the input matrix size.
Given a graph in Adjacency Matrix format. Write a program to compute whether two given vertices of the
graph (vertex i and vertex j) are adjacent or not. The graph has to be read from a file in the following format
–
Sample input file:
0,1,1,0,0
1,0,0,1,1
1,0,0,0,0
0,1,0,0,0
0,1,0,0,0
Values of i & j are to be taken as input using scanf() statement in the program. The output should be printed
to the terminal. You can assume that the number of vertices in the whole graph to be less than 10.
Email me when people comment.
Email me when people comment.
Loading...
An error occurred in subscribing you.
Email me when people comment.
Email me when people comment.
Loading...
An error occurred in subscribing you.
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
For starters Im sure you know that the adjacency matrix is one of the worst ways to represent a graph because of its large memory requirements (n^2).
To determine if a vertex is adjacent to another we need to scan the matrix in the row i and column y, if the value at Matrix[i][j] == 1 then those vertex are adjacent. a common variation to this problem might be in a weighted graph, were, instead of 1 and 0s you have actual numbers representing the cost. that does not seem to be the case here
So the first thing you need to do is to represent the adjacency matrix in memory thats a 2D array.
To dinamycally allocate a 2D array in the following code might do the trick, (please keep in mind Im a CPP programer so the syntax might be a bit off)
Now you have the array, its time to fill it up, please not that new should be replaced with malloc() in the above code to comply with the C ONLY requirement.
Im assuming that your file contains the actual number of vertices and that you have that number stored in a variable already... in case you dont, all you gotta do to get is scan the first line of the file counting the numbers of 'comas' and adding one to it
Ok so now you have a 2D array filled from the info on th HDD all that is left is to read i and j from the console and ouput the result
Thats pretty much it, most of the code is C++ all you gotta do is replace cout, with pritnf, and cin with scanf, also the string tokenization used an STL vector that you might need to replace with a buch of calls to strtok().
- Red October 21, 2014I hope you get the gist, an apologies for the code it was written straight into the comment box without double checking if the syntax was ok