基本的图算法

本文主要是对图的一些基本算法进行总结，涉及的算法有：广度优先搜索（BFS）、深度优先搜索（DFS）、拓扑排序、强连通分量（Kosaraju、Tarjan）以及欧拉回路等问题。

广度优先搜索（BFS）：BFS的特点是其搜索过的节点形成一颗广度优先树，每个节点到这棵树的根节点的距离叫做深度。BFS搜到的路径是最短路径，这里的最短路径是指经历的节点数目。BFS算法一般会用到队列作为节点的存储结构，其实现的时间复杂度为O(V+E)。其代码为：

void Graphic::breadth_first_search(void){
    std::list<size_t> queue;
    for(size_t i=0;i<vertex_num;++i){
        if(WHITE != root[i].color)
            continue;
        queue.push_front(root[i].number);
        root[i].color = GRAY;
        while(!queue.empty()){
            vertex* tmp = root[queue.back()].next;
            while(NULL != tmp){
                if(root[tmp->number].color == WHITE){
                    root[tmp->number].color = GRAY;
                    root[tmp->number].parent = &root[queue.back()];
                    tmp->var .depth = root[queue.back()].var.depth + 1;
                    queue.push_front(tmp->number);
                }
                tmp = tmp->next;
            }
            root[queue.back()].color = BLACK;
            BFS_result.push_back(queue.back());
            queue.pop_back();
        }
    }
}

注：在我们的算法中，图的存储方式为邻接矩阵表。

深度优先遍历（DFS）：DFS有两个主要特点，即：深度优先搜索形成的不再是一棵树，而是深度优先森林、节点的发现时间和完成时间具有括号性。之所以形成优先森林，是因为在进行深度优先遍历时，到达某个节点的源节点不唯一。具有括号性是指：如果开始搜索记为“（”，结束搜索记为“）”，则左右的括号都适当的嵌套在一起。通过括号性，我们可以更好的理解深度优先遍历的过程。利用这两个特性，DFS有很多应用，例如：判断图中是否有环、拓扑排序等的。下面是DFS的代码：

void Graphic::depth_first_search(){
　　for(size_t i=0;i<vertex_num;++i){
　　    if(WHITE == root[i].color)
　　        DFS(i);
　　}
}
Graphic::DFS(size_t num){
    DFS_result.push_back(num);
    root[num].color = GRAY;
    Graphic::time += 1;
    root[num].var.time[0] = (unsigned short)Graphic::time;
    vertex *tmp = root[num].next;
    while(0 != tmp){
        if(root[tmp->number].color == WHITE){
            root[tmp->number].parent = &root[num];
            DFS(tmp->number);
        }
        tmp = tmp->next;
    }
    root[num].color = BLACK;
    Graphic::time += 1;
    root[num].var.time[1] = (unsigned short)Graphic::time;
}

拓扑排序：拓扑排序就是将有向图中节点间的关系转化为线性关系。拓扑排序可以用于查看图中是否存在环，如果存在环则无法进行拓扑排序。但是，在下面的程序中，我们假设图中不存在环。对于无向图来说，因为节点间的关系是对称的，所以节点不能进行拓扑排序。拓扑排序其实很简单，其过程如下：每次从节点集合中选出一个节点A，且A的入度为0，然后修改以A为使点的节点的入度，按上述过程依次进行，直到节点集合为空或者不存在拓扑排序为止。这个过程可以通过DFS的括号性来表示，即：拓扑排序就是将节点按着完成时间进行降序排序。代码如下：

std::list<size_t> Graphic::topological_sort(void){
　　depth_first_search();
    std::map<size_t,size_t> rst_map;
    for(size_t i=0;i<vertex_num;++i){
        rst_map.insert(std::make_pair(root[i].var.time[1],root[i].number));
    }
    std::list<size_t>rst_list;
    for(std::map<size_t,size_t>::const_iterator iter = rst_map.begin();
        iter != rst_map.end();++iter){
            rst_list.push_front(iter->second);
    }
}

强连通分量：强连通分量是指，在有向图中任意两点之间都存在连通边，即：如果u、v在同一个强连通分量红，则（u,v）（v,u）都存在。这个我们同样可以通过DFS进行求解。求解强连通分量的方法很多，常用的有三种：Kosaraju、Tarjan和Gabow。下面简要介绍着三种算法，然后给出相应代码。

Kosaraju：1）对原图进行DFS，2）求解原图的转置，3）按着1）中DFS完成时间的递减次序对2）中的转置图进行DFS，每生成一颗深度优先树就求到了一个强连通分支。具体证明见算法导论（证明的关键在于连通分支不存在环）。代码如下：

Graphic Graphic::transposed_graphic(){
    Graphic rst(edage_num,vertex_num);
    for(size_t i=0;i<rst.vertex_num;++i){
        vertex *tmp = root[i].next;
        while(NULL != tmp){
            size_t num = tmp->number;
            vertex *tmp_node = new vertex;
            tmp_node->number = i;
            tmp_node->next = rst.root[num].next;
            rst.root[num].next = tmp_node;
            tmp = tmp->next;
        }
    }
    return rst;
}
std::list<size_t> Graphic::calculate_cycle_path(const std::list<std::list<size_t> > cycle){
    std::list<size_t> rst_list;
    for(size_t i=0;i<vertex_num;++i){
        bool mark = true;
        if(BLACK == root[i].color){
            for(std::list<std::list<size_t> >::const_iterator iter = cycle.begin();
                iter != cycle.end();++iter){
                    if(find(iter->begin(),iter->end(),i) != iter->end()){
                        mark = false;
                        break;
                    }
            }
            if (mark)
                rst_list.push_back(i);
        }
    }
    return rst_list;
}
void Graphic::SCC_Kosaraju(void){
    depth_first_search();
    Graphic tran_root = transposed_graphic();
    std::list<size_t>rst_list = node_sort_by_out_time();
    std::list<size_t>::const_iterator iter = rst_list.begin();
    std::list<std::list<size_t> > cycle;
    while(iter != rst_list.end()){
        tran_root.DFS(*iter++);
        std::list<size_t> tmp = tran_root.calculate_cycle_path(cycle);
        if(!tmp.empty())
            cycle.push_front(tmp);
    }
}

