图的相关概念及遍历办法概述ITeye - 亚美娱乐

图的相关概念及遍历办法概述ITeye

2019年03月05日15时04分48秒 | 作者: 鹏涛 | 标签: 极点,邻接,相关 | 浏览: 1996

表:极点V1到其它各极点的最短途径表

从图中能够看出,极点V1到V4的途径有3条(V1,V2,V4),(V1,V4),(V1,V3,V2,V4),其途径长度别离为15,20和10,因而,V1到V4的最短途径为(V1,V3,V2,V4)。

那么怎么求带权有向图的最短途径长度呢?能够运用迪杰斯特拉(Dijkstra)算法。

 

图(graph)是 一种比线性表、树更为杂乱的数据结构。在线性表中,数据元素之间呈线性联络,即每个元素只要一个直接前驱和一个直接后继。在树型结构中,数据元素之间有明 显的的层次联络,即每个结点只要一个直接前驱,但可有多个直接后继,而在图结构中,每个结点即可有多个直接前驱,也可有多个直接后继,因而,树结构是图结 构的一种特别景象。当一个树结构中答应同一结点呈现在不同分支上时,该树结构实际上就是一个图结构。图的最早运用能够追溯到十八世纪数学家欧拉(EULer)运用图处理了闻名的哥尼斯堡桥的问题,为图在现代科学技术领域的运用奠定了根底。

一、图的根本概念

1、图的界说

图是一种数据结构,图和树相同能够用二元组表明。它可界说为Graph=(V,R)其间,V={x|x∈datatype},R={VR},VR={ x,y |P(x,y)∧(x,y∈V)}。在图中,数据元平素称为极点(Vertex),V是极点的非空有穷调集;R是边(弧)的有穷调集。VR是两个极点之间的联络调集。极点之间联络可用序偶对来表明。若 x,y ∈VR,则〈x,y 表明从x到y有一条弧(arc,或称又向边),且称x为弧尾(tail)或初始点(initial node),称y为弧头(Read)或终端点(terminal node),此刻的图称为有向图(digraph)。若 x,y ∈VR,必有 y,x ∈VR即VR是对称的,以无序对(x,y)替代这两个有序对,表明x和y之间的一条边(edge),此刻的图称为无向图(undigraph)。谓词P(x,y)表明从x到y有单向通路或其他信息。从逻辑上看,图是由极点和边组成,边反映出极点之间的联络。

2、图的根本术语

不考虑结点的自返圈,即结点到其本身的边,若〈V1,V2〉或〈V1,V2〉是图的一条边,则V1≠V2,而且也不答应一条边在图中重复呈现。

(1)彻底图

在一个有n个极点的图中,若每个极点到其他(n-1)个极点都连有一条边,则图中有n个极点且有n*(n-1)/2条边的图称为彻底图。任一个具有n个极点的有向图,其最大边数为n*(n-1).

(2)邻接点、相关边

关于无向图G=(V,E),若(V1,V2)∈E,则称V1和V2互为邻接点(adjacent),即V1和V2相邻接,而边(V1,V2)则是与结点V1和V2“相相关的边”。在有向图G=(V,A)中,若 V1,V2 ∈A,则称结点V1邻接到结点V2,结点V2邻接于V1,而边〈V1,V2〉是与结点V1,V2相相关的。

(3)极点的度、入度、出度

极点的度(degree)是和V相相关的边的数目,计为TD(V).在有向图G=(V,A)中,假如弧 V1,V2 ∈A,则以V1为头的弧的数目称为V1的入度(indegree),记为ID(V1);以V1为尾的弧的数目称为V1的出度(outdegree),,记为OD(V1);极点的度为TD(V1)=ID(V1)+OD(V1).

(4)途径、回路

