資料結構---->圖的存儲結構

樹的存儲結構

2.1鄰接矩陣(數組)表示法

圖沒有順序映像的存儲結構，但可以借助數組來表示資料元素之間的關系。

建立一個頂點表（記錄各個頂點資訊）和一個鄰接矩陣（表示各個頂點之間關系）

頂點表：（a,b,c,d）

鄰接矩陣：

分析1：無向圖的鄰接矩陣是對稱的；

分析2：頂點i 的度＝第i 行 (列) 中1 的個數；

特别：完全圖的鄰接矩陣中，對角元素為0，其餘全1。

有向帶權圖和它的鄰接矩陣：

分析1：有向圖的鄰接矩陣可能是不對稱的。

分析2：頂點的出度=第i行元素之和，OD( Vi )=∑A.Edge[ i ][j ]

       頂點的入度=第i列元素之和。ID( Vi )=∑A.Edge[ j ][i ]

       頂點的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD( Vi )+ ID( Vi )

鄰接矩陣法優點：容易實作圖的操作，如：判斷頂點之間是否有邊（弧）、找頂點的鄰接點等等。

鄰接矩陣法缺點：首先n個頂點需要N×N個單元存儲邊(弧);空間效率為O(n2)。對稀疏圖而言尤其浪費空間。其次，矩陣結構是靜态的，其大小N需要預先估計，然後建立的矩陣。然而，圖的規模往往是動态變化的，N的估計過大會造成更多的空間浪費，如果估計過小則經常會出現空間不夠用的情況。

2.2、鄰接表(鍊式)表示法

鄰接矩陣的空間效率之是以低，是因為其中大量的單元所對應的邊有可能并未在圖中出現，這是靜态數組結構不可避免的問題。既然如此，則可以将靜态的存儲結構改為動态的鍊式存儲結構。按照這一思路可以得到圖的另一種表示形式，它其實是對鄰接矩陣法的一種改進，即鄰接表。

每個單連結清單附設一個頭結點（設為2個域），存vi資訊；

每個單連結清單的頭結點用順序存儲結構存儲。

對每個頂點vi 建立一個單連結清單，把與vi有關聯的邊的資訊（即度或出度邊）連結起來，表中每個結點都設為3個域；

無向圖的鄰接表

對于n個頂點e條邊的無向圖，鄰接表中除了n個頭結點外，隻有2e個表結點,空間效率為O(n+2e)。若是稀疏圖(e<<n2)，則比鄰接矩陣表示法O(n2)省空間。

頂點vi的度恰為頂點vi的鄰接表中邊表結點的個數；

有向圖的鄰接表

在有向圖中,鄰接表中除了n個頭結點外,隻有e個表結點,空間效率為O(n+e)。若是稀疏圖,則比鄰接矩陣表示法合适。

頂點vi的鄰接表中邊表結點的個數僅為頂點vi的出度，為求頂點vi的入度必須周遊整個鄰接表。在所有連結清單中其鄰接點域的值指向vi的位置的結點個數是頂點vi的入度。

逆鄰接表：為了友善求得有向圖中頂點的入度，可以建立一個有向圖的逆鄰接表。

鄰接表的優點：空間效率高；容易尋找頂點的鄰接點；

鄰接表的缺點：判斷兩頂點間是否有邊或弧，需搜尋兩結點對應的單連結清單，沒有鄰接矩陣友善。

鄰接表與鄰接矩陣聯系：鄰接表中每個連結清單對應于鄰接矩陣中的一行，連結清單中結點個數等于一行中非零元素的個數。

