圖的存儲

鄰接矩陣法

鄰接矩陣存儲不帶權圖

0 - 表示兩個頂點不鄰接

1 - 表示兩個頂點鄰接

在無向圖中，每條邊在矩陣中對應兩個1

在有向圖中，每條邊在矩陣中對應一個1

//不帶權圖的鄰接矩陣存儲
#define MaxVertexNum 100		//頂點數目的最大值
typedef struct{char Vex[MaxVertexNum];int Edge[MaxVertexNum][MaxVertexNum];		//鄰接矩陣，邊表int vexnum,arcnum;			//圖當前頂點數和邊數/弧數
}MGraph;

因為矩陣中只需要存放0和1，所以也可以將Edge（二維數組）定義為bool類型或枚舉類型，讓矩陣變得更小，節省存儲空間

求頂點的度、入度、出度

無向圖：第i個頂點的度 = 第i行（或第i列）的非零元素個數 時間復雜度O(|V|)

有向圖：第i個頂點的入度 = 第i行的非零元素個數 時間復雜度O(|V|)

? 第i個頂點的出度 = 第i列的非零元素個數 時間復雜度O(|V|)

? 第i個頂點的度 = 第i行和第i列的非零元素個數之和 時間復雜度O(|V|)

鄰接矩陣存儲帶權圖（網）

//鄰接矩陣存儲帶權圖（網）
#define MaxVertexNum 100		//頂點數目的最大值
#define INFINITY 最大的int值	//宏定義常量“無窮”		使用int的上限值表示“無窮”
typedef char VertexType;		//頂點的數據類型
typedef int EdgeType;			//帶權圖中邊上權值的數據類型
typedef struct{VertexType Vex[MaxVertexNum];			//頂點EdgeType Edge[MaxVertexNum][MaxVertexNum];		//邊的權int vexnum,arcnum;			//圖的當前定點數和弧數
}

若兩個頂點間沒有邊，則權值為無窮

也有一些教材將一個頂點與自身的權值記作0，所以在使用鄰接矩陣表示帶權圖（網）時，如果兩個點之間權值為0或∞，則代表這兩個頂點間沒有邊

鄰接矩陣法的性能分析

空間復雜度：O(|V|²) – 只和頂點數相關，和實際邊數無關

當邊數較少時，有大量的空間被浪費，所以鄰接矩陣法適用于存儲稠密圖

無向圖的鄰接矩陣是對稱矩陣，可以進行壓縮存儲（只存儲上三角區/下三角區）

鄰接矩陣的性質

設圖G的鄰接矩陣為A（矩陣元素為0/1），則Aⁿ的元素Aⁿ[i][j]等于由頂點i到頂點j的長度為n的路徑的數目

鄰接表法（順序+鏈式存儲）

//用鄰接表存儲的圖
typedef struct{AdjList vertices;int vexnum,arcnum;
}ALGraph;
//頂點
typedef struct VNode{VertexType data;	//頂點信息ArcNode *first;		//第一條邊/弧    
}VNode,AdjList[MaxVertexNum];
//“邊/弧”
typedef struct ArcNode{int adjvex;		//邊/弧指向哪個結點struct ArcNode *next;		//指向下一條弧的指針//InfoType info			//邊權值
}ArcNode;//與樹的孩子表示法相同

空間復雜度

無向圖：邊結點的數量為2|E|，整體的空間復雜度為O(|V|+2|E|)

有向圖：邊結點的數量為|E|，整體的空間復雜度為O(|V|+|E|)

求頂點的度、入度、出度

無向圖：度 = 頂點指向的邊鏈表中結點的數量

有向圖：度 = 入度 + 出度

? 出度 = 頂點指向的邊鏈表中結點的數量

? 入度 = 指向當前結點的弧的數量（需要遍歷所有結點的邊鏈表）

同一個圖的鄰接表表示方式不唯一（邊鏈表各結點的順序是任意的）

鄰接表和鄰接矩陣

	鄰接表	鄰接矩陣
空間復雜度	無向圖：O(|V|+2|E|)；有向圖：O(|V|+|E|)	O(|V|2)
適用于	存儲稀疏圖	存儲稠密圖
表示方式	不唯一	唯一
計算度/入度/出度	計算有向圖的度和入度不方便，其余很方便	必須遍歷對應的行和列
找相鄰的邊	找有向圖的入邊不方便，其余很方便	必須遍歷對應的行和列

十字鏈表法、鄰接多重表

十字鏈表法（存儲有向圖）

【有向圖存儲】

鄰接表：入度、入邊尋找計算不方便

鄰接矩陣：空間復雜度高

空間復雜度：O(|V|+|E|)

找出邊：順著綠色線路找

找入邊：順著橙色路線找

注意：十字鏈表法只能用于存儲有向圖

鄰接多重表（存儲無向圖）

【存儲無向圖】

鄰接表：每條邊對應兩份冗余信息，刪除頂點、刪除邊時間復雜度高

鄰接矩陣：空間復雜度高

空間復雜度：O(|V|+|E|)

刪除邊、刪除節點等操作很方便

注意：鄰接多重表只適用于存儲無向圖

小結

	鄰接表	鄰接矩陣	十字鏈表法	鄰接多重表
空間復雜度	無向圖：O(|V|+2|E|)；有向圖：O(|V|+|E|)	O(|V|2)	O(|V|+|E|)	O(|V|+|E|)
適用于	存儲稀疏圖	存儲稠密圖	只能存有向圖	只能存無向圖
表示方式	不唯一	唯一	不唯一	不唯一
刪除邊或頂點	無向圖中刪除邊或刪除頂點都不方便	刪除邊很方便，刪除頂點需要大量移動數據	很方便	很方便
找相鄰的邊	找有向圖的入邊必須遍歷整個鄰接表	遍歷對應行或列，時間復雜度O(|V|)	很方便	很方便