无向图G=(V,E)中,从极点V到极点V’的途径(Path)是一个极点序列(V=Vi0,Vi1,Vi2,……,Vim=V’),其间(Vij-1,Vij)∈E,1 =j =m.假如是有向图,则途径也是有向的,极点序列满意(Vij-1,Vij)∈E,1 =j =n,途径长度是途径上的边或弧的数目。榜首个极点和最终一个极点相同的途径称为回路或环(cycle),序列中极点不重复的称为简略途径。除了榜首个极点和最终一个极点外,其他极点不重复的回路,称为简略回路或简略环。

(5)子图

假设有两个图G={V,{E}}和G’={V’,{E’}},假如V’包含于V,E’包含于E,则称G’是G的子图。

(6)连通和强连通

在无向图G中,假如从极点V到极点V’有途径,则称V和V’是连通的。假如关于图G中恣意两个极点Vi,Vj ∈V都是连通的,则称为G是连通图(connected graph).连通重量指的是无向图中极大连通子图。在有向图G中,假如关于每一对Vi,Vj∈V,Vi Vj,从Vi到Vj和从Vj到Vi都存在途径,则称G是强连通图。有向图中极大强连通子图称作为有向图G的强连通重量。

(7)生成树

一个连通图的生成树,它含有图中悉数极点,但只要足以构成一棵树的n-1条边。

(8)权、网

在图的边或弧上,有时标有与它们相关的数,这种与图的边或弧相关的数称作权(Weight)。这些权能够表明从一个极点到另一个极点的间隔或价值。这种带权的图常称作网(network)。

 

二、图的存储结构

1、邻接矩阵表明法

邻接矩阵是表明极点之间相邻联络的矩阵。设G=(V,E)是具有n个极点的图,由G的邻接矩阵是具有如下性质的n阶方阵其界说为:

                1   若 i,j 或 j,i ∈E

    A[i,j]=

              0     反之

这一n*n的方阵,可凭借二维数组作为存储结构。将邻接矩阵中的0,1还成权值,就是 图的邻接矩阵。无向图的邻接矩阵是对称矩阵,极点vi的度是邻接矩阵中第i行(或第i列)的元素1之和。有向图的邻接矩阵纷歧定是对称矩阵;极点vi的出 度是邻接矩阵中第i行元素之和,入度是邻接矩阵中第i列的元素之和。用邻接矩阵表明有向图所需的存储空间为n*n位。对无向图,因为其对称性,仅需存入下 三角(或上三角)的元素,故有n个极点的无向图仅需n(n+1)/2存储空间。用邻接矩阵表明有n个极点的图,测验其边的数目时,必须按行、列逐次测验, 故需O(n*n)次。经过邻接矩阵可简略断定极点间有无边(弧),简略核算极点的度(出度、入度);缺陷是所占用空间只和极点个数有关,和边数无关,在边 数较少时,空间糟蹋较大。一般在极点数较少且边数稠密时运用邻接矩阵。

2、邻接表

邻接表是为了战胜邻接矩阵在图为稀少图时的空间糟蹋大的这个缺陷而提出的。邻接表是顶 点的向量结构和边(弧)的单链表结构的调集,每个极点结点包含两个域,将n个极点放在一个向量中(成为次序存储的结点表);一个极点的一切邻接点链结成单 链表,该极点在向量中有一个指针域指向其榜首个邻接点。邻接表结构: 极点结点:vexdata  | frist   adjvex  |  info  | next   

其间,vexdata是极点数据,firstarc是指向该极点榜首个邻接点的指针,adjvex是邻接点在向量表中的下标,info是邻接点的信息,next是指向下一邻接点的指针。

       对无向图,简略求各极点的度;边表中结点个数是边数的两倍。对有向图,简略求极点的出度;若求极点的入度则不简略,要遍历整个表。为了求极点的入度,有时 可设逆邻接表(指向某极点的邻接点链接成单链表)。所谓逆邻接表就是对图中的每个极点i树立一个单链表,把被i邻接的极点放在一个链表中,即边表中寄存的 是入度边而不是出度边。一般在处理稀少矩阵时用邻接表。

构建一个图的邻接表

struct node                  /*单链表中结点结构 */

