当前位置: 动力学知识库 > 问答 > 编程问答 >

c++ - Graph theory - switching tree members

问题描述:

I cannot decide, how to define a graph in C++.

Right now, i have 2-dimensional array:

A - B,D

B - A

C - D

D - A,C

But my troubles comes when i want to switch some "members" of the graph (e.g. D and A). I know i need something like this (which i can manually recognize from the graph):

A - C,D

B - D

C - A

D - A,B

But i actually don't know, how to write the algorithm, which will be able to change order of the 2-D array as it's not so simple as reordering 1D array.

网友答案:

There are two common way to represent a graph in data. The first is a set of pairs where the first and the second are both vertices. If the pair exists, then an edge exists btween the two vertices in the pair:

std::set<std::pair<int, int> > setMyGraph;

The second uses a data structure known as an adjacency matrix. The matrix lists the vertices on the rows and the columns, and holds a true in position (x, y) if a edge exists between the vertex x and vertex y. Otherwise it holds a false.

vector<vector<bool> > vMyGraph;
网友答案:

If you're just looking for a way to represent your graph so you can get your job done, consider boost::graph.

I have to do something mildly similar when I allow the user to drag one vertex onto another to merge them. The way I do it, and you'll probably have to do the same, is to keep track of the edges, store their description in a temporary (I have data attached to the graph), delete one of the vertexes (you'll probably have to do both), and then reconstruct the parts of the graph that need to be reconstructed...but now different.

网友答案:

If you use indices instead of pointers to refer to the neighbors, then you can simply swap A and D and leave the edges unchanged. In other words, change a 2D array from

0 (A) - 1, 3 
1 (B) - 0
2 (C) - 3
3 (D) - 0, 1

to

0 (D) - 1, 3 
1 (B) - 0
2 (C) - 3
3 (A) - 0, 1

Edit: Whether you use pointers or not, your graph is described by a sequence of nodes each containing a value (A, B, C, or D in this example) and references to the neighbor nodes. These references can be either indices into the node array (as in my example) or pointers to the neighbor nodes. Whatever the representation of the neighbor references, you can just swap the values and leave the neighbor references unchanged.

分享给朋友:
您可能感兴趣的文章:
随机阅读: