定向图实现 [英] Directed graph implementation

问题描述

我需要在c ++中实现一个有向图（定向图）作为作业的一部分，我有一些问题，如何表示顶点和边缘数据类型。

任何人都可以点我到一个例子或一个简单的c ++类实现这个，所以我可以研究它，并从那里延伸？

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?

我已经google了一下，但我只找到关于使用Boost或其他库的结果，我只需要一个不依赖任何库的简单的东西。

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.

谢谢。

推荐答案

具有数据结构的二合字母：

There are two major ways of representing digraphs with data structures:

以节点为中心。此方法将每个节点表示为程序中的对象，每个节点都包含有关其链接的其他节点的信息。其他节点可以像在当前节点和目标节点之间存在有向边的节点列表一样简单。

Node centric. This method represents each node as 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 表示为程序中的对象，每个边都包含有关其连接的节点的信息。在有向图中，每个边缘将具有恰好一个源和目的地节点（如果你考虑自循环，它可以是相同的节点）。这个方法本质上是一个有序对的列表。

Edge centric. This method represents each edge as 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.

这篇关于定向图实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！