问图实现，用于查找两个节点之间的循环、路径、最近路径等。

EN

int main() {

    using namespace GraphUtils;

    Graph<char> graph;

    Node<char> a('a');
    Node<char> b('b');
    Node<char> c('c');
    Node<char> d('d');
    Node<char> e('e');
    Node<char> f('f');

    graph.AddNode(a).AddNode(b).AddNode(c).AddNode(d).AddNode(e).AddNode(f);

    a.AddChild(f).AddChild(d);
    b.AddChild(c).AddChild(a);
    c.AddChild(d);
    e.AddChild(f);
    f.AddChild(b);

    graph.Print();


    if( !PathExist(graph, a, b)) {
        cout << "ERR: a -> b exists" << endl;
    }

    if( !PathExist(graph, a, c)) {
        cout << "ERR: a -> c exists" << endl;
    }

    if( PathExist(graph, a, e)) {
        cout << "ERR: a -> c doesn't exist" << endl;
    }

    if( PathExist(graph, c, e)) {
        cout << "ERR: c -> e doesn't exist" << endl;
    }
    if( !PathExist(graph, e, c)) {
        cout << "ERR: e -> c exists" << endl;
    }
}

#include <iostream>
#include <map>
#include <vector>
#include <queue>


using std::map;
using std::vector;
using std::cout;
using std::endl;
using std::queue;

namespace GraphUtils {

template <typename T>
struct Node {
    T data;
    vector<Node*> children;

    Node() {}
    Node(T input): data(input) {}


    Node& AddChild(Node& input) {
        children.push_back(&input);
        return *this;
    }

};


template <typename T>
bool operator<(Node<T>& lhs, Node<T>& rhs) {
    return (lhs.data < rhs.data);
}


template <typename T>
bool operator==(Node<T>& lhs, Node<T>& rhs) {
    return !(lhs.data < rhs.data || lhs.data > rhs.data);
}


template<typename T>
struct Graph {
    vector<const Node<T>* > nodes;

    Graph& AddNode(const Node<T>& input) {
        nodes.push_back(&input);
        return *this;
    }

    void Print() {

        for(typename vector<const Node<T>* >::const_iterator iter = nodes.begin();
                iter != nodes.end();
                iter++)
        {
            cout << (*iter)->data << ":";

            for(typename vector<Node<T>* >::const_iterator child = (*iter)->children.begin();
                    child != (*iter)->children.end();
                    child++)
            {
                cout << (*child)->data << ", ";

            }

            cout << endl;
        }
    }
};


// using BFS to determine if path exists
template<typename T>
bool PathExist(Graph<T>& graph, Node<T>& a, Node<T>& b) {

    map<const Node<T>* , bool> t_visited;
    queue<Node<T>* > t_queue;

    for(typename vector<const Node<T>* >::const_iterator iter = graph.nodes.begin();
            iter != graph.nodes.end(); iter++)
    {
        t_visited[*iter] = false;
    }

    t_queue.push(&a);

    Node<T>* t_node;
    while(!t_queue.empty()) {

        // get the top object
        t_node = t_queue.front();
        t_queue.pop();

        // set visited
        t_visited[t_node] = true;

        // node doesn't have the == operator
        if(*t_node == b) return true;

        // for each ot it's children
        for(typename vector<Node<T>* >::iterator iter = t_node->children.begin();
                iter !=  t_node->children.end(); iter++)
        {
            // if item has not been visited
            if(!t_visited[(*iter)]) {
                t_queue.push((*iter));
            }
        }
    }

    return false;
}





};