明升ms88社区

 找回暗码
 注册
明升ms88社区 主页 业界资讯 技能文摘 检查内容

自己着手完成图的BFS和DFS(附完好源码)

2014-2-25 15:24| 发布者: 红黑魂| 检查: 121169| 谈论: 2|原作者: 兰亭风雨|来自: CSDN博客

m88 188bet uedbet 威廉希尔 明升 bwin 明升88 bodog bwin 明升m88.com 18luck 188bet unibet unibet Ladbrokes Ladbrokes casino m88明升 明升 明升 m88.com 188bet m88 明陞 uedbet赫塔菲官网 365bet官网 m88 help
摘要: 图的存储结构 本文的要点在于图的深度优先查找(DFS)和广度优先查找(BFS),因而不再对图的基本概念做过多的介绍,可是要先大致了解下图的几种常见的存储结构。 邻接矩阵 邻接矩阵既能够用来存储无向图,也能够 ...

图的存储结构

    本文的要点在于图的深度优先查找(DFS)和广度优先查找(BFS),因而不再对图的基本概念做过多的介绍,可是要先大致了解下图的几种常见的存储结构。

    邻接矩阵

    邻接矩阵既能够用来存储无向图,也能够用来存储有向图。该结构实际上便是用一个二维数组(邻接矩阵)来存储极点的信息和极点之间的联系(有向图的弧或无向图的边)。其描绘方法如下:

  1. //图的邻接矩阵存储表明  
  2. #define MAX_NUM 20 // 最大极点个数  
  3. enum GraphKind{GY,GN}; // {有向图,无向图}  
  4. typedef struct  
  5. {  
  6.    VRType adj; // 极点联系类型。对无权图,用1(是)或0(否)表明是否相邻;对带权图,则为权值  
  7.    InfoType *info; // 与该弧或边相关信息的指针(可无)  
  8. }ArcCell,AdjMatrix[MAX_NUM][MAX_NUM]; // 二维数组  
  9. typedef struct  
  10. {  
  11.    VertexType vexs[MAX_NUM]; // 极点向量  
  12.    AdjMatrix arcs; // 邻接矩阵  
  13.    int vexnum,arcnum; // 图的当时极点数和弧(边)数  
  14.    GraphKind kind; // 图的品种标志  
  15. }Graph;  
    咱们别离看下面两个图,左面为有向图,右边为无向图


    上面两个图均为无权图,咱们假定存储的时分,V0的序号为0,V1的序号为1,V2的序号为2。。。,且adj为1表明两极点间没有没有衔接,为0时表明有衔接。则有向图的邻接矩阵如下图左面的矩阵所示,无向图的邻接矩阵如下图右边的矩阵所示;


    依据邻接矩阵很简单判别图中恣意两个极点之间连通与否,并能够求出各个极点的度。
    1、关于无向图,调查右边的矩阵,发现极点Vi的度便是邻接矩阵中第i行(或第i列)的元素之和。
    2、关于有向图,因为需求别离计算出度和入读,调查左面的矩阵,发现极点Vi的出度即为邻接矩阵第i行元素之和,入度即为邻接矩阵第i列元素之和,因而极点Vi的度即为邻接矩阵中第i行元素和第i列元素之和。
    很明显,邻接矩阵所占用的存储空间与图的边数或弧数无关,因而适用于边数或弧数较多的稠密图。

    邻接表

    邻接表是图的一种链式存储结构,既适合于存储无向图,也适合于存储有向图。在邻接表中,用一个一维数组存储图中的每个极点的信息,一起为每个极点树立一个单链表,链表中的节点保存依靠在该极点上的边或弧的信息。其描绘方法如下
  1. //图的邻接表存储表明  
  2. #define MAX_NUM 20  
  3. enum GraphKind{GY,GN}; // {有向图,无向图}  
  4. typedef struct   
  5. {  
  6.    int adjvex; // 该弧所指向的极点或边的另一个极点的方位  
  7.    ArcNode *nextarc; // 指向下一条弧或边的指针  
  8.    InfoType *info; // 与弧或边相关信息的指针(可无)  
  9. }ArcNode;// 表结点  
  10. typedef struct  
  11. {  
  12.    VertexType data; // 极点信息  
  13.    ArcNode *firstarc; // 榜首个表结点的地址,指向榜首条依靠该极点的弧或边的指针  
  14. }VNode,AdjList[MAX_NUM]; // 头结点  
  15. struct   
  16. {  
  17.    AdjList vertices;  
  18.    int vexnum,arcnum; // 图的当时极点数和弧(边)数  
  19.    GraphKind kind; // 图的品种标志  
  20. }Graph;  
    仍然以上面的有向图和无向图为例,选用邻接表来存储,能够得到对应的存储方法如下:


    在邻接表上简单找到恣意一个极点的榜首个邻接点和下一个邻接点,可是要断定恣意两个极点之间是否有边或弧需查找两个极点对应的链表,不及邻接矩阵便利。
    很明显,邻接表所占用的存储空间与图的边数或弧数有关,因而适用于边数或弧数较少的稀少图。

    十字链表

    十字链表也是一种链式存储结构,用来表明有向图,它在有向图邻接表的基础上参加了指向弧尾的指针。表明方法如下:
  1. //有向图的十字链表存储表明  
  2. #define MAX_NUM 20  
  3. typedef struct // 弧结点  
  4. {  
  5.   int tailvex,headvex; // 该弧的尾和头极点的方位  
  6.   ArcBox *hlink,*tlink; // 别离为弧头相同和弧尾相同的弧的链域  
  7.   InfoType *info; // 该弧相关信息的指针,可指向权值或其他信息(可无)  
  8. }ArcBox;  
  9. typedef struct // 极点结点  
  10. {  
  11.   VertexType data;  
  12.   ArcBox *firstin,*firstout; // 别离指向该极点榜首条入弧和出弧  
  13. }VexNode;  
  14. struct  
  15. {  
  16.   VexNode xlist[MAX_NUM]; // 表头向量(数组)  
  17.   int vexnum,arcnum; // 有向图的当时极点数和弧数  
  18. }Graph;      
    其思维也很简单了解,这儿不再细说。
    在十字链表中,既简单找到以某个极点为尾的弧,也简单找到以某个极点为头的弧,因而简单求得极点的出度和入度。

    邻接多重表

    邻接多重表也是一种链式存储结构,用来表明无向图,与有向图的十字链表类似,这儿也不再细说,直接给出其表明方法:
  1. //无向图的邻接多重表存储表明  
  2.  #define MAX_NUM 20  
  3.  typedef struct   
  4.  {  
  5.    VisitIf mark; // 拜访符号  
  6.    int ivex,jvex; // 该边依靠的两个极点的方位  
  7.    EBox *ilink,*jlink; // 别离指向依靠这两个极点的下一条边  
  8.    InfoType *info; // 该边信息指针,可指向权值或其他信息  
  9.  }EBox;  
  10.  typedef struct  
  11.  {  
  12.    VertexType data;  
  13.    EBox *firstedge; // 指向榜首条依靠该极点的边  
  14.  }VexBox;  
  15.  typedef struct   
  16.  {  
  17.    VexBox adjmulist[MAX_NUM];  
  18.    int vexnum,edgenum; // 无向图的当时极点数和边数  
  19.  }Graph;  

