Lets see if I can properly convey the question in my head.
I've been beating my head against the wall for the past few hours trying to figure out how I might go about solving my current problem.
I have two parallel arrays, such that a[I] and b[I] each store one half of a set. So if set 'I' stores (1,5), then a[I] would be 1 and b[I] would be 5.
Say there are 5 vertices, so we're building a matrix from (0,0) to (4,4).
For each set, a 1 is placed in the adjaceny matrix.
EG:
(0,1) (1,2) (2,4) (3,2) (4,0) (1,3) would have the follow matrix
0 1 0 0 1
1 0 1 1 0
0 1 0 1 1
0 1 1 0 0
1 0 1 0 0
Given that I will display this from left to right, top to bottom, I need to search for each set in order. The problem I'm running into is the sets aren't in numerical order, and the (4,0) and (0,4) represent the same adjacency. I'm having a hell of a time coming up with an algorithm that will search check all possibility of set combinations before deciding if that particular set exists, before moving on to the next column and checking that.
I have no functional code, but some pseudo-code that might be of use. I also am not necessarily looking for code answers. Even just a walk through of how this would be accomplished at a pseudo level would be great, I'm sure I can write the code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
|
// Display the adjacency matrix
void Graph::display() const
{
int a[] = {0,1,2,3,4,1};
int b[] = {1,2,4,2,0,3};
cout << fName << ":\n\n" << "Adjacency Matrix" << endl;
//actually build the matrix
//int i is going to represent the row we are currently building
for (int i =0; i < numVert; i++){
//int j is going to represent the column.
for (int j = 0; j < numVert; j++){
//right now, we're filing out the 0 row. What numbers (if any) are adjacent to 0)
if (a[i] == i or b[j] == i) {
//perfect. We know that ONE of these values is 0, which means whatever values is the other half the set is adjacent.
//stuck on how to move forward with completing this row..
}
}
}
}
|