{

int  vertex;               /*极点编号*/

struct node    * next       /*指针域*/

 };     
struct headnode               /*数组中元素的结构*/

{

int  vert;                /*极点编号*/

   struct  node   * link       /*指针域*/

};       

为了便利,先给出一个将极点b加入到极点a的邻接链表的函数:
struct  headnode   * linkup (a, b, head);
int  a, b;
struct  headnode   * head;
{
   struct node      * p;
   while(head- vertex!  = a)    /*找到编号为a的极点*/
    {       
      head = head+1;
      p = head- link;
    }
   while( (p!  =NULL) ( p- vertex !  =b ))
       p =p- next          /*查编号为b的极点是否为a的链接极点*/
    if  (p = =NULL)           /*假如未查到*/

    {

         p = (struct  node * )malloc(sizeof(struct  node));   // 拓荒新节点
        p- vertex = b;                  /*将b放入*/
         p- next = head- link;          /*指针从头定向*/
         head- link =p;                 /*a指向b*/
         return(head);
      }

}

结构邻接表的函数为:
  struct headnode  *adjlist(d, n)
  int    n;
  int    d[ ];

{

struct  headnode head[100] ;
     struct node     * q, * p ;
     int    i,vl;
     for(i=0; i i++ )
     {
       head[i].vert=d[i];     /*为每个极点树立一个衔接*/
        head[i].link=NULL;      /*下一个指针先置空*/

 printf (“inputlinked  list  of \ n”); /*输入和此极点相连的极点*/

 scanf (“%d”, vl);

while (vl =0)         /*若此数值为有用/*
{
   p= (struct node * ) malloc(sizeof(struct node));    /*拓荒新节点*/
   p- vertex=vl;        /*放入极点编号*/
   p- next = ead[i].link;/*从头将指针定向*/
   head[i].link=p;
   scanf(“%d”, vl);   /*再输入下一个相连的极点编号*/
 }

}

   return (head);

}
以上函数回来值为邻接表的首地址。

3、十字链表

十字链表(orthogonallist)是有向图的一种链式存储结构,能够看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中对应于有向图中的每一条弧和每个极点的结构如下:

极点结点:data | firstin| firstout

弧结点: tailvex |headvexz | hlink | tlink

在极点结点中有三个域:data域存储和极点相关的信息,如极点称号等;firstin和firstout为两个链域,别离指向以该结点为弧头和弧尾的榜首个结点。为了存取便利,极点一般选用次序存储办法,存储在一维数组中。在弧结点中有四个域:尾域(tailvex)和头域(headvex)别离表明弧尾和弧头这两个极点在图中的的编号,链域hlink指向弧头相同的下一条弧,而链域tlink指向弧尾相同的下一条弧。若加上与弧相关的其他信息,则需求界说更多的域空间。在十字链表中,既简略找到以Vi为头的弧,也简略找到以Vi为尾的弧,因而简略求得极点Vi的入度和出度。

4、邻接多重图

邻接多重图(adjacencymultlist)是无向图的一种存储结构。在邻接表中每一条边的两个结点(Vi,Vj)别离在第i个和第j个 链表之中,这给图的某些操作带来不便利。例如在图的运用中需求对已被查找过的边作记号或对一条边进行操作入删去等等。此刻,需求找到表明同一条边的两个顶 点,因而,对无向图进行这类操作时,选用邻接多重表作为存储结构更为适合。在邻接多重表中,图的每条边只用一个结点表明。

其结点结构如下:mark | ivex |ilink | jvex | jlink  

其间,mark为标志域,用以符号该条边是否已被拜访;ivex和jvex为该边依靠的两个极点;ilink和jlink别离为指向依靠于ivex和jvex下一条边的指针。

每个极点也能够用一个结点表明:data |firstedage

data域存储和极点有关的信息,firstedage指示榜首条依靠于该定点的边。

在邻接多重表中,一切依靠于同一极点边都串联在同一链表中,因为每条边依靠于两个极点,所以每个边结点一起链接在两个链表中。