用途：鄰接矩陣多用于稠密圖的存儲(e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(e<<n2)

2.3  雙鍊式存儲結構

雖然鄰接表是圖的一種很有效的存儲結構，在鄰接表中容易求得頂點和邊的各種資訊。但是這種結構會給圖的某些操作帶來不便。例如，在無向圖中，每條邊在鄰接表中對應了兩個邊表結點，如果在圖的應用中需要對邊進行标記，或删除邊等，此時需要找到表示同一條邊的兩個邊表結點，然後執行相同的操作，以保證資料的一緻性，是以操作的實作比較麻煩。另一方面，如果在鄰接表中，将所有的頂點按照順序的方式存儲，會使得頂點的删除操作所需的時間代價較大。首先在數組中删除一個元素，平均需要移動大約數組中一半的元素；其次，在删除一個頂點時，需要将與之相關聯的所有邊删除，如上所述，在無向圖中删除一條邊需要删除兩個邊表結點，較為複雜；再次，由于在删除某個頂點以後，會造成後續頂點在頂點數組中的位置發生變化，是以要判斷所有邊表結點的鄰接點域是否需要修改，如果其鄰接點域所指頂點位置發生變化，則需要使用新的指向替換原來的指向。以上操作總共需要Ο(|V|+|E|)的時間。解決這個問題的一種辦法是，在删除頂點時，并不将數組中其後續頂點前移，隻是将相應位置設定為空，然後删除與之關聯的所有邊。但是這種方法會使得在圖中添加頂點之前需要先周遊頂點數組，查找數組中為空的位置，如果有則将新的頂點放入該位置，如果沒有則放到數組的尾部。這樣添加一個新頂點的操作實作會比較複雜。綜合以上兩點，在圖的鄰接表與逆鄰接表的基礎上，我們給出圖的一種雙鍊式存儲結構以解決上述問題。

頂點中有3 個重要的指針域：頂點位置域、鄰接邊域、逆鄰接邊域。其中頂點位置域指向頂點在頂點連結表中所在的結點，以此可以在Ο(1)時間内确定頂點在圖中的位置。在無向圖中頂點的鄰接邊域指向的連結表存儲了與該頂點關聯的所有邊的引用，頂點的逆鄰接邊域為空；而在有向圖中，頂點的鄰接邊域指向的連結表存儲了該頂點所有出邊的引用，頂點的逆鄰接邊域指向的連結表存儲了該頂點所有入邊的引用。鄰接邊域和逆鄰接邊域相當于圖中頂點的鄰接表和逆鄰接表。通過這兩個域可以很快的找到與該頂點相連的所有頂點和邊的資訊。

邊中有5個重要的指針域：第一頂點域、第二頂點域、第一邊表位置域、第二邊表位置域、邊位置域。在有向圖中，第一頂點域指向該邊的起始頂點在頂點表中的位置，第二頂點域指向該邊的終止頂點在頂點表中的位置；如果是無向圖，則分别指向邊的兩個頂點在頂點表中的位置；通過這兩個域可以在Ο(1)時間内定位與邊關聯的頂點。在有向圖中，第一邊表位置域指向邊在其起始點的出邊表中的位置，第二邊表位置域指向邊在其終止點的入邊表中的位置；如果是無向圖，則這兩個域分别指向邊在其第一、第二頂點的鄰接邊表（無向圖的頂點隻有鄰接邊表，無逆鄰接邊表）中的位置。邊位置域指向邊在邊表中的位置，通過該域可以在Ο(1)時間内定位邊在圖中的位置。

雙鍊式存儲結構的頂點定義

public class Vertex {
	private Object info; // 頂點資訊
	private LinkedList adjacentEdges; // 頂點的鄰接邊表
	private LinkedList reAdjacentEdges; // 頂點的逆鄰接邊表，無向圖時為空
	private boolean visited; // 通路狀态
	private Node vexPosition; // 頂點在頂點表中的位置
	private int graphType; // 頂點所在圖的類型
	private Object application; // 應用資訊。例如求最短路徑時為Path，求關鍵路徑時為Vtime

	// 構造方法:在圖G中引入一個新頂點
	public Vertex(Graph g, Object info) {
		this.info = info;
		adjacentEdges = new LinkedListDLNode();
		reAdjacentEdges = new LinkedListDLNode();
		visited = false;
		graphType = g.getType();
		vexPosition = g.insert(this);
		application = null;
	}

	// 輔助方法:判斷頂點所在圖的類型
	private boolean isUnDiGraphNode() {
		return graphType == Graph.UndirectedGraph;
	}

	// 擷取或設定頂點資訊
	public Object getInfo() {
		return info;
	}

	public void setInfo(Object info) {
		this.info = info;
	}

	// 與頂點的度相關的方法
	public int getDeg() {
		if (isUnDiGraphNode())
			return adjacentEdges.getSize(); // 無向圖頂點的(出/入)度即為鄰接邊表的規模
		else
			return getOutDeg() + getInDeg(); // 有向圖頂點的度為出度與入度之和
	}

	public int getOutDeg() {
		return adjacentEdges.getSize(); // 有(無)向圖頂點的出度為鄰接表規模
	}

	public int getInDeg() {
		if (isUnDiGraphNode())
			return adjacentEdges.getSize(); // 無向圖頂點的入度就是它的度
		else
			return reAdjacentEdges.getSize();// 有向圖頂點入度為逆鄰接表的規模
	}

	// 擷取與頂點關聯的邊
	public LinkedList getAdjacentEdges() {
		return adjacentEdges;
	}

	public LinkedList getReAdjacentEdges() {
		if (isUnDiGraphNode())
			return adjacentEdges; // 無向圖頂點無逆鄰接邊表,其逆鄰接邊表就是鄰接邊表
		else
			return reAdjacentEdges;
	}

	// 取頂點在所屬圖頂點集中的位置
	public Node getVexPosition() {
		return vexPosition;
	}

	// 與頂點通路狀态相關方法
	public boolean isVisited() {
		return visited;
	}

	public void setToVisited() {
		visited = true;
	}

	public void setToUnvisited() {
		visited = false;
	}

	// 取或設定頂點應用資訊
	protected Object getAppObj() {
		return application;
	}

	protected void setAppObj(Object app) {
		application = app;
	}

	// 重置頂點狀态資訊
	public void resetStatus() {
		visited = false;
		application = null;
	}
}
           

雙鍊式存儲結構的邊定義

public class Edge {
	public static final int NORMAL = 0;
	public static final int MST = 1; // MST邊
	public static final int CRITICAL = 2;// 關鍵路徑中的邊
	private int weight; // 權值
	private Object info; // 邊的資訊
	private Node edgePosition; // 邊在邊表中的位置
	private Node firstVexPosition; // 邊的第一頂點在頂點表中的位置
	private Node secondVexPosition; // 邊的第二頂點在頂點表中的位置
	private Node edgeFirstPosition; // 邊在第一（二）頂點的鄰接（逆鄰接）邊表中的位置
	private Node egdeSecondPosition;// 在無向圖中就是在兩個頂點的鄰接表中的位置
	private int type; // 邊的類型
	private int graphType; // 所在圖的類型

	// 構造方法:在圖G中引入一條新邊,其頂點為u、v
	public Edge(Graph g, Vertex u, Vertex v, Object info) {
		this(g, u, v, info, 1);
	}

	public Edge(Graph g, Vertex u, Vertex v, Object info, int weight) {
		this.info = info;
		this.weight = weight;
		edgePosition = g.insert(this);
		firstVexPosition = u.getVexPosition();
		secondVexPosition = v.getVexPosition();
		type = Edge.NORMAL;
		graphType = g.getType();
		if (graphType == Graph.UndirectedGraph) {
			// 如果是無向圖,邊應當加入其兩個頂點的鄰接邊表
			edgeFirstPosition = u.getAdjacentEdges().insertLast(this);
			egdeSecondPosition = v.getAdjacentEdges().insertLast(this);
		} else {
			// 如果是有向圖,邊加入起始點的鄰接邊表,終止點的逆鄰接邊表
			edgeFirstPosition = u.getAdjacentEdges().insertLast(this);
			egdeSecondPosition = v.getReAdjacentEdges().insertLast(this);
		}
	}

	// get&set methods
	public Object getInfo() {
		return info;
	}

	public void setInfo(Object info) {
		this.info = info;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

	public Vertex getFirstVex() {
		return (Vertex) firstVexPosition.getData();
	}

	public Vertex getSecondVex() {
		return (Vertex) secondVexPosition.getData();
	}

	public Node getFirstVexPosition() {
		return firstVexPosition;
	}

	public Node getSecondVexPosition() {
		return secondVexPosition;
	}

	public Node getEdgeFirstPosition() {
		return edgeFirstPosition;
	}

	public Node getEdgeSecondPosition() {
		return egdeSecondPosition;
	}

	public Node getEdgePosition() {
		return edgePosition;
	}

	// 與邊的類型相關的方法
	public void setToMST() {
		type = Edge.MST;
	}

	public void setToCritical() {
		type = Edge.CRITICAL;
	}

	public void resetType() {
		type = Edge.NORMAL;
	}

	public boolean isMSTEdge() {
		return type == Edge.MST;
	}

	public boolean isCritical() {
		return type == Edge.CRITICAL;
	}
}
           

以下兩種存儲方式是第3種在有向圖和無向圖上面的具體化，并且節點用順序存儲結構。而雙鍊式存儲結構節點和邊表都是鍊式存儲結構。

2.4、十字連結清單---->适用于有向圖

它是有向圖的另一種鍊式結構。

思路：将鄰接矩陣用連結清單存儲，是鄰接表、逆鄰接表的結合。

1、每條弧對應一個結點(稱為弧結點，設5個域）

2、每個頂點也對應一個結點（稱為頂點結點，設3個域）

十字連結清單存儲結構描述：

#define MAX_VERTEX_NUM 20

Typedef  struct  ArcBox {               //弧結點結構
   int  tailvex , headvex ;
   struct  ArcBox * hlink , tlink;
   InfoType    *info;
} ArcBox；

Typedef   struct  VexNode{  //頂點結構
    VertexType   data;
     ArcBox   * firstin,*firstout;
} VexNode;  

Typedef   struct { 
      VexNode xlist[  MAX_VERTEX_NUM ];   //表頭向量
      int  vexnum, arcnum;
} OLGraph;    //圖結構
           

例子：

2.5、鄰接多重表---->适用于無向圖

這是無向圖的另一種存儲結構，當對邊操作時，無向圖應采用此種結構存儲。

1、每條邊隻對應一個結點（稱為邊結點），設立6個域；

2、每個頂點也對應一個結點（頂點結點），設立2個域；

無向圖的鄰接多重表存儲表示

typedef struct Ebox {
     VisitIf  mark;   //通路标記
     int  ivex, jvex;  //該邊依附的兩個頂點的位置
     struct EBox  *ilink, *jlink; 
     InfoType  *info;  //該邊資訊指針
} EBox;
typedef struct VexBox {
   VertexType  data;
   EBox  *firstedge; // 指向第一條依附該頂點的邊
} VexBox;
typedef struct {  // 鄰接多重表
    VexBox  adjmulist[MAX_VERTEX_NUM];
     int   vexnum, edgenum;    
} AMLGraph;
           

無向圖鄰接多重表-例子