您當前位置：首頁 > 數據庫 > 數據庫應用 > 數據結構 - 圖的存儲結構

數據結構 - 圖的存儲結構

來源：程序員人生發布時間：2015-06-16 09:00:27 閱讀次數：4585次

圖的抽象數據類型定義

圖是1種數據結構，加上1組基本操作就構成了圖的抽象數據類型。
圖的抽象數據類型定義以下：
ADT Graph{
數據對象V：具有相同特性的數據元素的集合，稱為頂點集。
數據關系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() ： 圖的創建操作。
初始條件：無。
     操作結果：生成1個沒有頂點的空圖G。GetVex(G, v) ： 求圖中的頂點v的值。
初始條件：圖G存在，v是圖中的1個頂點。
操作結果：生成1個沒有頂點的空圖G。 
… … 
DFStraver(G,V)：從v動身對圖G深度優先遍歷。
    初始條件：圖G存在。
    操作結果：對圖G深度優先遍歷，每一個頂點訪問且只訪問1次。
          ? ?
BFStraver(G,V)：從v動身對圖G廣度優先遍歷。
      初始條件：圖G存在。
      操作結果：對圖G廣度優先遍歷，每一個頂點訪問且只訪問1次。
} ADT Graph

圖的存儲結構

  圖的存儲結構比較復雜，其復雜性主要表現在：

◆ 任意頂點之間可能存在聯系，沒法以數據元素在存儲區中的物理位置來表示元素之間的關系，所以不能用簡單的順序存儲結構來表示。
◆ 圖中頂點的度不1樣，有的可能相差很大，若按度數最大的頂點設計結構，則會浪費很多存儲單元，反之按每一個頂點自己的度設計不同的結構，又會影響操作。
圖的經常使用的存儲結構有：鄰接矩陣、鄰接鏈表、10字鏈表、鄰接多重表和邊表。

鄰接矩陣(數組)表示法

  圖的鄰接矩陣基本思想：用兩個數組來表示圖：1個1維數組存儲頂點信息，1個2維數組存儲邊或弧的信息。該2維數組稱為鄰接矩陣。

無權圖鄰接矩陣的特點

無向圖鄰接矩陣的特性
鄰接矩陣是對稱方陣；
對頂點vi，其度數是第i行的非0元素的個數；
無向圖的邊數是上(或下)3角形矩陣中非0元素個數。
無向圖的鄰接矩陣中非零元個數 = 2*無向圖邊數
有向圖鄰接矩陣的特性
對頂點vi，第i行的非0元素的個數是其出度OD(vi)；第i列的非0元素的個數是其入度ID(vi) 。
鄰接矩陣中非0元素的個數就是圖的弧的數目。

3 圖的鄰接矩陣的創建
圖的鄰接矩陣的實現比較容易，定義兩個數組分別存儲頂點信息(數據元素)和邊或弧的信息(數據元素之間的關系) 。其存儲結構情勢定義以下：


#define MAXVEX 100         /* 最大頂點數，應由用戶定義 */
#define INFINITY 65535

typedef char VertexType; /* 頂點類型應由用戶定義  */
typedef int EdgeType; /* 邊上的權值類型應由用戶定義 */
typedef struct
{
   VertexType vexs[MAXVEX];     /* 頂點表 */
   EdgeType arc[MAXVEX][MAXVEX]; /* 鄰接矩陣，可看做邊表 */
   int numVertexes, numEdges; /* 圖中當前的頂點數和邊數  */
}MGraph;

(1)  圖的創建
/* 建立無向網圖的鄰接矩陣表示 */
void CreateMGraph(MGraph *G)
{
    輸入頂點數numVertexes和邊數numEdges ；
    for(i = 0;i <G-> numVertexes;i++)
               讀入頂點信息,建立頂點表
    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) 圖的頂點定位
肯定1個頂點在vexs數組中的位置(下標) ，其進程完全同等于在順序存儲的線性表中查找1個數據元素。
根據下標，讀出頂點信息。
(3) 向圖中增加頂點
類似在順序存儲的線性表的末尾增加1個數據元素。
(4) 向圖中增加1條弧
根據給定的弧或邊所依附的頂點，修改鄰接矩陣中所對應的數組元素。

鄰接鏈表法

基本思想：數組與鏈表相結合。
具體辦法：
頂點用1個1維數組存儲，每一個數據元素還需要存儲指向第1個鄰接點的指針。
每一個頂點vi的所有鄰接點構成1個單鏈表，無向圖稱為頂點vi的邊（鏈）表，有向圖稱為頂點vi作為弧尾的出邊表（或作為弧頭的入邊表

鄰接表的相干操作

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

3  結點及其類型定義
#define MAX_VEX  30              /*  最大頂點數  */
typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType;      /* 邊上的權值類型應由用戶定義 */


typedef struct EdgeNode  /* 邊表結點  */
{
    int adjvex;    /* 鄰接點域,存儲該頂點對應的下標 */
    EdgeType info;   /* 用于存儲權值,對非網圖可以不需要 */
    struct EdgeNode *next; /* 鏈域,指向下1個鄰接點 */
}EdgeNode;

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