5、边集数组

带权图的另一种存储结构是边集数组,用边集数组表明带权图 时列出每条边的起、始极点及依靠于这两个极点的边上的权,边集数组一般可用一个二维数组别离存储依靠于每条边的两端点,边上的权值用一个一维数组存储。在 边集数组表明中,数组中对应的列下标表明同一弧的极点及权值。它适用于一些以边为主的操作。这一存储结构相同适用于无向图。

 

 

一、概念。
图: 是一种杂乱的非线性数据结构。
图的二元组界说:

  图 G 由两个调集 V 和 E 组成,记为:
  G=(V, E)  其间: V 是极点的有穷非空调集,
  E 是 V 中极点偶对(称为边)的有穷集。

  一般,也将图 G 的极点集和边集别离记为 V(G) 和 E(G) 。 E(G) 能够是空集。若 E(G) 为空,则图 G 只要极点而没有边。

有向图: 若图 G 中的每条边都是有方向的,则称 G 为有向图 (Digraph) 。
无向图: 若图 G 中的每条边都是没有方向的,则称 G 为无向图 (Undigraph) 。
彻底图:若无向图中的每个极点之间存在着一条边,有向图中的每两个定点之间都存在着方向相反的两条边,则称此图为彻底图。
稠密图: 当一个图挨近彻底图时,则称它为稠密图。 
稀少图:当一个图含有较少边数(即e n(n-1),双小于号表明十分小于的意义)时,则称它为稀少图。
简略图:图中每条边的极点均不相同。
邻接点:
   有向图:假如 u, v ∈ E, 则称v为u的邻接点,u为v的逆邻接点。边 u, v 与极点u和v相相关,从u动身的边称为u的出边或邻接边,而指向极点u的边称为u的入边或逆邻接边。
   无向图:假如(u, v)∈ E, 则称u与v互为邻接点。
极点的度、入度与出度:
  依靠与某极点v的边数 称为度;
  在有向图中,极点v的 入度 指以极点为结尾的边的数目。
                       出度 指以极点开始点的边的数目;
  无向图中出度入度持平。
通路或途径:由m+1个极点与m条边替换构成的一个序列。
环路:如途径的榜首个极点和最终一个极点相同,称之为环路。
可达重量:有向图中,若极点s到v有一条通路,称v是从s可达的。关于s,从s可达的一切极点的调集叫可达重量。
连通图:无向图中,若一个极点到另一个极点有途径,则称这2个极点是连通的。假如图中恣意2极点都是连通的,则称该图是连通图。
连通重量:指无向图的极大连通子图。
权:与图中边有关的实数。
带权图或网:边上具有权值的图。

强连通重量(有向图):极点s在图G中的可达重量 与 s在镜像图R(G)中的可达重量的交集。

最小生成树:从图中的不同极点或从同一极点按不同的优先搜素进程能够得到不同的树。而关于一个连

  通网(连通带权图)来说,生成的树不同,每棵树的价值(树中每条边上权值之和)也或许不同,价值最小

  的生成树为图的最小生成树。

 

二、笼统数据类型
  ADT Graph{
    数据目标D:具有相同性质的数据元素的调集。
    数据联络R:R{ u,v |(u,v∈D)}。
    根本操作:
     1   int getType();//回来图的类型
     2   int getVexNum();//回来图的极点数
     3   int getEdgeNum();//回来图的边数
     4   Iterator getVertex();//回来图的一切极点
     5   Iterator getEdge();//回来图的一切边
     6   void remove(Vertex v);//删去一个极点v
     7   void remove(Edge e);//删去一条边e
     8   Node insert(Vertex v);//增加一个极点v
     9   Node insert(Edge e);//增加一条边e
    10   boolean areAdjacent(Vertex u, Vertex v);//判别极点u、v是否邻接,即是否有边从u到v
    11   Edge edgeFromTo(Vertex u, Vertex v);//回来从u指向v的边,不存在则回来null
    12   Iterator adjVertexs(Vertex u);//回来从u动身能够直接抵达的邻接极点
    13   Iterator DFSTraverse(Vertex v);//对图进行深度优先遍历
    14   Iterator BFSTraverse(Vertex v);//对图进行广度优先遍历
    15   Iterator shortestPath(Vertex v);//求极点v到其他极点的最短途径
    16   void generateMST() throws UnsupportedOperation;//求无向图的最小生成树,假如是有向图不支持此操作
    17   Iterator toplogicalSort() throws UnsupportedOperation;//求有向图的拓扑序列,无向图不支持此操作
    18   void criticalPath() throws UnsupportedOperation;//求有向无环图的要害途径,无向图不支持此操作
  }

  请看 接口界说 Graph

 