Tarjan：1）在节点第一次被访问时将其压入栈；2）遇到已在栈中的元素时，记录此节点，并进行出栈操作，直到找到记录的节点为止，此为一个连通分量。代码如下；

std::list<std::list<size_t> > Graphic::Tarjan_DFS(size_t *DFN, size_t *low,size_t num){
    static std::list<std::list<size_t> > rst;
    static std::list<size_t> stck;
    static size_t index = 0;

    DFN[num] = low[num] = index++;
    stck.push_back(num);
    root[num].color = GRAY;

    vertex *tmp = root[num].next;
    while(0 != tmp){
        size_t tmp_num = tmp->number;
        if(root[tmp_num].color == WHITE){
            Tarjan_DFS(DFN,low,tmp_num);
            low[num] = std::min(low[num],low[tmp_num]);
        }
        else if(root[tmp_num].color == GRAY){
            low[num] = std::min(low[num],DFN[tmp_num]);
        }
        tmp = tmp->next;
    }

    std::list<size_t> t;
    size_t t_num;

    if(low[num] == DFN[num]){
        do{
            t_num = stck.back();
            t.push_front(t_num);
            stck.pop_back();
            root[t_num].color = BLACK;
        }while(t_num != num && !stck.empty());
    }

    if(!t.empty())
        rst.push_front(t);
    return rst;
}
void Graphic::SCC_Tarjan(void){
    size_t *low = new size_t [vertex_num];
    size_t *DFN = new size_t [vertex_num];
    std::list<std::list<size_t> > rst;

    for(size_t i=0;i<vertex_num;++i){
        if(WHITE == root[i].color){
            rst = Tarjan_DFS(DFN,low,i);
        }
    }
    delete [] low;
    delete [] DFN;

}

欧拉回路：欧拉回路就是通过G的每条边仅一次，但可以访问每个节点多次。我们看到欧拉回路就是强连通分量的一个子集，只是在强连通分量上加了一个限制条件，即：强连通分量中的每个节点的入度和出度必须相同（具体证明就不说啦）。其实，欧拉回路也就是一笔画的问题。我们仅需按着上述算法求出强连通分量，然后判断其中节点的入度是否等于出度即可，代码就省略了:)。

下面是，本文代码的一个整体框架，也就是一个类，只给出了类的大方法和上面没有实现的代码，如下：

enum node_color{WHITE,GRAY,BLACK};
struct vertex{
    size_t number;
    vertex *parent,*next;
    node_color color;
    union{
        size_t depth;
        //enter_time,out_time;
        unsigned short time[2];
    }var;
};

class Graphic{
public:
    Graphic(size_t e_num,size_t v_num,std::list<std::pair<size_t,size_t> >edges)
        :edage_num(e_num),vertex_num(v_num),root(0){
        root = new vertex[vertex_num];
        init_vertex();
        init_edge(edges);
    }
    Graphic(size_t e_num,size_t v_num)
        :edage_num(e_num),vertex_num(v_num),root(0){
        root = new vertex[vertex_num];
        init_vertex();
    }
    Graphic(){}
    ~Graphic(){
        if(0 != root)
            delete [] root;
    }
private:
    void init_vertex(void);
    void init_edge(const std::list<std::pair<size_t,size_t> > &edges);
public:
    void breadth_first_search(void);
    void depth_first_search(void);
public:
    std::list<size_t> topological_sort(void);
    void SCC_Kosaraju(void);
    void SCC_Tarjan(void);
private:
    void DFS(size_t num);
    std::list<std::list<size_t> > Tarjan_DFS(size_t *DFN, size_t *low,size_t num);
    Graphic transposed_graphic(void);
    std::list<size_t> node_sort_by_out_time();
    std::list<size_t> calculate_cycle_path(const std::list<std::list<size_t> > cycle);
private:
    std::vector<size_t> BFS_result;
    std::vector<size_t> DFS_result;
private:
    vertex *root;
    vertex tran_root;
    size_t edage_num;
    size_t vertex_num;
    static size_t time;
};
size_t Graphic::time = 0;
void Graphic::init_vertex(void){
    for(size_t i=0;i<vertex_num;++i){
        root[i].parent = 0;
        root[i].number = i;
        root[i].next = 0;
        root[i].color = WHITE;
        root[i].var.depth = 0;
    }
}

void Graphic::init_edge(const std::list<std::pair<size_t,size_t> > &edges){
    for(std::list<std::pair<size_t,size_t> >::const_iterator iter = edges.begin();
        iter != edges.end();++iter){
            vertex *tmp_vertex = new vertex;
            tmp_vertex->next = root[iter->first].next;
            tmp_vertex->number = iter->second;
            root[iter->first].next = tmp_vertex;
    }
}

本文出自：http://blog.chinaunix.net/uid/28311809/abstract/1.html