Здравствуйте, Шебеко Евгений, Вы писали:

ШЕ>тип узлов и рёбер задать непонятно как

У меня была таже самая проблема -) Не долго думая, написал класс.
Получился направленный граф. Не помню, как я оптимизировал, но помню вставка достаточно быстрая, а удаление всего графа медленное.
Можно ходить по входящим ребрам, по исходящим или по всем сразу.
Еще момент — для некоторых операций (копирования поддеревьев и все другие ф-ии кот. это используют) надо граф предварительно "очистить" (cpd::graph<EdgeData, VertexData>::wash(void)).
Может для вашей задачи подойдет..

Использование:

#include "graph.hpp"

typedef cpd::edge<CMyEdge, CMyNode> joint;
typedef cpd::vertex<CMyEdge, CMyNode> node;
typedef cpd::graph<CMyEdge, CMyNode> graph;

graph g;
node n, *pn;
node::edge_iterator o_it;

pn = g.add_vertex(&n);

for(o_it = pn ->o_begin(); o_it pn ->o_end(); ++o_it);
// идем по исходящим ребрам

g.remove_subtree(pn);

Сам класс:
graph.hpp

/*
 * graph.hpp
 * history:
 * v1.1 2005/04/26, G.Vostrikov
 *  vertex outgoing, incoming edge iterator added,
 *  graph::copy_subtree + graph::wash functions available now
 *  vertex::disconnect bug fixed
 * v1.0 2005/03/30, G.Vostrikov
 *  original
 */

#pragma once

#include <list>
#include <map>

namespace cpd
{
    template<typename EdgeData, typename VertexData>
    class vertex;

    template<typename EdgeData, typename VertexData>
    class graph;
    
    template<typename EdgeData, typename VertexData>
    class edge
    {
    public:
        EdgeData data;
        
        vertex<EdgeData, VertexData>* pred(void) const {return pred_;} // родитель
        vertex<EdgeData, VertexData>* succ(void) const {return succ_;} // наследник
    protected:
        friend class vertex<EdgeData, VertexData>;

        edge(vertex<EdgeData, VertexData>* pred,
            vertex<EdgeData, VertexData>* succ)
            : pred_(pred), succ_(succ) {}

        edge(vertex<EdgeData, VertexData>* pred,
            vertex<EdgeData, VertexData>* succ, EdgeData& d)
            : data(d), pred_(pred), succ_(succ) {}

        virtual ~edge() {}

        vertex<EdgeData, VertexData>* pred_;
        vertex<EdgeData, VertexData>* succ_;
    private:
        edge(const edge& rhs){}
        edge& operator=(const edge& rhs) {return *this;}
    };
    
    template<typename EdgeData, typename VertexData>
    class vertex
    {
    public:
        VertexData data;
        
        virtual edge<EdgeData, VertexData>*
            connect(vertex<EdgeData, VertexData>* target, EdgeData* pdata = 0); // соединить 2 узла
        virtual bool disconnect(vertex<EdgeData, VertexData>* target = 0); // разьединить 2 узла, либо отсоединить узел
        virtual edge<EdgeData, VertexData>* is_connected(vertex<EdgeData, VertexData>* target);
        virtual bool is_connected(void) {return !edges_.empty();}
        
        std::list<edge<EdgeData, VertexData>* > * edges(void) {return &edges_;}

        typedef typename std::list<edge<EdgeData, VertexData>* >::iterator edge_iterator;
        // итератор по исходящим связям
        edge_iterator o_begin(void) {return edges_.begin();}
        edge_iterator o_end(void) {return pred_end_;}
        // итератор по входящим связям
        edge_iterator i_begin(void) {return pred_end_;}
        edge_iterator i_end(void) {return edges_.end();}

    protected:
        friend class graph<EdgeData, VertexData>;
        vertex() : pred_end_(edges_.end()), mark_(0) {}
        vertex(VertexData& d) : data(d), pred_end_(edges_.end()), mark_(0) {}
        vertex(const vertex& rhs) : data(rhs.data), pred_end_(edges_.end()), mark_(0) {}
        vertex& operator=(const vertex& rhs)
        {
            if(this!=&rhs)
                data = rhs.data;
            return *this;
        }
        virtual ~vertex() {disconnect();}

        std::list<edge<EdgeData, VertexData>* > edges_;
        edge_iterator pred_end_;

        // used by graph
        mutable unsigned long mark_;
    };
    
    template<typename EdgeData, typename VertexData>
    class graph
    {
    public:
        graph() {}
        graph(const graph& rhs);
        graph& operator=(const graph& rhs);

        virtual ~graph();
        
        virtual vertex<EdgeData, VertexData>* add_vertex(VertexData* pdata = 0);
        virtual bool remove_vertex(vertex<EdgeData, VertexData>* pvertex);

        virtual void copy(const graph& rhs);
        virtual void clear(void);
        virtual void wash(void) const;

        virtual vertex<EdgeData, VertexData>* copy_subtree(vertex<EdgeData, VertexData>* pvertex);
        virtual void remove_subtree(vertex<EdgeData, VertexData>* pvertex);

        std::list<vertex<EdgeData, VertexData>* > * vertexes(void) {return &vertexes_;}
    protected:
        std::list<vertex<EdgeData, VertexData>* > vertexes_;
    };
        
