您當(dāng)前位置：首頁(yè) > 數(shù)據(jù)庫(kù) > 數(shù)據(jù)庫(kù)應(yīng)用 > 數(shù)據(jù)結(jié)構(gòu) - 圖的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu) - 圖的存儲(chǔ)結(jié)構(gòu)

來(lái)源：程序員人生發(fā)布時(shí)間：2015-06-16 09:00:27 閱讀次數(shù)：4593次

圖的抽象數(shù)據(jù)類(lèi)型定義

圖是1種數(shù)據(jù)結(jié)構(gòu)，加上1組基本操作就構(gòu)成了圖的抽象數(shù)據(jù)類(lèi)型。
圖的抽象數(shù)據(jù)類(lèi)型定義以下：
ADT Graph{
數(shù)據(jù)對(duì)象V：具有相同特性的數(shù)據(jù)元素的集合，稱(chēng)為頂點(diǎn)集。
數(shù)據(jù)關(guān)系R：R={VR}
VR={<v,w>|<v,w>| v,w?V∧p(v,w) ，<v,w>表示                                     從v到w的弧，P(v,w)定義了弧<v,w>的信息 }

基本操作P： 
Create_Graph() ： 圖的創(chuàng)建操作。
初始條件：無(wú)。
     操作結(jié)果：生成1個(gè)沒(méi)有頂點(diǎn)的空?qǐng)DG。GetVex(G, v) ： 求圖中的頂點(diǎn)v的值。
初始條件：圖G存在，v是圖中的1個(gè)頂點(diǎn)。
操作結(jié)果：生成1個(gè)沒(méi)有頂點(diǎn)的空?qǐng)DG。 
… … 
DFStraver(G,V)：從v動(dòng)身對(duì)圖G深度優(yōu)先遍歷。
    初始條件：圖G存在。
    操作結(jié)果：對(duì)圖G深度優(yōu)先遍歷，每一個(gè)頂點(diǎn)訪問(wèn)且只訪問(wèn)1次。
          ? ?
BFStraver(G,V)：從v動(dòng)身對(duì)圖G廣度優(yōu)先遍歷。
      初始條件：圖G存在。
      操作結(jié)果：對(duì)圖G廣度優(yōu)先遍歷，每一個(gè)頂點(diǎn)訪問(wèn)且只訪問(wèn)1次。
} ADT Graph

圖的存儲(chǔ)結(jié)構(gòu)

  圖的存儲(chǔ)結(jié)構(gòu)比較復(fù)雜，其復(fù)雜性主要表現(xiàn)在：

◆ 任意頂點(diǎn)之間可能存在聯(lián)系，沒(méi)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系，所以不能用簡(jiǎn)單的順序存儲(chǔ)結(jié)構(gòu)來(lái)表示。
◆ 圖中頂點(diǎn)的度不1樣，有的可能相差很大，若按度數(shù)最大的頂點(diǎn)設(shè)計(jì)結(jié)構(gòu)，則會(huì)浪費(fèi)很多存儲(chǔ)單元，反之按每一個(gè)頂點(diǎn)自己的度設(shè)計(jì)不同的結(jié)構(gòu)，又會(huì)影響操作。
圖的經(jīng)常使用的存儲(chǔ)結(jié)構(gòu)有：鄰接矩陣、鄰接鏈表、10字鏈表、鄰接多重表和邊表。

鄰接矩陣(數(shù)組)表示法

  圖的鄰接矩陣基本思想：用兩個(gè)數(shù)組來(lái)表示圖：1個(gè)1維數(shù)組存儲(chǔ)頂點(diǎn)信息，1個(gè)2維數(shù)組存儲(chǔ)邊或弧的信息。該2維數(shù)組稱(chēng)為鄰接矩陣。

無(wú)權(quán)圖鄰接矩陣的特點(diǎn)

