Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7093283
  • 博文数量: 3857
  • 博客积分: 6409
  • 博客等级: 准将
  • 技术积分: 15948
  • 用 户 组: 普通用户
  • 注册时间: 2008-09-02 16:48
个人简介

迷彩 潜伏 隐蔽 伪装

文章分类

全部博文(3857)

文章存档

2017年(5)

2016年(63)

2015年(927)

2014年(677)

2013年(807)

2012年(1241)

2011年(67)

2010年(7)

2009年(36)

2008年(28)

分类: C/C++

2014-06-21 13:45:01

原文地址:基本的图算法 作者:bl竹子

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

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

点击(此处)折叠或打开

  1. void Graphic::breadth_first_search(void){
  2.     std::list<size_t> queue;
  3.     for(size_t i=0;i<vertex_num;++i){
  4.         if(WHITE != root[i].color)
  5.             continue;
  6.         queue.push_front(root[i].number);
  7.         root[i].color = GRAY;
  8.         while(!queue.empty()){
  9.             vertex* tmp = root[queue.back()].next;
  10.             while(NULL != tmp){
  11.                 if(root[tmp->number].color == WHITE){
  12.                     root[tmp->number].color = GRAY;
  13.                     root[tmp->number].parent = &root[queue.back()];
  14.                     tmp->var .depth = root[queue.back()].var.depth + 1;
  15.                     queue.push_front(tmp->number);
  16.                 }
  17.                 tmp = tmp->next;
  18.             }
  19.             root[queue.back()].color = BLACK;
  20.             BFS_result.push_back(queue.back());
  21.             queue.pop_back();
  22.         }
  23.     }
  24. }

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

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

点击(此处)折叠或打开

  1. void Graphic::depth_first_search(){
  2.   for(size_t i=0;i<vertex_num;++i){
  3.       if(WHITE == root[i].color)
  4.           DFS(i);
  5.   }
  6. }
  7. Graphic::DFS(size_t num){
  8.     DFS_result.push_back(num);
  9.     root[num].color = GRAY;
  10.     Graphic::time += 1;
  11.     root[num].var.time[0] = (unsigned short)Graphic::time;
  12.     vertex *tmp = root[num].next;
  13.     while(0 != tmp){
  14.         if(root[tmp->number].color == WHITE){
  15.             root[tmp->number].parent = &root[num];
  16.             DFS(tmp->number);
  17.         }
  18.         tmp = tmp->next;
  19.     }
  20.     root[num].color = BLACK;
  21.     Graphic::time += 1;
  22.     root[num].var.time[1] = (unsigned short)Graphic::time;
  23. }

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

点击(此处)折叠或打开

  1. std::list<size_t> Graphic::topological_sort(void){
  2.   depth_first_search();
  3.     std::map<size_t,size_t> rst_map;
  4.     for(size_t i=0;i<vertex_num;++i){
  5.         rst_map.insert(std::make_pair(root[i].var.time[1],root[i].number));
  6.     }
  7.     std::list<size_t>rst_list;
  8.     for(std::map<size_t,size_t>::const_iterator iter = rst_map.begin();
  9.         iter != rst_map.end();++iter){
  10.             rst_list.push_front(iter->second);
  11.     }
  12. }

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

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

点击(此处)折叠或打开

  1. Graphic Graphic::transposed_graphic(){
  2.     Graphic rst(edage_num,vertex_num);
  3.     for(size_t i=0;i<rst.vertex_num;++i){
  4.         vertex *tmp = root[i].next;
  5.         while(NULL != tmp){
  6.             size_t num = tmp->number;
  7.             vertex *tmp_node = new vertex;
  8.             tmp_node->number = i;
  9.             tmp_node->next = rst.root[num].next;
  10.             rst.root[num].next = tmp_node;
  11.             tmp = tmp->next;
  12.         }
  13.     }
  14.     return rst;
  15. }
  16. std::list<size_t> Graphic::calculate_cycle_path(const std::list<std::list<size_t> > cycle){
  17.     std::list<size_t> rst_list;
  18.     for(size_t i=0;i<vertex_num;++i){
  19.         bool mark = true;
  20.         if(BLACK == root[i].color){
  21.             for(std::list<std::list<size_t> >::const_iterator iter = cycle.begin();
  22.                 iter != cycle.end();++iter){
  23.                     if(find(iter->begin(),iter->end(),i) != iter->end()){
  24.                         mark = false;
  25.                         break;
  26.                     }
  27.             }
  28.             if (mark)
  29.                 rst_list.push_back(i);
  30.         }
  31.     }
  32.     return rst_list;
  33. }
  34. void Graphic::SCC_Kosaraju(void){
  35.     depth_first_search();
  36.     Graphic tran_root = transposed_graphic();
  37.     std::list<size_t>rst_list = node_sort_by_out_time();
  38.     std::list<size_t>::const_iterator iter = rst_list.begin();
  39.     std::list<std::list<size_t> > cycle;
  40.     while(iter != rst_list.end()){
  41.         tran_root.DFS(*iter++);
  42.         std::list<size_t> tmp = tran_root.calculate_cycle_path(cycle);
  43.         if(!tmp.empty())
  44.             cycle.push_front(tmp);
  45.     }
  46. }

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

