的定义和术语

图是一种数据结构，它的形式化定义为

     Graph=（v，r）

  其中   V={ x|x<<dataobject}

R={VR}

     VR={ <x,y> | P( x,y )^( x,y <<V)}

 在图中的数据元素通常称作顶点 （vertex），V是顶点的有穷非空集合,VR是两个顶点之间的关系的集合。若<x,y><<VR,则 <x,y> 表示从x  到y 的一条弧(arc),且称x为弧尾(tail)或初始点(initial node)称Y为弧头（head）或终端点（TERMINAL NODE） 此时的图称为有向图（DIGRAPH）。若〈X，Y 〉〈〈VR必有〈Y，X〉〈〈VR，即VR是对称的，则一无序对（X，Y）代替这两个有序对表示X和Y之间的一条边〈EDGE此时的图称为无向图（UNDIGRPAH）。例如图7。1（A）中  G1是有向图,-定义此图的谓词P(X,Y)则表示从X到Y的一条单向通路.例如图7.1(A)中G1是有向图,定义此图的谓词P(X,Y)则表示从X到Y的一条单向通路.

    G1=(V1,{A1})

其中:   V1={V1,V2,V3,V4}

   A1={(<V1,V2>,<V1,V3>,<V3,V4>,<V4,V1>)}

图7.1(B)中G2为无向图。

     G2=(V2{E2})

其中V2={V1,V2,V3,V4,V5} 

E2={(V1,V2),(V1,V4)(V2,V3),(V2,V5)(V3,V4),(V3,V5)}

我们用N 表示图中顶点数目,用E表示边或弧的数目.在下面的讨论中我们不考顶点到其自身的弧或边,即若<Vi,Vj><<VR,则 Vi!=Vj,那么对于无向图,e的取值范围是0到1/2 N*(N-1).有1/2 N*N(N-1)条边的无向图称为完全图(Completed graph)；

对于有向图,e的取值范围是0到n*(n-1).具有n*(n-1)条弧的有向图称为有向完全图.有很少条边或弧,(如 e<nlogn)的图称为稀疏图(sparse graph),反之称为稠密图(dense graph).

    有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权(weight).这些全可以表示从一个顶点到另一个顶点的距离或耗费.这种带权的图通常称为网(subgraph)

6.2 图的存储结构

6.2.1 数组表示法

用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。其形式定义如下：

     const vtxnum=...，{图的顶点数}

     type vtxptr=1..vtxnum；bit=0..1

  vertex=record

  ...{和顶点相关的信息}

end;

  arc=record

     adj:bit;{表示两个顶点之间是否存在关系}

...    {和弧(或边)相关的其它信息}

end;

graph=record

   vexs:array[vtxptr]of vertex;

arcs:array[vtxptr,vtxptr]ofarc

   end;

若图中顶点只有1至vtxnum的编号，弧(或边)上亦无权及其它相关信息,则只要以一个二维数组表示图的邻接矩阵即可,此时的存储结构可简单说明如下:

type   adjmatrix=arrayvtxptr，vtxptr]of bit；

6.2.2 邻接表

    邻接表（adhacency）是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。

若无向图中有n个顶点，e条边，则它的邻接表需n个头结点和2e个表结点。
在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数；而在有向图中，第i个链表中的结点个数只是顶点vi的出度。

6.2.4 邻接多重表

邻接多重表是无向图的另一种链式存储结构。

其中，mark为标志域，可用以标记该条边是否被搜索过；ivex和jvex为该条边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边。每一个顶点也用一个结点表示，它由如下所示的两个域组成：

其中，data域存储和该顶点相关的信息，firstedge域知识第一条依附于该顶点的边。
邻接多重表的类型说明如下：

   TYPE edgeptr=↑enode；
        　　　　　　firstedge:edgeptr;  END;
        adjmulist=ARRAY[vxtptr] OF　vexnode;

建设中……