    template<typename EdgeData, typename VertexData>
        edge<EdgeData, VertexData>*
        vertex<EdgeData, VertexData>::connect(vertex<EdgeData, VertexData>* target, EdgeData* pdata)
    {
        ATLASSERT(target);
        ATLASSERT(this != target);
        
        edge<EdgeData, VertexData>* pedge =
            pdata ? new edge<EdgeData, VertexData>(this, target, *pdata) :
        new edge<EdgeData, VertexData>(this, target);
        
        edges_.push_front(pedge);
        target->pred_end_ = target->edges_.insert(target->pred_end_, pedge);
        
        return pedge;
    }
    
    template<typename EdgeData, typename VertexData>
        bool vertex<EdgeData, VertexData>::disconnect(vertex<EdgeData, VertexData>* target)
    {
        ATLASSERT(this != target);
        
        bool success = false;
        edge_iterator it;
        edge<EdgeData, VertexData>* pedge;
        vertex<EdgeData, VertexData>* pvertex;
        
        if(target)
        {
            if(pedge = is_connected(target))
            {
                if(*pred_end_ == pedge) pred_end_++;
                edges_.remove(pedge);

                if(*target->pred_end_ == pedge) target->pred_end_++;
                target->edges_.remove(pedge);
                delete pedge;
                
                success = true;
            }
        } else // if(target)
        {
            for(it = edges_.begin(); it != edges_.end(); ++it)
            {
                pedge = (*it);
                pvertex = pedge->succ() != this ? pedge->succ() : pedge->pred();
                if(*pvertex->pred_end_ == pedge) pvertex->pred_end_++;
                pvertex->edges_.remove(pedge);
                
                delete pedge;
            }
            
            edges_.clear();
            pred_end_ = edges_.end();
            success = true;
        }
        
        return success;
    }

    template<typename EdgeData, typename VertexData>
        edge<EdgeData, VertexData>*
        vertex<EdgeData, VertexData>::is_connected(vertex<EdgeData, VertexData>* target)
    {
        ATLASSERT(target);
        ATLASSERT(this != target);

        edge_iterator it;
        edge<EdgeData, VertexData>* pedge;

        for(it = edges_.begin(); it != edges_.end(); ++it)
        {
            pedge = (*it);
            if(pedge->succ() == target || pedge->pred() == target)
                return pedge;
        }

        return 0;
    }
    
    template<typename EdgeData, typename VertexData>
        graph<EdgeData, VertexData>::~graph()
    {
        clear();
    }
    
    template<typename EdgeData, typename VertexData>
        vertex<EdgeData, VertexData>* graph<EdgeData, VertexData>::add_vertex(VertexData* pdata)
    {
        vertex<EdgeData, VertexData>* pvertex =
            pdata ? new vertex<EdgeData, VertexData>(*pdata) :
        new vertex<EdgeData, VertexData>;
        
        vertexes_.push_back(pvertex);
        return pvertex;
    }
    
    template<typename EdgeData, typename VertexData>
        bool graph<EdgeData, VertexData>::remove_vertex(vertex<EdgeData, VertexData>* pvertex)
    {
        vertexes_.remove(pvertex);
        delete pvertex;
        return true;
    }

    template<typename EdgeData, typename VertexData>
        void graph<EdgeData, VertexData>::clear(void)
    {
        std::list<vertex<EdgeData, VertexData>* >::iterator it;
        
        for(it = vertexes_.begin(); it != vertexes_.end(); ++it)
            delete (*it);

        vertexes_.clear();
    }

    template<typename EdgeData, typename VertexData>
        void graph<EdgeData, VertexData>::wash(void) const
    {
        std::list<vertex<EdgeData, VertexData>* >::const_iterator v_it;
        
        for(v_it = vertexes_.begin(); v_it != vertexes_.end(); ++v_it)
            (*v_it)->mark_ = 0;
    }

    template<typename EdgeData, typename VertexData>
        void graph<EdgeData, VertexData>::remove_subtree(vertex<EdgeData, VertexData>* pvertex)
    {
        vertex<EdgeData, VertexData>::edge_iterator it;

        while((it = pvertex->o_begin()) != pvertex->o_end())
            remove_subtree((*it)->succ());

        remove_vertex(pvertex);
    }

    template<typename EdgeData, typename VertexData>
        graph<EdgeData, VertexData>::graph(const graph<EdgeData, VertexData>& rhs)
    {
        copy(rhs);
    }

    template<typename EdgeData, typename VertexData>
        graph<EdgeData, VertexData>& graph<EdgeData, VertexData>::operator=(const graph<EdgeData, VertexData>& rhs)
    {
        if(this!=&rhs)
        {
            clear();
            copy(rhs);
        }
        return *this;
    }

    template<typename EdgeData, typename VertexData>
        void graph<EdgeData, VertexData>::copy(const graph& rhs)
    {
        rhs.wash();

        std::list<vertex<EdgeData, VertexData>* >::const_iterator v_it;
        for(v_it = rhs.vertexes_.begin(); v_it != rhs.vertexes_.end(); ++v_it)
            copy_subtree(*v_it);

    }

    template<typename EdgeData, typename VertexData>
        vertex<EdgeData, VertexData>* graph<EdgeData, VertexData>::copy_subtree(vertex<EdgeData, VertexData>* pvertex)
    {
        if(pvertex->mark_)
            return (vertex<EdgeData, VertexData>*)(ULONG_PTR)pvertex->mark_;

        vertex<EdgeData, VertexData>* pv = add_vertex(&pvertex->data);
        pvertex->mark_ = (unsigned long)(ULONG_PTR)pv;

        vertex<EdgeData, VertexData>::edge_iterator e_it;
        for(e_it = pvertex->o_begin(); e_it != pvertex->o_end(); ++e_it)
            pv->connect(copy_subtree((*e_it)->succ()), &(*e_it)->data);

        return pv;
    }

} // namespace cpd