8.2 圖的存儲結構

圖的存儲結構除了要存儲圖中各個頂點的本身的信息外,，同時還要存儲頂點與頂點之間的所有關系（邊的信息）,，因此，圖的結構比較復雜,，很難以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關系,，但也正是由于其任意的特性,，故物理表示方法很多常用的圖的存儲結構有鄰接矩陣鄰接表十字鏈表和鄰接多重表

8.2.1 鄰接矩陣表示法

對于一個具有n個頂點的圖，可以使用n*n的矩陣（二維數(shù)組）來表示它們間的鄰接關系圖8.10和圖8.11中,，矩陣A(i,，j)=1表示圖中存在一條邊(V_i，V_j),，而A(i,，j)=0表示圖中不存在邊(V_i，V_j)實際編程時,，當圖為不帶權圖時,，可以在二維數(shù)組中存放bool值，A(i,，j)=true表示存在邊(V_i,，V_j)，A(i,，j)=false表示不存在邊(V_i,，V_j)；當圖帶權值時,，則可以直接在二維數(shù)組中存放權值,，A(i，j)=null表示不存在邊(V_i,，V_j)

圖8.10所示的是無向圖的鄰接矩陣表示法,，可以觀察到，矩陣延對角線對稱,，即A(i,，j)= A(j，i)無向圖鄰接矩陣的第i行或第i列非零元素的個數(shù)其實就是第i個頂點的度這表示無向圖鄰接矩陣存在一定的數(shù)據(jù)冗余

圖8.11所示的是有向圖鄰接矩陣表示法，矩陣并不延對角線對稱，A(i,，j)=1表示頂點V_i鄰接到頂點V_j；A(j,，i)=1則表示頂點V_i鄰接自頂點V_j兩者并不象無向圖鄰接矩陣那樣表示相同的意思有向圖鄰接矩陣的第i行非零元素的個數(shù)其實就是第i個頂點的出度，而第i列非零元素的個數(shù)是第i個頂點的入度,，即第i個頂點的度是第i行和第i列非零元素個數(shù)之和

由于存在n個頂點的圖需要n²個數(shù)組元素進行存儲,，當圖為稀疏圖時，使用鄰接矩陣存儲方法將出現(xiàn)大量零元素,，照成極大地空間浪費,，這時應該使用鄰接表表示法存儲圖中的數(shù)據(jù)

8.2.2 鄰接表表示法

圖的鄰接矩陣存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構鄰接表由表頭結點和表結點兩部分組成，其中圖中每個頂點均對應一個存儲在數(shù)組中的表頭結點如這個表頭結點所對應的頂點存在相鄰頂點,，則把相鄰頂點依次存放于表頭結點所指向的單向鏈表中如圖8.12所示，表結點存放的是鄰接頂點在數(shù)組中的索引對于無向圖來說,，使用鄰接表進行存儲也會出現(xiàn)數(shù)據(jù)冗余,，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點

有向圖的鄰接表有出邊表和入邊表（又稱逆鄰接表）之分出邊表的表結點存放的是從表頭結點出發(fā)的有向邊所指的尾頂點,；入邊表的表結點存放的則是指向表頭結點的某個頭頂點如圖8.13所示,，圖(b)和(c)分別為有向圖(a)的出邊表和入邊表

以上所討論的鄰接表所表示的都是不帶權的圖，如果要表示帶權圖,，可以在表結點中增加一個存放權的字段,，其效果如圖8.14所示

注意：觀察圖8.14可以發(fā)現(xiàn)，當刪除存儲表頭結點的數(shù)組中的某一元素,，有可能使部分表頭結點索引號的改變,，從而導致大面積修改表結點的情況發(fā)生可以在表結點中直接存放指向表頭結點的指針以解決這個問題（在鏈表中存放類實例即是存放指針，但必須要保證表頭結點是類而不是結構體）在實際創(chuàng)建鄰接表時,，甚至可以使用鏈表代替數(shù)組存放表頭結點或使用順序表存代替鏈表存放表結點對所學的數(shù)據(jù)結構知識應當根據(jù)實際情況及所使用語言的特點靈活應用,，切不可生搬硬套

例8-1 AdjacencyList.cs圖的鄰接表存儲結構

1  &65279;using System;

2  using System.Collections.Generic;

3  public classAdjacencyList<T>

4  {

5      List<Vertex<T>>items; //圖的頂點集合

6      public AdjacencyList() : this(10) { } //構造方法

7      public AdjacencyList(int capacity) //指定容量的構造方法

8      {

9          items = newList<Vertex<T>>(capacity);

10     }

11     public void AddVertex(T item) //添加一個頂點

12     {  //不允許插入重復值

13         if (Contains(item))

14         {

15             throw new ArgumentException("插入了重復頂點！");

16         }

17         items.Add(newVertex<T>(item));

18     }

19     public void AddEdge(T from, T to) //添加無向邊

20     {

21         Vertex<T> fromVer = Find(from);//找到起始頂點

22         if (fromVer == null)

23         {

24             throw new ArgumentException("頭頂點并不存在,！");

25         }

26         Vertex<T> toVer = Find(to);//找到結束頂點

27         if(toVer == null)

28         {

29             throw new ArgumentException("尾頂點并不存在,！");

30         }

31         //無向邊的兩個頂點都需記錄邊信息