图的遍历

    图的遍历比树的遍历要杂乱的多,因为图的任一极点都有或许与其他的极点相邻接,因而,咱们需求设置一个辅佐数组visited[]来符号某个节点是否现已被拜访过。图的遍历一般有两种办法:深度优先遍历(BFS)和广度优先遍历(DFS),两种遍历方法的思维都不难了解。下面咱们就以如下图所示的比方来阐明图的这两种遍历方法的基本思维,并用邻接表作为图的存储结构,给出BFS和DFS的完成代码(下图为无向图,有向图的BFS和DFS完成代码与无向图的相同):

    咱们以邻接表作为上图的存储结构,并将A、B、C、D、E、F、G、H在极点数组中的序号别离设为0、1、2、3、4、5、6、7。咱们依据上图所包括的信息,精简了邻接表的存储结构,采纳如下所示的结构来存储图中极点和边的相关信息:

  1. #define NUM 8          //图中极点的个数  
  2.   
  3. /* 
  4. 用邻接表作为图的存储结构 
  5. 在邻接表中,用一个一维数组存储图中的每个极点的信息, 
  6. 一起为每个极点树立一个单链表,链表中的节点保存依靠在该极点上的边或弧的信息 
  7. */  
  8. typedef struct node  
  9. {   //链表中的每个节点,保存依靠在该节点上的边或弧的信息  
  10.     int vertex;          //在有向图中表明该弧所指向的极点(即弧头)的方位,  
  11.                          //在无向图中表明依靠在该边上的另一个极点的方位  
  12.     struct node *pNext;  //指向下一条依靠在该极点上的弧或边  
  13. }Node;  
  14. typedef struct head  
  15. {   //数组中的每个元素,保存图中每个极点的相关信息  
  16.     char data;          //极点的数据域  
  17.     Node *first;        //在有向图中,指向以该极点为弧尾的榜首条弧  
  18.                         //在无向图中,指向依靠在该极点上的榜首条边  
  19. }Head,*Graph;           //动态分配数组保存每个极点的相关信息  

    那么用邻接表来表明上图中各极点间的联系,如下图所示:

    深度优先查找

    深度优先查找(DFS)类似于树的先序遍历(如没有把握图的先序遍历,请移步这儿:http://blog.csdn.net/ns_code/article/details/12977901)。其基本思维是:从图中某个极点v动身,遍历该极点,然后顺次从v的未被拜访的邻接点动身深度优先遍历图中,直到图中一切与v连通的极点都已被遍历。假如当时图仅仅需求遍历的非连通图的一个极大连通子图,则另选其他子图中的一个极点,重复上述遍历进程,直到该非连通图中的一切极点都被遍历完。很明显,这儿要用到递归的思维。

    结合上面的比方来剖析,假定从A点开端遍历该图,依据图中极点的存储联系,会依照下面的过程来遍历该图:

    1、在拜访完极点A后,挑选A的榜首个邻接点B进行拜访;

    2、然后看B的邻接点,因为B的榜首个邻接点A现已被拜访过,故挑选其下一个邻接点D进行拜访;

    3、然后看D的邻接点,因为D的榜首个邻接点B现已被拜访过,故挑选其下一个邻接点H进行拜访;

    4、然后看H的邻接点,因为H的榜首个邻接点D现已被拜访过,故挑选其下一个邻接点E进行拜访;

    5、然后看E的邻接点,因为E的榜首个邻接点B现已被拜访过,那么看其第二个邻接点H,也被拜访过了,E的邻接点现已悉数被拜访过了。

    6、这时退回到上一层递归,回到极点H,相同H的邻接点也都被拜访结束,再退回到D,D的邻接点也已拜访结束,再退回到B,一直退回到A;

    7、因为A的下一个邻接点C还没有被拜访,因而拜访C;

    8、然后看C的邻接点,因为C的榜首个邻接点A现已被拜访过,故挑选其下一个邻接点F进行拜访;

    9、然后看F的邻接点,因为F的榜首个邻接点C现已被拜访过,故挑选其下一个邻接点G进行拜访;

    10、然后看G的邻接点,因为G的临界点都已被拜访结束,因而会退到上一层递归,看F极点;

    11、同理,由F再回退到C,再由C回退到A,这是榜首层的递归,A的一切邻接点也已都被拜访结束,遍历到此结束。


  • 快毕业了,没作业经验,
    找份作业好难啊?
    赶忙去人才芯片公司锻炼吧!!

最新谈论

关于LUPA|人才芯片工程|人才招聘|LUPA认证|LUPA教育|明升ms88社区 ( 浙B2-20090187  

回来顶部