boost graph --- 有向图中两点间所有路径(可处理有环情况)

求有向图中两点间所有路径

问题的本质是遍历图,基本的遍历有BFS和DFS,其实这两种遍历算法boost graph里都有提供,但是如果用其提供的算法得到两点间所有路径,就比较困难,所以下面是我自己实现的算法,一个是DFS的递归实现,另一个是DFS的非递归实现.

DFS 递归版

typedef boost::graph_traits<graphtype>::vertex_descriptor vertex_t;

void AllPaths(vector<vector<vertex_t> >& res, vector<vertex_t> previous, vertex_t curr, vertex_t des){
    for(unsigned int i = 0; i < previous.size(); ++i ){//寻找是否有环
        if(previous[i] == curr){
            return ;
        }
    }
    previous.push_back(curr); //加入路径
    if(curr == des){   //找到一条路径 
        res.push_back(previous);
    }
    typename graph_traits<graphtype>::out_edge_iterator out_i,out_end;
    tie(out_i, out_end) = out_edges(curr, graph_);
    for(; out_i != out_end; ++out_i ){
        vertex_t v = target(*out_i, graph_);
        AllPaths(res, previous, v, des);   
    }
}

递归算法的问题在于递归层次太深的话 会栈溢出,所以工程上不建议使用递归算法.

DFS 非递归版

void AllPaths(vector<vector<vertex_t> >& res, vertex_t start, vertex_t end){
    boost::unordered_map<vertex_t, boost::shared_ptr<std::set<vertex_t> > > visited;
    vector<vertex_t> path;
    typename boost::graph_traits<graphtype>::out_edge_iterator out_i, out_end;
    path.push_back(start);
    vertex_t top = path.back();
    while(!path.empty()){
        tie(out_i, out_end) = out_edges(top, graph_);
        for(; out_i != out_end; ++out_i){
            vertex_t v_tg = target(*out_i, graph_);
            if(!IsExist(visited, top, v_tg)){
                if(!IsExist(path, v_tg)){
                    path.push_back(v_tg);

                    visited[top]->insert(v_tg);
                    top = v_tg;
                    if(v_tg == end){ //找到路径
                        res.push_back(path);
                        path.pop_back();   //回溯
                        top = path.back();
                    }

                }else{
                    path.pop_back();
                    top = path.back();
                }
                break;
            }
        }
        if(out_i == out_end){
            path.pop_back();
            top = path.back();
        }
    }
}


bool IsExist(const vector<vertex_t>& src, vertex_t v){
    vector<vertex_t>::const_iterator iter = src.begin();
    for(; iter != src.end(); ++iter){
        if(*iter == v){
            return true;
        }
    }
    return false;
}
bool IsExist(boost::unordered_map<vertex_t, boost::shared_ptr<std::set<vertex_t> > >& visited, vertex_t s, vertex_t v){
    boost::unordered_map<vertex_t, boost::shared_ptr<std::set<vertex_t > > >::iterator map_iter = visited.find(s);
    if(map_iter == visited.end()){
        boost::shared_ptr<std::set<vertex_t> > vertexs(new set<vertex_t>());
        visited.insert(std::make_pair(s, vertexs));

        return false;
    }else{
        std::set<vertex_t>::const_iterator iter = map_iter->second->find(v);
        if(iter == map_iter->second->end()){
            return false;
        }
        return true;
    }

}

非递归的实现,其实就是用辅助栈来模拟递归,另外还需要记录下来每个点走过的路径