图的相关概念及遍历方法概述

这一篇我们要总结的是图(Graph)，图可能比我们之前学习的线性结构和树形结构都要复杂，不过没有关系，我们一点一点地来总结，那么关于图我想从以下几点进行总结：

1，图的定义？

2，图相关的概念和术语？

3，图的创建和遍历？

4，最小生成树和最短路径？

5，算法实现？

一，图的定义

什么是图呢？

图是一种复杂的非线性结构。

在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继；

在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(双亲节点)及下一层的多个元素(孩子节点)相关；

而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。

图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V，E)

二，图相关的概念和术语

1，无向图和有向图

对于一个图，若每条边都是没有方向的，则称该图为无向图。图示如下：

因此，(V_i，V_j)和(V_j，V_i)表示的是同一条边。注意，无向图是用小括号，而下面介绍的有向图是用尖括号。

无向图的顶点集和边集分别表示为：

V(G)={V₁，V₂，V₃，V₄，V₅}

E(G)={(V₁，V₂)，(V₁，V₄)，(V₂，V₃)，(V₂，V₅)，(V₃，V₄)，(V₃，V₅)，(V₄，V₅)}

 

对于一个图G，若每条边都是有方向的，则称该图为有向图。图示如下。

因此，<V_i，V_j>和<V_j，V_i>是两条不同的有向边。注意，有向边又称为弧。

有向图的顶点集和边集分别表示为：

V(G)={V₁，V₂，V₃}

E(G)={<V₁，V₂>，<V₂，V₃>，<V_3，V₁>，<V₁，V₃>}

2，无向完全图和有向完全图

我们将具有n(n-1)/2条边的无向图称为无向完全图。同理，将具有n(n-1)条边的有向图称为有向完全图。

3，顶点的度

对于无向图，顶点的度表示以该顶点作为一个端点的边的数目。比如，图(a)无向图中顶点V₃的度D(V₃)=3

对于有向图，顶点的度分为入度和出度。入度表示以该顶点为终点的入边数目，出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。比如，顶点V₁的入度ID(V₁)=1，出度OD(V₁)=2，所以D(V₁)=ID(V₁)+OD(V₁)=1+2=3

记住，不管是无向图还是有向图，顶点数n，边数e和顶点的度数有如下关系：

因此，就拿有向图(b)来举例，由公式可以得到图G的边数e=(D(V₁)+D(V₂)+D(V₃))/2=(3+2+3)/2=4

4，子图

故名思义，这个就不解释了。

5，路径，路径长度和回路

路径，比如在无向图G中，存在一个顶点序列V_p,V_i1,V_i2,V_i3…，V_im，V_q，使得(V_p,V_i1)，(V_i1,V_i2)，…,(V_im,V_q)均属于边集E(G)，则称顶点V_p到V_q存在一条路径。

路径长度，是指一条路径上经过的边的数量。

回路，指一条路径的起点和终点为同一个顶点。

6，连通图(无向图)

连通图是指图G中任意两个顶点V_i和V_j都连通，则称为连通图。比如图(b)就是连通图。下面是一个非连通图的例子。

上图中，因为V₅和V₆是单独的，所以是非连通图。

7，强连通图(有向图)

强连通图是对于有向图而言的，与无向图的连通图类似。

8，网

带”权值”的连通图称为网。如图所示。

三，图的创建和遍历

1，图的两种存储结构

1) 邻接矩阵，原理就是用两个数组，一个数组保存顶点集，一个数组保存边集。下面的算法实现里边我们也是采用这种存储结构。如下图所示：

2) 邻接表，邻接表是图的一种链式存储结构。这种存储结构类似于树的孩子链表。对于图G中每个顶点V_i，把所有邻接于V_i的顶点V_j链成一个单链表，这个单链表称为顶点V_i的邻接表。

2，图的两种遍历方法

1) 深度优先搜索遍历

深度优先搜索DFS遍历类似于树的前序遍历。其基本思路是：

a) 假设初始状态是图中所有顶点都未曾访问过，则可从图G中任意一顶点v为初始出发点，首先访问出发点v，并将其标记为已访问过。

b) 然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中所有和v有路径相通的顶点都被访问到。

c) 若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述步骤，直到图中所有顶点都被访问到为止。

图示如下：

注：红色数字代表遍历的先后顺序，所以图(e)无向图的深度优先遍历的顶点访问序列为：V₀，V₁，V₂，V₅，V₄，V₆，V₃，V₇，V₈

如果采用邻接矩阵存储，则时间复杂度为O(n²)；当采用邻接表时时间复杂度为O(n+e)。

2) 广度优先搜索遍历

广度优先搜索遍历BFS类似于树的按层次遍历。其基本思路是：

a) 首先访问出发点V_i

