C++ 有向图实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2156920/
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
Directed graph implementation
提问by daniels
I need to implement a digraph(Directed graph) in c++ as part of a homework and I'm having some issues with how to represent the vertices and edges data types.
Can anybody please point me to a example or a simple c++ class that implements this so I can study it and extend from there?
我需要在 C++ 中实现一个有向图（有向图）作为作业的一部分，我在如何表示顶点和边数据类型方面遇到了一些问题。
任何人都可以指点我一个例子或一个简单的c++类来实现这个，这样我就可以研究它并从那里扩展？
I've googled for a bit but I only found results about using Boost or other libraries, I just need something simple that doesn't rely on any library.
我用谷歌搜索了一下，但我只找到了关于使用 Boost 或其他库的结果，我只需要一些不依赖任何库的简单东西。
Thank you.
谢谢你。
回答by Greg Hewgill
There are two major ways of representing digraphs with data structures:
用数据结构表示有向图有两种主要方式：
Node centric. This method represents each nodeas an object within your program, and each node contains information about other nodes it links to. The other nodes can be as simple as a list of nodes where there exists a directed edge between the current node and the target node.
以节点为中心。此方法将每个节点表示为程序中的一个对象，每个节点都包含有关它链接到的其他节点的信息。其他节点可以像节点列表一样简单，其中在当前节点和目标节点之间存在有向边。
Edge centric. This method represents each edgeas an object within your program, and each edge contains information about which nodes it connects. In a digraph, each edge will have exactly one "source" and "destination" node (which may be the same node if you're considering self-loops). This method is essentially a list of ordered pairs.
边缘为中心。此方法将每条边表示为程序中的一个对象，并且每条边都包含有关它连接哪些节点的信息。在有向图中，每条边将只有一个“源”和“目标”节点（如果您考虑自环，这可能是同一个节点）。这个方法本质上是一个有序对的列表。
Depending on the problem you're solving, one of these two basic forms will end up being most appropriate. More specific algorithms might need to add more information to the above basic structures, such as for example a list of all nodes reachable from the current node.
根据您要解决的问题，这两种基本形式中的一种最终将是最合适的。更具体的算法可能需要向上述基本结构添加更多信息，例如从当前节点可到达的所有节点的列表。
回答by Paul Nathan
Loosely, there are 2 straightforward ways of representing graphs:
松散地，有两种简单的表示图形的方法：
- Connection Matrix
- List of Lists.
- 连接矩阵
- 列表列表。
Each has advantages/disadvantages, depending on the application.
每个都有优点/缺点，具体取决于应用程序。
#2 will involve a lot of pointer fiddling.
#2 将涉及大量的指针摆弄。
#1 is often easier to use when doing graph transformationss.
#1 在进行图形转换时通常更容易使用。
In either one, you're going to have something like this:
在任何一种情况下，你都会有这样的事情：
template<typename T>
class node
{
public:
T data;
};
And the matrix and list of list classes will be pointing to dynamically allocated node's.
并且列表类的矩阵和列表将指向动态分配node的。
The implication is that you will have a graphclass and a nodeclass.
这意味着您将有一个graph班级和一个node班级。
回答by Potatoswatter
Try a vector< NodeType >with a multimap< NodeType *, EdgeType>.
尝试vector< NodeType >使用multimap< NodeType *, EdgeType>.
multimapdoesn't support subscripting [ x ]so you'll need to use edges.lower_bound()instead.
multimap不支持下标，[ x ]因此您需要edges.lower_bound()改用。
Alternatively, a map< pair< NodeType *, NodeType * >, EdgeType >can help look for an edge given two nodes. I used exactly that in one pretty heavy-duty program.
或者，amap< pair< NodeType *, NodeType * >, EdgeType >可以帮助查找给定两个节点的边。我在一个非常繁重的程序中使用了它。
Here's an example for the first suggestion:
这是第一个建议的示例：
struct NodeType {
int distance;
NodeType( int d ) { distance = d; }
};
struct EdgeType {
int weight;
NodeType *link;
EdgeType( int w, NodeType *l ) { weight = w; link = l }
};
vector< NodeType > nodes;
nodes.reserve( 3 );
nodes.push_back( NodeType( 0 ) );
nodes.push_back( NodeType( 0 ) );
nodes.push_back( NodeType( 0 ) );
multimap< NodeType *, EdgeType > edges;
edges.insert( make_pair( &nodes[0], EdgeType( 4, &nodes[2] ) ) );
edges.insert( make_pair( &nodes[0], EdgeType( 1, &nodes[1] ) ) );
edges.insert( make_pair( &nodes[2], EdgeType( 2, &nodes[0] ) ) );
for ( multimap< NodeType *, EdgeType >::iterator iter = edges.lower_bound( &nodes[1] ),
end = edges.upper_bound( &nodes[1] ); iter != end; ++ iter ) {
cerr << "1 connects to " << iter->second.link - nodes.begin() << endl;
}
回答by BlueRaja - Danny Pflughoeft
template<class T>
class node
{
public:
T data;
vector<node<T>*> edges;
}
You will most likely also want to store a list<node<dataType>*>of all the nodes.
您很可能还想存储list<node<dataType>*>所有节点中的一个。
回答by Skurmedel
This university papermight help you.
这篇大学论文可能对你有帮助。
It's not the most complete, but it gives you an idea perhaps. I found it rather useful, it's also for a lecture so there is no risk of copying anything one shouldn't.
它不是最完整的，但它可能会给你一个想法。我发现它相当有用，它也用于讲座，因此没有复制任何不应该复制的内容的风险。
