有向图实现

使用数据结构表示有向图有两种主要方式:

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

. 此方法表示每个 作为程序中的对象,每个边都包含有关其连接的节点的信息。在有向图中,每条边都有一个“源”和“目标”节点(如果考虑自循环,则可能是同一个节点)。该方法本质上是一个有序对的列表。

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

大致来说,有两种直观的图形表示方法:

1. 连接矩阵
2. 清单清单。

#2将涉及大量的指针篡改。

在任何一种情况下,您都会遇到如下情况:

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

node

这意味着你将有一个 graph 节点 班级。

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

这 university paper 也许对你有帮助。

这不是最完整的,但它可能会给你一个想法。我发现它相当有用,它也是一个讲座,所以没有风险复制任何人不应该。

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

您很可能还希望存储一个 list<node<dataType>*>