三、图的存储办法

 1、邻接矩阵表明法:选用2个数组来表明图;一个是存储一切极点信息的一维数组、一个是存储图中极点之间相关联络的二维数组,这个二维数组称为邻接矩阵。

 

   关于无向图a,邻接矩阵是一个对称矩阵。第i行(i列)非∞元素的个数正好是第i个极点的度。

   关于有向图b,第i行非∞元素的个数是第i个极点的出度、i列非∞元素的个数是第i个极点的入度。

 

   邻接矩阵的缺乏:

      1、由n个极点构成的图中最多能够有n2条边,但大大都情况下,边的数目远远达不到这个量级,邻接矩阵中大大都单元都是搁置的。

2、矩阵结构是静态的,巨细N需求预先估量,然后创立N*N的矩阵,而图的规划往往是动态改变的,N估量过大会形成空间糟蹋,过小则形成空间不够用。

 

2、邻接表表明法:
链接表是图的一种动态的链式存储办法,类似于树的孩子链表表明法。
关于n个极点、m条边的无向图,选用邻接表,需求n个表头节点和2m个边表节点。在边稀少的情 况下,要比运用邻接矩阵节约空间。

邻接表的特性:

在无向图中,极点v的度为v的邻接表中 表表节点的个数。

在有向图中,极点v的邻接表中边表的节点个数仅为v的出度。入度需求遍历这个邻接表 或许

从逆邻接表中获取。

判别2个极点直接是否有边需求搜素2个极点对应的邻接表。不如邻接矩阵便利。

3、双链式存储结构:

  邻接表是图的一种很有用的存储结构,但是在该结构中删去极点,边,或增加极点,边的操作完成起来都比较杂乱,所需时刻价值较大。所以给出双链式存储结构处理上述问题。
  极点、边都笼统为独立的类,一切的极点类都存储在一个链接表中,一切的边类也存储在一个链接表中。并在极点、边之间树立联络。

 边中有5个重要的指针域:榜首极点域、第二极点域、榜首边表方位域、第二边表方位域、边方位域。

    有向图中:榜首极点域指向该边的开始极点在极点表中的方位、第二极点域指向该边的停止极点在极点表中的方位;  榜首边表方位域指向边在其开始点的出边表中的方位,第二边表方位域指向边表在其停止点的入边表中的方位;

    无向图:二个极点域别离指向边的两个极点在极点表中的方位。榜首边表方位域、第二边表方位域别离指向榜首、第二极点的邻接边表中的方位。

    边方位域指向边在边表中的方位。

   

  双链式存储结构的极点界说 Vertex.java

     双链式存储结构的边的界说 Edge.java

 

 四、图的一种简略完成 暗示

    AbstractGraph.java

    

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表亚美娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章

阅读排行

  • 1
  • 2
  • 3
  • 4
  • 5

    Digester 解析XMLITeye

    元素,参数,解析
  • 6

    运用文件体系ITeye

    目录,读取,是否
  • 7
  • 8
  • 9

    Deep diving into CloningITeye

    文章,摘自,首先
  • 10

    Spring 整合 junit4 测验ITeye

    测验,配置文件,试用