無(wú)向圖鄰接矩陣的特性
鄰接矩陣是對(duì)稱(chēng)方陣；
對(duì)頂點(diǎn)vi，其度數(shù)是第i行的非0元素的個(gè)數(shù)；
無(wú)向圖的邊數(shù)是上(或下)3角形矩陣中非0元素個(gè)數(shù)。
無(wú)向圖的鄰接矩陣中非零元個(gè)數(shù) = 2*無(wú)向圖邊數(shù)
有向圖鄰接矩陣的特性
對(duì)頂點(diǎn)vi，第i行的非0元素的個(gè)數(shù)是其出度OD(vi)；第i列的非0元素的個(gè)數(shù)是其入度ID(vi) 。
鄰接矩陣中非0元素的個(gè)數(shù)就是圖的弧的數(shù)目。

3 圖的鄰接矩陣的創(chuàng)建
圖的鄰接矩陣的實(shí)現(xiàn)比較容易，定義兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)信息(數(shù)據(jù)元素)和邊或弧的信息(數(shù)據(jù)元素之間的關(guān)系) 。其存儲(chǔ)結(jié)構(gòu)情勢(shì)定義以下：


#define MAXVEX 100         /* 最大頂點(diǎn)數(shù)，應(yīng)由用戶(hù)定義 */
#define INFINITY 65535

typedef char VertexType; /* 頂點(diǎn)類(lèi)型應(yīng)由用戶(hù)定義  */
typedef int EdgeType; /* 邊上的權(quán)值類(lèi)型應(yīng)由用戶(hù)定義 */
typedef struct
{
   VertexType vexs[MAXVEX];     /* 頂點(diǎn)表 */
   EdgeType arc[MAXVEX][MAXVEX]; /* 鄰接矩陣，可看做邊表 */
   int numVertexes, numEdges; /* 圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)  */
}MGraph;

(1)  圖的創(chuàng)建
/* 建立無(wú)向網(wǎng)圖的鄰接矩陣表示 */
void CreateMGraph(MGraph *G)
{
    輸入頂點(diǎn)數(shù)numVertexes和邊數(shù)numEdges ；
    for(i = 0;i <G-> numVertexes;i++)
               讀入頂點(diǎn)信息,建立頂點(diǎn)表
    for(i = 0;i <G-> numVertexes;i++)
         for(j = 0;j <G-> numVertexes;j++)
               G->arc[i][j]=INFINITY;/* 鄰接矩陣初始化 */
    for(k = 0;k <G->numEdges;k++) 
                    讀入numEdges條邊，建立鄰接矩陣 
}

   其他操作

(2) 圖的頂點(diǎn)定位
肯定1個(gè)頂點(diǎn)在vexs數(shù)組中的位置(下標(biāo)) ，其進(jìn)程完全同等于在順序存儲(chǔ)的線性表中查找1個(gè)數(shù)據(jù)元素。
根據(jù)下標(biāo)，讀出頂點(diǎn)信息。
(3) 向圖中增加頂點(diǎn)
類(lèi)似在順序存儲(chǔ)的線性表的末尾增加1個(gè)數(shù)據(jù)元素。
(4) 向圖中增加1條弧
根據(jù)給定的弧或邊所依附的頂點(diǎn)，修改鄰接矩陣中所對(duì)應(yīng)的數(shù)組元素。

鄰接鏈表法

基本思想：數(shù)組與鏈表相結(jié)合。
具體辦法：
頂點(diǎn)用1個(gè)1維數(shù)組存儲(chǔ)，每一個(gè)數(shù)據(jù)元素還需要存儲(chǔ)指向第1個(gè)鄰接點(diǎn)的指針。
每一個(gè)頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成1個(gè)單鏈表，無(wú)向圖稱(chēng)為頂點(diǎn)vi的邊（鏈）表，有向圖稱(chēng)為頂點(diǎn)vi作為弧尾的出邊表（或作為弧頭的入邊表

