C++ 邻接表图表示的实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14133115/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implementation of an adjacency list graph representation
提问by Somebody
I have just started with the graph theory. I can't figure out how to code adjacency list using linked lists. for example, if I have this graph (undirected):
我刚刚开始学习图论。我不知道如何使用链表对邻接表进行编码。例如，如果我有这个图（无向图）：
A--------B
| /|\
| / | \
| / | \
| / | \
| / | \
| / | \
| / | \
C E-------D
How do I code it? I know how to do it using adjacency matrix, but how to code it using adjacency list and linked lists (c++)?
我该如何编码？我知道如何使用邻接矩阵来做到这一点，但是如何使用邻接表和链表（c++）对其进行编码？
回答by Yuushi
An adjacency list is just a vector/array of lists. Each element in the graph is an element in the array, and any edge is added to the it's adjacency list. Thus it looks something like:
邻接列表只是列表的向量/数组。图中的每个元素都是数组中的一个元素，任何边都被添加到它的邻接表中。因此它看起来像：
A -> {B, C}
A -> {B, C}
B -> {A, C, D, E}
B -> {A, C, D, E}
C -> {A, B}
C -> {A, B}
D -> {B, E}
D -> {B, E}
E -> {B, D}
E -> {B, D}
So we start with something like std::vector<std::list<vertex>>. However, we can do better than this, because verticies are unique, hence we can utilize a map. Furthermore, a vertex can only appear in an edge list once, so we modify it to std::map<vertex, std::set<vertex>>.
所以我们从类似的东西开始std::vector<std::list<vertex>>。但是，我们可以做得比这更好，因为顶点是唯一的，因此我们可以使用map. 此外，一个顶点只能在边列表中出现一次，因此我们将其修改为std::map<vertex, std::set<vertex>>。
So to start with, something like:
因此，首先，例如：
struct vertex
{
//
};
class undirected_graph
{
private:
std::map<vertex, std::set<vertex>> graph_container;
public:
void add_vertex(const vertex& v) { //add a vertex to the map }
void add_edge(const vertex& v, const vertex& u) { //look up vertex in map and add to the vertex adjacency list }
//Other methods
//...
};
回答by Potatoswatter
An adjacency list would just be a set of objects representing the edges of the graph.
邻接表只是表示图边的一组对象。
struct edge {
node *nodes[2];
edge( node *a, node *b ) {
if ( a < b ) { // define canonical order of edges for undirected graph
nodes[0] = a;
nodes[1] = b;
} else {
nodes[0] = b;
nodes[1] = a;
}
}
};
A linked list doesn't sound particularly practical; usually you would define an ordering of edges and put them in a std::setor std::map.
链表听起来不是特别实用；通常你会定义一个边的顺序并将它们放在 a std::setor 中std::map。
bool operator< ( edge const &lhs, edge const &rhs ) {
if ( lhs.nodes[0] < rhs.nodes[0] ) return true;
if ( rhs.nodes[0] < lhs.nodes[0] ) return false;
return lhs.nodes[1] < rhs.nodes[1];
}
typedef std::set< edge > graph;
There are many ways to do this, it's hard to suggest anything more without knowing what you intend to do with the graph.
有很多方法可以做到这一点，如果不知道您打算对图表做什么，就很难提出更多建议。