b) 接着依次访问V_i的所有未被访问过的邻接点V_i1，V_i2，V_i3，…，V_it并均标记为已访问过。

c) 然后再按照V_i1，V_i2，… ，V_it的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依此类推，直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。

图示如下：

因此，图(f)采用广义优先搜索遍历以V₀为出发点的顶点序列为：V₀，V₁，V₃，V₄，V₂，V₆，V₈，V₅，V₇

如果采用邻接矩阵存储，则时间复杂度为O(n²)，若采用邻接表，则时间复杂度为O(n+e)。

四，最小生成树和最短路径

1，最小生成树

什么是最小生成树呢？在弄清什么是最小生成树之前，我们需要弄清什么是生成树？

用一句语简单概括生成树就是：生成树是将图中所有顶点以最少的边连通的子图。

比如图(g)可以同时得到两个生成树图(h)和图(i)

知道了什么是生成树之后，我们就很容易理解什么是最小生成树了。所谓最小生成树，用一句话总结就是：权值和最小的生成树就是最小生成树。

比如上图中的两个生成树，生成树1和生成树2，生成树1的权值和为：12，生成树2的权值为：14，我们可以证明图(h)生成树1就是图(g)的最小生成树。

那么如何构造最小生成树呢？可以使用普里姆算法。

2，最短路径

求最短路径也就是求最短路径长度。下面是一个带权值的有向图，表格中分别列出了顶点V1其它各顶点的最短路径长度。

源点	最短路径	终点		路径长度
V1	V1，V3，V2	V2	中转	5
V1	V1，V3	V3	直达	3
V1	V1，V3，V2，V4	V4	中转	10
V1	V1，V3，V5	V5	中转	18

表：顶点V₁到其它各顶点的最短路径表

从图中可以看出，顶点V₁到V₄的路径有3条(V₁，V₂，V₄)，(V₁，V₄)，(V₁，V₃，V₂，V₄)，其路径长度分别为15，20和10，因此，V₁到V₄的最短路径为(V₁，V₃，V₂，V₄)。

那么如何求带权有向图的最短路径长度呢？可以使用迪杰斯特拉(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<n; 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

 

三、图的存储方法

 １、邻接矩阵表示法：采用2个数组来表示图;一个是存储所有顶点信息的一维数组、一个是存储图中顶点之间关联关系的二维数组,这个二维数组称为邻接矩阵。

 

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

   对于有向图b，第i行非∞元素的个数是第i个顶点的出度、i列非∞元素的个数是第i个顶点的入度。

 

   　邻接矩阵的不足：

      1、由n个顶点构成的图中最多可以有n²条边，但大多数情况下，边的数目远远达不到这个量级，邻接矩阵中大多数单元都是闲置的。

　　　２、矩阵结构是静态的，大小Ｎ需要预先估计，然后创建Ｎ*Ｎ的矩阵，而图的规模往往是动态变化的，Ｎ估计过大会造成空间浪费，过小则造成空间不够用。

 

　　２、邻接表表示法：
　　　链接表是图的一种动态的链式存储方法，类似于树的孩子链表表示法。
对于n个顶点、m条边的无向图，采用邻接表，需要n个表头节点和2m个边表节点。在边稀疏的情　　况下，要比使用邻接矩阵节省空间。

　　邻接表的特性：

　　　　在无向图中，顶点ｖ的度为ｖ的邻接表中 表表节点的个数。

　　　　在有向图中，顶点ｖ的邻接表中边表的节点个数仅为ｖ的出度。入度需要遍历这个邻接表　或者

　　从逆邻接表中获取。

　　　　判断２个顶点直接是否有边需要搜素２个顶点对应的邻接表。不如邻接矩阵方便。

　　

　３、双链式存储结构：

  　邻接表是图的一种很有效的存储结构，但是在该结构中删除顶点，边，或添加顶点，边的操作实现起来都比较复杂，所需时间代价较大。所以给出双链式存储结构解决上述问题。
  　顶点、边都抽象为独立的类，所有的顶点类都存储在一个链接表中，所有的边类也存储在一个链接表中。并在顶点、边之间建立关系。

 边中有5个重要的指针域：第一顶点域、第二顶点域、第一边表位置域、第二边表位置域、边位置域。

    有向图中：第一顶点域指向该边的起始顶点在顶点表中的位置、第二顶点域指向该边的终止顶点在顶点表中的位置；  第一边表位置域指向边在其起始点的出边表中的位置，第二边表位置域指向边表在其终止点的入边表中的位置；

    无向图：二个顶点域分别指向边的两个顶点在顶点表中的位置。第一边表位置域、第二边表位置域分别指向第一、第二顶点的邻接边表中的位置。

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

   

 　　双链式存储结构的顶点定义　Vertex.java

     双链式存储结构的边的定义　Edge.java

 

 四、图的一种简单实现 示意

    AbstractGraph.java