鄰接表的相干操作

求某結(jié)點(diǎn)的度，只需查找該頂點(diǎn)的邊表中結(jié)點(diǎn)的個(gè)數(shù)（或直接將頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)再增加1項(xiàng)，用以存儲(chǔ)其鄰接點(diǎn)的個(gè)數(shù)）；
判斷頂點(diǎn)vi到vj是不是存在邊，檢查頂點(diǎn)vi的邊表中是不是存在結(jié)點(diǎn)vj的下標(biāo)j便可；
求頂點(diǎn)的所有鄰接點(diǎn)，只需對(duì)該頂點(diǎn)的邊表進(jìn)行遍歷便可。
注：在無(wú)向圖的鄰接表中，邊表結(jié)點(diǎn)的個(gè)數(shù)=2 * 邊數(shù)
2 鄰接表法的特點(diǎn)
◆ 在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲(chǔ)空間；
◆ 在無(wú)向圖，頂點(diǎn)Vi的度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)；
◆ 對(duì)有向圖可以建立正鄰接表或逆鄰接表。正鄰接表是以頂點(diǎn)Vi為出度(即為弧的出發(fā)點(diǎn))而建立的鄰接表；逆鄰接表是以頂點(diǎn)Vi為入度(即為弧的終點(diǎn))而建立的鄰接表；
◆ 在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)Vi的出 (或入)度；求入 (或出)度，須遍歷全部鄰接表；

3  結(jié)點(diǎn)及其類(lèi)型定義
#define MAX_VEX  30              /*  最大頂點(diǎn)數(shù)  */
typedef char VertexType; /* 頂點(diǎn)類(lèi)型應(yīng)由用戶(hù)定義 */
typedef int EdgeType;      /* 邊上的權(quán)值類(lèi)型應(yīng)由用戶(hù)定義 */


typedef struct EdgeNode  /* 邊表結(jié)點(diǎn)  */
{
    int adjvex;    /* 鄰接點(diǎn)域,存儲(chǔ)該頂點(diǎn)對(duì)應(yīng)的下標(biāo) */
    EdgeType info;   /* 用于存儲(chǔ)權(quán)值,對(duì)非網(wǎng)圖可以不需要 */
    struct EdgeNode *next; /* 鏈域,指向下1個(gè)鄰接點(diǎn) */
}EdgeNode;

typedef struct VertexNode /* 頂點(diǎn)表結(jié)點(diǎn) */
{
    VertexType data;          /* 頂點(diǎn)域,存儲(chǔ)頂點(diǎn)信息 */
    /*  int  indegree ;    //頂點(diǎn)的度, 有向圖是入度或出度       (亦可不要) */
    EdgeNode *firstarc;   /* 邊表頭指針 */
}VertexNode, AdjList[MAX_VEX];

typedef struct
{
    AdjList adjList;  //頂點(diǎn)數(shù)組（亦成為頭結(jié)點(diǎn)向量）
    int numNodes,numEdges; /* 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) */
}GraphAdjList;

利用上述的存儲(chǔ)結(jié)構(gòu)描寫(xiě)，可方便地實(shí)現(xiàn)圖的基本操作。


(1)  圖的創(chuàng)建     /* 建立圖的鄰接表結(jié)構(gòu) */
void  CreateALGraph(GraphAdjList *G)
{     輸入頂點(diǎn)數(shù)G->numNodes和邊數(shù)G->numEdges
      for(i = 0;i < G->numNodes;i++) 
            讀入頂點(diǎn)信息   G->adjList[i].data,
                                     G->adjList[i].firstedge）/* 將邊表置為空表 */
     for(k = 0;k < G->numEdges;k++) /* 建立邊表 */
    {     輸入邊(vi,vj)上的頂點(diǎn)序號(hào);
          向內(nèi)存申請(qǐng)空間,生成邊表結(jié)點(diǎn)；
          將新生成的結(jié)點(diǎn)插入到以頂點(diǎn)vi為頭結(jié)點(diǎn)的鏈表上; 
       （ 用頭插入法or尾插入法方便？）
          此處需注意：如果是無(wú)向圖，1條邊對(duì)應(yīng)兩個(gè)頂點(diǎn)，所以應(yīng)同時(shí)修正以vi為頭結(jié)點(diǎn)和以vj為頭結(jié)點(diǎn)的鏈表。
     }
}

