Representing an adjacency matrix/list

Question

I'm having a hard time thinking of an appropriate data structure to use to represent an adjacency matrix for an undirected graph.

I want to be able to take the nodes from these graphs and insert them into random positions in arrays, and then "score" the arrays based on how well they've managed to keep the adjacent nodes apart. i.e if node A and node B are connected in my graph, and the array places them next to each other, +1 would be added to the array's score, with the lowest scoring array being the best.

So what would be the best data structure to use to represent a collection of nodes, and the neighbouring nodes of each one in the collection?

Answer 1

If I understand your question which I do not think it really clear. For an adjacency matrix, I think the best way to go is an Array. You can access each positions in O(1) and since it is an undirected graph, it should be easy to create. see graph below

        0 --- 1------5---6
        | \    \     |  /
        |  \    \    | /
        2   3----4---7

            0 1 2 3 4 5 6 7
          -----------------
        0 | 0 1 1 1 0 0 0 0
        1 | 1 0 0 0 1 1 0 0
        2 | 1 0 0 0 0 0 0 0
        3 | 1 0 0 0 1 0 0 0
        4 | 0 1 0 1 0 0 0 1
        5 | 0 1 0 0 0 0 1 1
        6 | 0 0 0 0 0 1 0 1
        7 | 0 0 0 0 1 1 1 0
          ------------------

You can implement your matrix like so and perform whatever operation you want on it. And all that matters is that if a location is not 0 then the graph is connected and you can just pick the highest value for whatever you are doing.