Chinaunix首页 | 论坛 | 博客

编海无涯

首页　| 　博文目录　| 　关于我

wangxx0729

  • 博客访问： 43315
  • 博文数量： 23
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 137
  • 用 户 组： 普通用户
  • 注册时间： 2014-07-21 11:10
个人简介

作为一名计算机专业的白丁，我还在摸索。

文章分类

全部博文（23）

文章存档

2014年（23）

我的朋友
最近访客
推荐博文
相关博文
基本的图算法

分类： C/C++

2014-09-12 19:30:37

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

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

广度优先搜索（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. }

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

Kosaraju：1）对原图进行DFS，2）求解原图的转置，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. }

Tarjan：1）在节点第一次被访问时将其压入栈；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;

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

  23.     std::list<size_t> t;
  24.     size_t t_num;

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

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

  44.     for(size_t i=0;i<vertex_num;++i){
  45.         if(WHITE == root[i].color){
  46.             rst = Tarjan_DFS(DFN,low,i);
  47.         }
  48.     }
  49.     delete [] low;
  50.     delete [] DFN;

  52. }

欧拉回路：欧拉回路就是通过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. };

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

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

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

阅读(537) | 评论(0) | 转发(0) |
0

上一篇：程序员必须知道的10大基础实用算法及其讲解

下一篇：一步一步写算法（之hash表）

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6