其他操作：
(2) 圖的頂點(diǎn)定位
圖的頂點(diǎn)定位實(shí)際上是肯定1個(gè)頂點(diǎn)在AdjList數(shù)組中的某個(gè)元素的data域內(nèi)容。
(3) 向圖中增加頂點(diǎn)
向圖中增加1個(gè)頂點(diǎn)的操作，在AdjList數(shù)組的末尾增加1個(gè)數(shù)據(jù)元素。
(4) 向圖中增加1條弧
根據(jù)給定的弧或邊所依附的頂點(diǎn)，修改單鏈表：無(wú)向圖修改兩個(gè)單鏈表；有向圖修改1個(gè)單鏈表。

10字鏈表法

10字鏈表(Orthogonal List)是有向圖的另外一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是將有向圖的正鄰接表和逆鄰接表結(jié)合起來(lái)得到的1種鏈表。
在這類(lèi)結(jié)構(gòu)中，每條弧的弧頭結(jié)點(diǎn)和弧尾結(jié)點(diǎn)都寄存在鏈表中，并將分別組織到以弧尾結(jié)點(diǎn)為頭(頂點(diǎn))結(jié)點(diǎn)和以弧頭結(jié)點(diǎn)為頭(頂點(diǎn))結(jié)點(diǎn)的鏈表中。

◆  data域：存儲(chǔ)和頂點(diǎn)相干的信息；
◆ firstin：指向以該頂點(diǎn)為弧頭的第1條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)；
◆ firstout：指向以該頂點(diǎn)為弧尾的第1條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)；

◆ tailvex：唆使弧尾頂點(diǎn)在頂點(diǎn)表中的下標(biāo)；
◆ headvex：唆使弧頭頂點(diǎn)在頂點(diǎn)表中的下標(biāo)；
◆ hlink：指向弧頭相同的下1條弧；
◆ tlink：指向弧尾相同的下1條弧；
◆ Info域：指向該弧的相干信息，如網(wǎng)的權(quán)值

結(jié)點(diǎn)類(lèi)型定義
#define INFINITY  MAX_VAL     /* 最大值∞ */
#define MAX_VEX  30     //  最大頂點(diǎn)數(shù)  
typedef struct ArcNode
{   int  tailvex , headvex ;   //  尾結(jié)點(diǎn)和頭結(jié)點(diǎn)在頂點(diǎn)表中的下標(biāo)；
InfoType    info  ;          // 與弧相干的信息, 如權(quán)值
struct ArcNode  *hlink , *tlink ; 
}ArcNode ;    /*  弧結(jié)點(diǎn)類(lèi)型定義   */
typedef struct VexNode
{  VexType  data;     // 頂點(diǎn)信息
ArcNode  *firstin , *firstout ;
}VexNode ;    /*  頂點(diǎn)結(jié)點(diǎn)類(lèi)型定義   */
typedef struct
{  int vexnum ;
VexNode  xlist[MAX_VEX] ;
}OLGraph ;   /*  圖的類(lèi)型定義   */

鄰接多重表(Adjacency Multilist)

       鄰接多重表(Adjacency Multilist)是無(wú)向圖的另外一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
       在無(wú)向圖的鄰接表中，1條邊(v,w)的兩個(gè)表結(jié)點(diǎn)分別被選在以v和w為頭結(jié)點(diǎn)的鏈表中。如果關(guān)注的重點(diǎn)是頂點(diǎn)，則鄰接表是不錯(cuò)的選擇，但在觸及到邊的操作會(huì)帶來(lái)不便。
      鄰接多重表的結(jié)構(gòu)和10字鏈表類(lèi)似，每條邊用1個(gè)結(jié)點(diǎn)表示；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)與鄰接表中的完全相同