点击(此处)折叠或打开

  1. std::list<std::list<size_t> > Graphic::Tarjan_DFS(size_t *DFN, size_t *low,size_t num){
  2.     static std::list<std::list<size_t> > rst;
  3.     static std::list<size_t> stck;
  4.     static size_t index = 0;
  5.     
  6.     DFN[num] = low[num] = index++;
  7.     stck.push_back(num);
  8.     root[num].color = GRAY;

  9.     vertex *tmp = root[num].next;
  10.     while(0 != tmp){
  11.         size_t tmp_num = tmp->number;
  12.         if(root[tmp_num].color == WHITE){
  13.             Tarjan_DFS(DFN,low,tmp_num);
  14.             low[num] = std::min(low[num],low[tmp_num]);
  15.         }
  16.         else if(root[tmp_num].color == GRAY){
  17.             low[num] = std::min(low[num],DFN[tmp_num]);
  18.         }
  19.         tmp = tmp->next;
  20.     }

  21.     std::list<size_t> t;
  22.     size_t t_num;

  23.     if(low[num] == DFN[num]){
  24.         do{
  25.             t_num = stck.back();
  26.             t.push_front(t_num);
  27.             stck.pop_back();
  28.             root[t_num].color = BLACK;
  29.         }while(t_num != num && !stck.empty());
  30.     }

  31.     if(!t.empty())
  32.         rst.push_front(t);
  33.     return rst;
  34. }
  35. void Graphic::SCC_Tarjan(void){
  36.     size_t *low = new size_t [vertex_num];
  37.     size_t *DFN = new size_t [vertex_num];
  38.     std::list<std::list<size_t> > rst;

  39.     for(size_t i=0;i<vertex_num;++i){
  40.         if(WHITE == root[i].color){
  41.             rst = Tarjan_DFS(DFN,low,i);
  42.         }
  43.     }
  44.     delete [] low;
  45.     delete [] DFN;

  46. }

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

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

点击(此处)折叠或打开

  1. enum node_color{WHITE,GRAY,BLACK};
  2. struct vertex{
  3.     size_t number;
  4.     vertex *parent,*next;
  5.     node_color color;
  6.     union{
  7.         size_t depth;
  8.         //enter_time,out_time;
  9.         unsigned short time[2];
  10.     }var;
  11. };

  12. class Graphic{
  13. public:
  14.     Graphic(size_t e_num,size_t v_num,std::list<std::pair<size_t,size_t> >edges)
  15.         :edage_num(e_num),vertex_num(v_num),root(0){
  16.         root = new vertex[vertex_num];
  17.         init_vertex();
  18.         init_edge(edges);
  19.     }
  20.     Graphic(size_t e_num,size_t v_num)
  21.         :edage_num(e_num),vertex_num(v_num),root(0){
  22.         root = new vertex[vertex_num];
  23.         init_vertex();
  24.     }
  25.     Graphic(){}
  26.     ~Graphic(){
  27.         if(0 != root)
  28.             delete [] root;
  29.     }
  30. private:
  31.     void init_vertex(void);
  32.     void init_edge(const std::list<std::pair<size_t,size_t> > &edges);
  33. public:
  34.     void breadth_first_search(void);
  35.     void depth_first_search(void);
  36. public:
  37.     std::list<size_t> topological_sort(void);
  38.     void SCC_Kosaraju(void);
  39.     void SCC_Tarjan(void);
  40. private:
  41.     void DFS(size_t num);
  42.     std::list<std::list<size_t> > Tarjan_DFS(size_t *DFN, size_t *low,size_t num);
  43.     Graphic transposed_graphic(void);
  44.     std::list<size_t> node_sort_by_out_time();
  45.     std::list<size_t> calculate_cycle_path(const std::list<std::list<size_t> > cycle);
  46. private:
  47.     std::vector<size_t> BFS_result;
  48.     std::vector<size_t> DFS_result;
  49. private:
  50.     vertex *root;
  51.     vertex tran_root;
  52.     size_t edage_num;
  53.     size_t vertex_num;
  54.     static size_t time;
  55. };
  56. size_t Graphic::time = 0;
  57. void Graphic::init_vertex(void){
  58.     for(size_t i=0;i<vertex_num;++i){
  59.         root[i].parent = 0;
  60.         root[i].number = i;
  61.         root[i].next = 0;
  62.         root[i].color = WHITE;
  63.         root[i].var.depth = 0;
  64.     }
  65. }

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

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

阅读(466) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~