有向图实现

Question

我需要在c++中实现有向图(digraph)，这是我的一项作业，但我遇到了如何表示顶点和边的数据类型的问题。
请问是否有人能提供一个示例或简单的c++类来实现这个问题，以便我可以研究并从中扩展？

我已经谷歌搜寻了一段时间，但我只找到了关于使用Boost或其他库的结果，我只需要一些简单的东西，不依赖于任何库。

谢谢。

- daniels

---

有向图是标准的图论术语。 - Paul Nathan

@Neil：请查看http://en.wiktionary.org/wiki/digraph。 - Greg Hewgill

@Greg 请参阅http://en.wikipedia.org/wiki/Digraphs_and_trigraphs - 但我将删除我的评论。 - anon

嗨，伙计们，事实证明单词可以有两个意思：http://en.wikipedia.org/wiki/Digraph - BlueRaja - Danny Pflughoeft

@Neil：没错，那个词典页面上列出了两个词源，以字为中心的是词源2。 - Greg Hewgill

Answer 1

有两种主要的方式可以使用数据结构来表示有向图：

节点中心。这种方法将每个节点表示为程序中的一个对象，每个节点包含与其相连的其他节点的信息。其他节点可以是仅由一条有向边连接的节点列表。

边缘中心。这种方法将每个边缘表示为程序中的一个对象，每个边缘包含它所连接的节点的信息。在有向图中，每个边缘将有恰好一个“源”和“目标”节点（如果考虑自环，则可能是同一个节点）。这种方法本质上是一个有序对的列表。

根据你正在解决的问题，这两种基本形式中的一种最适合。更具体的算法可能需要向上述基本结构添加更多信息，例如从当前节点可达的所有节点的列表。

- Greg Hewgill

Answer 2

一般来说，有两种直观的表示图的方法：

1. 连接矩阵
2. 链表列表。

每种方法都有其优点和缺点，具体取决于应用程序。

#2将涉及大量指针操作。

#1在进行图形转换时通常更易于使用。

不管哪种方法，你都会得到像这样的东西：

template<typename T>
class node
{
   public:
   T data;
};

矩阵和列表类将指向动态分配的node。

这意味着你将拥有一个graph类和一个node类。

- Paul Nathan

---

连接矩阵仅适用于稠密图，而稠密图相对较少见。您确实需要指定此内容。通常，密集和稀疏表示的用途是互斥的，并且有各种不像列表的列表的稀疏表示。 - Potatoswatter

Answer 3

尝试使用一个 vector< NodeType > 和一个 multimap< NodeType *, EdgeType>。 multimap 不支持下标访问 [ x ]，因此您需要使用 edges.lower_bound()。

或者，一个 map< pair< NodeType *, NodeType * >, EdgeType > 可以帮助查找给定两个节点之间的边。我在一个非常复杂的程序中就是这样做的。

以下是第一种建议的示例：

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;
}

- Potatoswatter

Answer 4

template<class T>
class node
{
public:
    T data;
    vector<node<T>*> edges;
}

您很可能还需要存储一个 list<node<dataType>*>，其中包含所有节点。

- BlueRaja - Danny Pflughoeft

Answer 5

这篇大学论文或许能对你有所帮助。

虽然不是最全面的，但它可以给你一个想法。我发现它非常有用，而且是为了一次演讲而写的，所以没有任何抄袭的风险。

- Skurmedel