Data域：存儲(chǔ)和頂點(diǎn)相干的信息；
firstedge：指向依附于該頂點(diǎn)的第1條邊所對(duì)應(yīng)的表結(jié)點(diǎn)；
mark：用以標(biāo)識(shí)該條邊是不是被訪問(wèn)過(guò)；
ivex和jvex：分別保存該邊所依附的兩個(gè)頂點(diǎn)在頂點(diǎn)表中的下標(biāo)；
info域：保存該邊的相干信息；
ilink：指向依附于頂點(diǎn)ivex的下1條邊；
jlink：指向依附于頂點(diǎn)jvex的下1條邊；

結(jié)點(diǎn)類(lèi)型定義
#define INFINITY  65535     /* 最大值∞ */
#define MAX_VEX  30     /*  最大頂點(diǎn)數(shù)  */
typedef  emnu {unvisited , visited}  Visitting ;
typedef struct EdgeNode
{  Visitting  mark ;    // 訪問(wèn)標(biāo)記
int  ivex , jvex  ;   // 該邊依附的兩個(gè)結(jié)點(diǎn)在圖中的位置
InfoType    info  ;       // 與邊相干的信息, 如權(quán)值
struct EdgeNode  *ilink , *jlink ; 
// 分別指向依附于這兩個(gè)頂點(diǎn)的下1條邊
}EdgeNode ;    /*  弧邊結(jié)點(diǎn)類(lèi)型定義   */

typedef struct VexNode
{  VexType  data;     // 頂點(diǎn)信息
ArcNode  *firsedge ;   //指向依附于該頂點(diǎn)的第1條邊
}VexNode ;    /*  頂點(diǎn)結(jié)點(diǎn)類(lèi)型定義   */
typedef struct
{  int vexnum ;
VexNode mullist[MAX_VEX] ;
}AMGraph ;

圖的邊表存儲(chǔ)結(jié)構(gòu)

在某些利用中，有時(shí)主要考察圖中邊的權(quán)值和所依附的兩個(gè)頂點(diǎn)，即圖的結(jié)構(gòu)主要由邊來(lái)表示，稱(chēng)為邊表存儲(chǔ)結(jié)構(gòu)。
邊表結(jié)構(gòu)采取順序存儲(chǔ)，用2個(gè)1維數(shù)組構(gòu)成，1個(gè)存儲(chǔ)頂點(diǎn)信息，1個(gè)存儲(chǔ)邊的信息。邊數(shù)組的每一個(gè)元素由3部份組成：
邊的出發(fā)點(diǎn)下標(biāo)
邊的終點(diǎn)下標(biāo)
邊的權(quán)值

邊表存儲(chǔ)結(jié)構(gòu)的情勢(shì)描寫(xiě)以下：
#define INFINITY  MAX_VAL     /* 最大值∞ */
#define MAX_VEX  30     /*  最大頂點(diǎn)數(shù)  */
#define MAX_EDGE  100     /*  最大邊數(shù)  */
typedef struct ENode
{  int  begin , end  ;   /*   邊所依附的兩個(gè)頂點(diǎn)  */
WeightType    weight  ;       /*   邊的權(quán)值   */
}ENode ;    /*  邊表元素類(lèi)型定義   */
typedef struct 
{  int  vexnum , edgenum ;     /*   頂點(diǎn)數(shù)和邊數(shù)    */
VexType  vexs[MAX_VEX] ;    /*   頂點(diǎn)表    */
ENode  edges[MAX_EDGE] ;     /*   邊表    */ 
}ELGraph ;