typedef struct
{
    AdjList adjList;  //頂點數組（亦成為頭結點向量）
    int numNodes,numEdges; /* 圖中當前頂點數和邊數 */
}GraphAdjList;

利用上述的存儲結構描寫，可方便地實現圖的基本操作。


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

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

10字鏈表法

10字鏈表(Orthogonal List)是有向圖的另外一種鏈式存儲結構，是將有向圖的正鄰接表和逆鄰接表結合起來得到的1種鏈表。
在這類結構中，每條弧的弧頭結點和弧尾結點都寄存在鏈表中，并將分別組織到以弧尾結點為頭(頂點)結點和以弧頭結點為頭(頂點)結點的鏈表中。

◆  data域：存儲和頂點相干的信息；
◆ firstin：指向以該頂點為弧頭的第1條弧所對應的弧結點；
◆ firstout：指向以該頂點為弧尾的第1條弧所對應的弧結點；

◆ tailvex：唆使弧尾頂點在頂點表中的下標；
◆ headvex：唆使弧頭頂點在頂點表中的下標；
◆ hlink：指向弧頭相同的下1條??；
◆ tlink：指向弧尾相同的下1條??；
◆ Info域：指向該弧的相干信息，如網的權值

結點類型定義
#define INFINITY  MAX_VAL     /* 最大值∞ */
#define MAX_VEX  30     //  最大頂點數  
typedef struct ArcNode
{   int  tailvex , headvex ;   //  尾結點和頭結點在頂點表中的下標；
InfoType    info  ;          // 與弧相干的信息, 如權值
struct ArcNode  *hlink , *tlink ; 
}ArcNode ;    /*  弧結點類型定義   */
typedef struct VexNode
{  VexType  data;     // 頂點信息
ArcNode  *firstin , *firstout ;
}VexNode ;    /*  頂點結點類型定義   */
typedef struct
{  int vexnum ;
VexNode  xlist[MAX_VEX] ;
}OLGraph ;   /*  圖的類型定義   */

鄰接多重表(Adjacency Multilist)

       鄰接多重表(Adjacency Multilist)是無向圖的另外一種鏈式存儲結構。
       在無向圖的鄰接表中，1條邊(v,w)的兩個表結點分別被選在以v和w為頭結點的鏈表中。如果關注的重點是頂點，則鄰接表是不錯的選擇，但在觸及到邊的操作會帶來不便。
      鄰接多重表的結構和10字鏈表類似，每條邊用1個結點表示；鄰接多重表中的頂點結點與鄰接表中的完全相同

Data域：存儲和頂點相干的信息；
firstedge：指向依附于該頂點的第1條邊所對應的表結點；
mark：用以標識該條邊是不是被訪問過；
ivex和jvex：分別保存該邊所依附的兩個頂點在頂點表中的下標；
info域：保存該邊的相干信息；
ilink：指向依附于頂點ivex的下1條邊；
jlink：指向依附于頂點jvex的下1條邊；

結點類型定義
#define INFINITY  65535     /* 最大值∞ */
#define MAX_VEX  30     /*  最大頂點數  */
typedef  emnu {unvisited , visited}  Visitting ;
typedef struct EdgeNode
{  Visitting  mark ;    // 訪問標記
int  ivex , jvex  ;   // 該邊依附的兩個結點在圖中的位置
InfoType    info  ;       // 與邊相干的信息, 如權值
struct EdgeNode  *ilink , *jlink ; 
// 分別指向依附于這兩個頂點的下1條邊
}EdgeNode ;    /*  弧邊結點類型定義   */

typedef struct VexNode
{  VexType  data;     // 頂點信息
ArcNode  *firsedge ;   //指向依附于該頂點的第1條邊
}VexNode ;    /*  頂點結點類型定義   */
typedef struct
{  int vexnum ;
VexNode mullist[MAX_VEX] ;
}AMGraph ;

圖的邊表存儲結構

在某些利用中，有時主要考察圖中邊的權值和所依附的兩個頂點，即圖的結構主要由邊來表示，稱為邊表存儲結構。
邊表結構采取順序存儲，用2個1維數組構成，1個存儲頂點信息，1個存儲邊的信息。邊數組的每一個元素由3部份組成：
邊的出發點下標
邊的終點下標
邊的權值

邊表存儲結構的情勢描寫以下：
#define INFINITY  MAX_VAL     /* 最大值∞ */
#define MAX_VEX  30     /*  最大頂點數  */
#define MAX_EDGE  100     /*  最大邊數  */
typedef struct ENode
{  int  begin , end  ;   /*   邊所依附的兩個頂點  */
WeightType    weight  ;       /*   邊的權值   */
}ENode ;    /*  邊表元素類型定義   */
typedef struct 
{  int  vexnum , edgenum ;     /*   頂點數和邊數    */
VexType  vexs[MAX_VEX] ;    /*   頂點表    */
ENode  edges[MAX_EDGE] ;     /*   邊表    */ 
}ELGraph ;