一、圖的鄰接矩陣實現
1。實現了以頂點陣列、鄰接矩陣為儲存結構的圖；
2。實現了圖的建立（包含有向/無向圖、有向/無向網）、頂點/邊的增刪操作、深度/廣度優先遍歷的演算法；
3。採用頂點物件列表、邊（弧）物件列表的方式，對圖的建立進行初始化；引用 “ObjArrayList。h”標頭檔案，標頭檔案可參看之前博文“資料結構之順序列表（支援物件元素）”程式碼；
4。採用將頂點陣列空位的下標索引入佇列的方式，解決頂點在陣列（靜態）中因增刪操作造成的不連續儲存的問題；引用 “LinkQueue。h”標頭檔案，標頭檔案可參看之前博文“資料結構之佇列（迴圈佇列、鏈佇列的類模板實現）”程式碼；
5。深度優先遍歷採用遞迴演算法；廣度優先遍歷採用佇列方式實現；
6。測試程式碼中以有向網的所有帶權邊作為邊的初始化資料，選擇圖型別（DG， UDG， DN， UDN）可建立成不同型別的圖。
二、測試程式碼中的圖結構圖
深度優先遍歷序列（從 v1 頂點開始）：
1。無向圖/網：v1-v2-v3-v5-v4-v6-v7
2。有向圖/網：v1-v2-v5-v3-v4-v6-v7
廣度優先遍歷序列（從 v2 頂點開始）：
1。無向圖/網：v2-v1-v3-v5-v4-v6-v7
2。有向圖/網：v2-v5 後序無法遍歷
注：有向圖的遍歷 是遵循出度方向遍歷的，若無出度方向，則遍歷終止。
三、程式碼
//檔名：“GraphAdjMat。h”
#pragma once
#ifndef GRAPHADJMAT_H_
#define GRAPHADJMAT_H_
#include
#include
#include “ObjArrayList。h”
#include “LinkQueue。h”
using namespace std；
/*
。 圖（鄰接矩陣實現） Graph Adjacency Matrix
。 相關術語：
。 頂點 Vertex ； 邊 Arc ；權 Weight ；
。 有向圖 Digraph ；無向圖 Undigraph ；
。 有向網 Directed Network ；無向網 Undirected Network ；
*/
class GraphAdjMat
{
/*
。 邊（弧） 單元，注：鄰接矩陣單元
*/
struct ArcCell
{
int adj； //鄰接頂點關係。圖：0|不相鄰 1|相鄰 ；網：無窮（INT_MAX）|不相鄰 權值（W）|相鄰
char * info； //邊（弧）資訊
}；
public：
/*
。 圖 種類
*/
enum GraphType
{
DG， //有向圖，預設 0
UDG， //無向圖，預設 1
DN， //有向網，預設 2
UDN //無向網，預設 3
}；
/*
。 邊（弧）資料，注：供外部初始化邊資料使用
*/
struct ArcData
{
string Tail； //弧尾
string Head； //弧頭
int Weight； //權重
}；
private：
const int _INFINITY = INT_MAX； //無窮大 注：包含於標頭檔案
static const int _MAX_VERTEX_NUM = 10； //支援最大頂點數
//靜態儲存結構
string vexs［_MAX_VERTEX_NUM］； //頂點表
ArcCell arcs［_MAX_VERTEX_NUM］［_MAX_VERTEX_NUM］； //邊（弧）矩陣
int vexNum； //頂點數
int arcNum； //邊數
int type； //圖種類
int nonAdjInt； //不相鄰 int 值：0|無權 無窮|有權
LinkQueue
bool vexs_visited［_MAX_VERTEX_NUM］； //頂點訪問標記陣列：0|未訪問 1|已訪問
void _CreateDG（ObjArrayList
void _CreateUDG（ObjArrayList
void _CreateDN（ObjArrayList
void _CreateUDN（ObjArrayList
int _Locate（string vertex）； //定位頂點元素位置
void _DFS_R（int index）； //深度優先遍歷 遞迴
public：
GraphAdjMat（int type）； //建構函式：初始化圖型別
~GraphAdjMat（）； //解構函式：銷燬圖儲存空間
void Init（ObjArrayList
void Display（）； //顯示 圖|網
void InsertVertex（string *vertex）； //插入一個新頂點
void DeleteVertex（string *vertex）； //刪除一個頂點
void InsertArc（ArcData *arc）； //插入一條新邊（弧）
void DeleteArc（ArcData *arc）； //刪除一條邊（弧）
void Display_DFS（string *vertex）； //從指定頂點開始，深度優先遍歷
void Display_BFS（string *vertex）； //從指定頂點開始，廣度優先遍歷
}；
GraphAdjMat：：GraphAdjMat（int type）
{
/*
。 建構函式：初始化圖型別
*/
this->type = type；
this->vexNum = 0；
this->arcNum = 0；
if （this->type == DG || this->type == UDG）
{
//圖的不相鄰 int 值 0
this->nonAdjInt = 0；
}
else
{
//網的不相鄰 int 值 無窮大
this->nonAdjInt = this->_INFINITY；
}
}
GraphAdjMat：：~GraphAdjMat（）
{
/*
。 解構函式：銷燬圖
*/
//1。釋放頂點空位置索引佇列
int * e；
while （vexs_null_index_queue->GetHead（） ！= NULL）
{
e = vexs_null_index_queue->DeQueue（）；
delete e；
}
delete vexs_null_index_queue；
}
void GraphAdjMat：：Init（ObjArrayList
{
/*
。 初始化頂點、邊資料，並構建 圖|網
。 入參：
。 vexs： 頂點 列表
。 arcsList： 邊資料 列表
*/
//1。初始化頂點資料
if （vexs->Length（） > this->_MAX_VERTEX_NUM）
{
return；
}
for （int i = 0； i < vexs->Length（）； i++）
{
this->vexs［i］ = *vexs->Get（i）；
}
this->vexNum = vexs->Length（）；
//1。1。初始化頂點陣列空頂點位置索引佇列
for （int i = vexs->Length（）； i < _MAX_VERTEX_NUM； i++）
{
vexs_null_index_queue->EnQueue（new int（i））；
}
//2。根據初始化的圖型別，建立指定的圖
switch （this->type）
{
case DG：
_CreateDG（arcsList）； break；
case UDG：
_CreateUDG（arcsList）； break；
case DN：
_CreateDN（arcsList）； break；
case UDN：
_CreateUDN（arcsList）； break；
default：
break；
}
}
void GraphAdjMat：：_CreateDG（ObjArrayList
{
/*
。 建立有向圖
。 頂點相鄰關係：0|不相鄰 1|相鄰
。 鄰接矩陣為 非對稱矩陣
*/
//初始化臨時 邊物件
ArcData * arcData = NULL；
//初始化 矩陣二維座標
int m = 0， n = 0；
//初始化邊的鄰接矩陣
for （int i = 0； i < _MAX_VERTEX_NUM； i++）
{
for （int j = 0； j < _MAX_VERTEX_NUM； j++）
{
this->arcs［i］［j］。adj = 0；
this->arcs［i］［j］。info = NULL；
}
}
//遍歷邊資料列表
for （int i = 0； i < arcsList->Length（）； i++）
{
//按序獲取邊（弧）
arcData = arcsList->Get（i）；
//定位（或設定）邊的兩端頂點位置
m = _Locate（arcData->Tail）；
n = _Locate（arcData->Head）；
//設定頂點相鄰 為 1 （無向）
if （this->arcs［m］［n］。adj == 1）
{
//去除重複邊
continue；
}
this->arcs［m］［n］。adj = 1；
//邊 計數
this->arcNum++；
}
}
void GraphAdjMat：：_CreateUDG（ObjArrayList
{
/*
。 建立無向圖
。 頂點相鄰關係：0|不相鄰 1|相鄰
。 鄰接矩陣為 對稱矩陣
*/
//初始化臨時 邊物件
ArcData * arcData = NULL；
//初始化 矩陣二維座標
int m = 0， n = 0；
//初始化邊的鄰接矩陣
for （int i = 0； i < _MAX_VERTEX_NUM； i++）
{
for （int j = 0； j < _MAX_VERTEX_NUM； j++）
{
this->arcs［i］［j］。adj = 0；
this->arcs［i］［j］。info = NULL；
}
}
//遍歷邊資料列表
for （int i = 0； i < arcsList->Length（）； i++）
{
//按序獲取邊（弧）
arcData = arcsList->Get（i）；
//定位（或設定）邊的兩端頂點位置
m = _Locate（arcData->Tail）；
n = _Locate（arcData->Head）；
//設定頂點相鄰 為 1 （有向）
if （this->arcs［m］［n］。adj == 1 || this->arcs［n］［m］。adj == 1）
{
//去除重複邊
continue；
}
this->arcs［m］［n］。adj = 1；
this->arcs［n］［m］。adj = 1；
//邊 計數
this->arcNum++；
}
}
void GraphAdjMat：：_CreateDN（ObjArrayList
{
/*
。 建立有向網
。 頂點相鄰關係：infinity|不相鄰 w|相鄰
。 鄰接矩陣為 非對稱矩陣
*/
//初始化臨時 邊物件
ArcData * arcData = NULL；
//初始化 矩陣二維座標
int m = 0， n = 0；
//初始化邊的鄰接矩陣
for （int i = 0； i < _MAX_VERTEX_NUM； i++）
{
for （int j = 0； j < _MAX_VERTEX_NUM； j++）
{
this->arcs［i］［j］。adj = this->_INFINITY； //無窮大
this->arcs［i］［j］。info = NULL；
}
}
//遍歷邊資料列表
for （int i = 0； i < arcsList->Length（）； i++）
{
//按序獲取邊（弧）
arcData = arcsList->Get（i）；
//定位（或設定）邊的兩端頂點位置
m = _Locate（arcData->Tail）；
n = _Locate（arcData->Head）；
//設定頂點相鄰 為 weight 權重
if （this->arcs［m］［n］。adj ！= this->_INFINITY）
{
//去除重複邊
continue；
}
this->arcs［m］［n］。adj = arcData->Weight；
//邊 計數
this->arcNum++；
}
}
void GraphAdjMat：：_CreateUDN（ObjArrayList
{
/*
。 建立無向網
。 頂點相鄰關係：infinity|不相鄰 w|相鄰
。 鄰接矩陣為 對稱矩陣
*/
//初始化臨時 邊物件
ArcData * arcData = NULL；
//初始化 矩陣二維座標
int m = 0， n = 0；
//初始化邊的鄰接矩陣
for （int i = 0； i < _MAX_VERTEX_NUM； i++）
{
for （int j = 0； j < _MAX_VERTEX_NUM； j++）
{
this->arcs［i］［j］。adj = this->_INFINITY； //無窮大
this->arcs［i］［j］。info = NULL；
}
}
//遍歷邊資料列表
for （int i = 0； i < arcsList->Length（）； i++）
{
//按序獲取邊（弧）
arcData = arcsList->Get（i）；
//定位（或設定）邊的兩端頂點位置
m = _Locate（arcData->Tail）；
n = _Locate（arcData->Head）；
//設定頂點相鄰 為 weight 權重
if （this->arcs［m］［n］。adj ！= this->_INFINITY || this->arcs［n］［m］。adj ！= this->_INFINITY）
{
//去除重複邊
continue；
}
if （arcData->Weight == this->_INFINITY）
{
//去除權重為 無窮 的邊
continue；
}
this->arcs［m］［n］。adj = arcData->Weight；
this->arcs［n］［m］。adj = arcData->Weight；
//邊 計數
this->arcNum++；
}
}
int GraphAdjMat：：_Locate（string vertex）
{
/*
。 定位頂點元素位置
。 後期可改成【字典樹】，頂點數超過100個後定位頂點位置可更快
*/
//遍歷定位頂點位置
for （int i = 0； i < this->_MAX_VERTEX_NUM； i++）
{
if （vertex == this->vexs［i］）
{
return i；
}
}
cout << endl << “頂點［” << vertex << “］不存在。” << endl；
return -1；
}
void GraphAdjMat：：Display（）
{
/*
。 顯示 圖|網 （輸出頂點陣列、鄰接矩陣）
*/
//顯示頂點陣列
//注：當刪除某個中間序號頂點後，頂點陣列就不是連續的
cout << endl << “頂點陣列：” << endl；
for （int i = 0， num = 0； i < this->_MAX_VERTEX_NUM && num < this->vexNum； i++）
{
if （this->vexs［i］ ！= “”）
{
cout << “ （” << i << “）” << this->vexs［i］；
num++；
}
}
//顯示邊（鄰接矩陣）
cout << endl << “邊（鄰接矩陣）：” << endl；
cout << “ ”；
for （int i = 0； i < this->_MAX_VERTEX_NUM； i++）
{
cout << “［” << i << “］”；
}
cout << endl；
for （int i = 0； i < this->_MAX_VERTEX_NUM； i++）
{
cout << “［” << i << “］ ”；
for （int j = 0； j < this->_MAX_VERTEX_NUM； j++）
{
if （this->arcs［i］［j］。adj == this->_INFINITY）
cout << “ + ”；
else
cout << “ ” << this->arcs［i］［j］。adj << “ ”；
}
cout << endl；
}
}
void GraphAdjMat：：InsertVertex（string *vertex）
{
/*
。 插入一個新頂點
*/
//1。判斷頂點是否已存在
if （_Locate（*vertex） > -1）
{
cout << endl << “該頂點已存在。” << endl；
return；
}
//2。判斷頂點數是否達到上限
if （this->vexNum >= this->_MAX_VERTEX_NUM）
{
cout << endl << “頂點數已達上限。” << endl；
return；
}
//3。插入新頂點，並自增頂點總數
int * index = vexs_null_index_queue->DeQueue（）； //從空位置索引佇列中取
this->vexs［*index］ = *vertex；
this->vexNum++；
//4。新增的頂點在鄰接矩陣中不需要作任何操作（已初始化）
}
void GraphAdjMat：：DeleteVertex（string *vertex）
{
/*
。 刪除一個頂點
*/
//1。判斷頂點是否已存在
int index = _Locate（*vertex）；
if （index == -1）
{
cout << endl << “該頂點不存在。” << endl；
return；
}
//2。刪除該頂點，並自減頂點總數
this->vexs［index］ = “”；
this->vexNum——；
//3。清除鄰接矩陣 index 行列的資料，即將此行列 恢復初始化狀態
if （this->type == DG || this->type == UDG）
{
//圖
for （int i = 0； i < this->_MAX_VERTEX_NUM； i++）
{
this->arcs［i］［index］。adj = 0；
this->arcs［index］［i］。adj = 0；
}
}
else
{
//網
for （int i = 0； i < this->_MAX_VERTEX_NUM； i++）
{
this->arcs［i］［index］。adj = this->_INFINITY；
this->arcs［index］［i］。adj = this->_INFINITY；
}
}
}
void GraphAdjMat：：InsertArc（ArcData *arc）
{
/*
。 插入一條新邊（弧）
。 若已存在，將對其更新
*/
//1。定位頂點位置
int i = _Locate（arc->Tail）；
int j = _Locate（arc->Head）；
//2。判斷頂點是否存在
if （i == -1 || j == -1）
{
cout << endl << “該邊頂點不存在。” << endl；
return；
}
//3。插入/更新一條邊
if （this->type == DG）
{
//有向無權圖
this->arcs［i］［j］。adj = 1；
}
else if （this->type == UDG）
{
//無向無權圖
this->arcs［i］［j］。adj = 1；
this->arcs［j］［i］。adj = 1；
}
else if （this->type == DN）
{
//有向有權網
this->arcs［i］［j］。adj = arc->Weight；
}
else
{
//無向有權網
this->arcs［i］［j］。adj = arc->Weight；
this->arcs［j］［i］。adj = arc->Weight；
}
}
void GraphAdjMat：：DeleteArc（ArcData *arc）
{
/*
。 刪除一條邊（弧）
*/
//1。定位頂點位置
int i = _Locate（arc->Tail）；
int j = _Locate（arc->Head）；
//2。判斷頂點是否存在
if （i == -1 || j == -1）
{
cout << endl << “該邊頂點不存在。” << endl；
return；
}
//3。刪除一條邊，即 恢復初始化狀態
if （this->type == DG）
{
//有向無權圖
this->arcs［i］［j］。adj = 0；
}
else if （this->type == UDG）
{
//無向無權圖
this->arcs［i］［j］。adj = 0；
this->arcs［j］［i］。adj = 0；
}
else if （this->type == DN）
{
//有向有權網
this->arcs［i］［j］。adj = this->_INFINITY；
}
else
{
//無向有權網
this->arcs［i］［j］。adj = this->_INFINITY；
this->arcs［j］［i］。adj = this->_INFINITY；
}
}
void GraphAdjMat：：Display_DFS（string *vertex）
{
/*
。 深度優先遍歷顯示，從指定頂點開始
*/
//1。判斷頂點是否存在
int index = _Locate（*vertex）；
if （index == -1）
return；
//2。初始化頂點訪問陣列
for （int i = 0； i < this->_MAX_VERTEX_NUM； i++）
{
this->vexs_visited［i］ = 0；
}
//3。深度優先遍歷 遞迴
cout << “深度優先遍歷：（從頂點” << *vertex << “開始）” << endl；
_DFS_R（index）；
}
void GraphAdjMat：：_DFS_R（int index）
{
/*
。 深度優先遍歷 遞迴
。 有向/無向演算法是一樣的
。 有向圖|網，以當前頂點的出度方向遍歷
。 無向圖|網，以當前頂點的相鄰結點方向遍歷（可理解為“出度”，但不是出度）
*/
//1。訪問頂點，並標記已訪問
cout << this->vexs［index］ << “ ”；
this->vexs_visited［index］ = 1；
//2。訪問其相鄰頂點
for （int i = 0； i < this->_MAX_VERTEX_NUM； i++）
{
//當邊值 不是 不相鄰int值（0|無權 無窮|有權），且未被訪問過時，可訪問
if （this->arcs［index］［i］。adj ！= this->nonAdjInt && this->vexs_visited［i］ ！= 1）
{
_DFS_R（i）；
}
}
}
void GraphAdjMat：：Display_BFS（string *vertex）
{
/*
。 廣度優先遍歷顯示，從指定頂點開始
。 類似於樹的層次遍歷演算法
*/
//1。判斷頂點是否存在
int index = _Locate（*vertex）；
if （index == -1）
return；
//2。初始化頂點訪問陣列
for （int i = 0； i < this->_MAX_VERTEX_NUM； i++）
{
this->vexs_visited［i］ = 0；
}
//3。廣度優先遍歷
cout << “廣度優先遍歷：（從頂點” << *vertex << “開始）” << endl；
//3。1。初始化佇列
LinkQueue
//3。2。訪問開始頂點，並標記訪問、入隊
cout << this->vexs［index］ << “ ”；
this->vexs_visited［index］ = 1；
vexQ->EnQueue（new int（index））；
//3。3。出隊，並遍歷鄰接頂點（下一層次），訪問後入隊
while （vexQ->GetHead（） ！= NULL）
{
index = * vexQ->DeQueue（）；
for （int j = 0； j < _MAX_VERTEX_NUM； j++）
{
//未訪問過的鄰接頂點
if （this->arcs［index］［j］。adj ！= this->nonAdjInt && this->vexs_visited［j］ ！= 1）
{
//訪問頂點，並標記訪問、入隊
cout << this->vexs［j］ << “ ”；
this->vexs_visited［j］ = 1；
vexQ->EnQueue（new int（j））；
}
}
}
//4。釋放佇列
int * e；
while （vexQ->GetHead（） ！= NULL）
{
e = vexQ->DeQueue（）；
delete e；
}
delete vexQ；
}
#endif // ！GRAPHADJMAT_H_
//檔名：“GraphAdjMat_Test。cpp”
#include “stdafx。h”
#include
#include “GraphAdjMat。h”
#include “ObjArrayList。h”
using namespace std；
int main（）
{
//初始化頂點資料
string * v1 = new string（“v1”）；
string * v2 = new string（“v2”）；
string * v3 = new string（“v3”）；
string * v4 = new string（“v4”）；
string * v5 = new string（“v5”）；
string * v6 = new string（“v6”）；
string * v7 = new string（“v7”）；
ObjArrayList
vexs->Add（v1）；
vexs->Add（v2）；
vexs->Add（v3）；
vexs->Add（v4）；
vexs->Add（v5）；
vexs->Add（v6）；
vexs->Add（v7）；
//初始化邊（弧）資料
GraphAdjMat：：ArcData * arc1 = new GraphAdjMat：：ArcData{ “v1”， “v2”， 2 }；
GraphAdjMat：：ArcData * arc2 = new GraphAdjMat：：ArcData{ “v1”， “v3”， 3 }；
GraphAdjMat：：ArcData * arc3 = new GraphAdjMat：：ArcData{ “v1”， “v4”， 4 }；
GraphAdjMat：：ArcData * arc4 = new GraphAdjMat：：ArcData{ “v3”， “v1”， 5 }；
GraphAdjMat：：ArcData * arc5 = new GraphAdjMat：：ArcData{ “v3”， “v2”， 6 }；
GraphAdjMat：：ArcData * arc6 = new GraphAdjMat：：ArcData{ “v3”， “v5”， 7 }；
GraphAdjMat：：ArcData * arc7 = new GraphAdjMat：：ArcData{ “v2”， “v5”， 8 }；
GraphAdjMat：：ArcData * arc8 = new GraphAdjMat：：ArcData{ “v4”， “v6”， 9 }；
GraphAdjMat：：ArcData * arc9 = new GraphAdjMat：：ArcData{ “v4”， “v7”， 9 }；
GraphAdjMat：：ArcData * arc10 = new GraphAdjMat：：ArcData{ “v6”， “v7”， 9 }；
ObjArrayList
arcsList->Add（arc1）；
arcsList->Add（arc2）；
arcsList->Add（arc3）；
arcsList->Add（arc4）；
arcsList->Add（arc5）；
arcsList->Add（arc6）；
arcsList->Add（arc7）；
arcsList->Add（arc8）；
arcsList->Add（arc9）；
arcsList->Add（arc10）；
//測試1：無向圖
cout << endl << “無向圖初始化：” << endl；
GraphAdjMat * udg = new GraphAdjMat（GraphAdjMat：：UDG）；
udg->Init（vexs， arcsList）；
udg->Display（）；
//1。1。深度優先遍歷
cout << endl << “無向圖深度優先遍歷序列：” << endl；
udg->Display_DFS（v1）；
//1。2。廣度優先遍歷
cout << endl << “無向圖廣度優先遍歷序列：” << endl；
udg->Display_BFS（v2）；
//1。3。插入新頂點、新邊
cout << endl << “無向圖插入新頂點、新邊：” << endl；
udg->InsertVertex（new string（“v8”））；
udg->InsertArc（new GraphAdjMat：：ArcData{ “v8”， “v1”， 8 }）；
udg->Display（）；
//1。4。刪除頂點、邊
cout << endl << “無向圖刪除頂點v1、邊arc9：” << endl；
udg->DeleteVertex（v1）；
udg->DeleteArc（arc9）；
udg->Display（）；
//測試2：有向圖
cout << endl << “有向圖：” << endl；
GraphAdjMat * dg = new GraphAdjMat（GraphAdjMat：：DG）；
dg->Init（vexs， arcsList）；
dg->Display（）；
//2。1。深度優先遍歷
cout << endl << “有向圖深度優先遍歷序列：” << endl；
dg->Display_DFS（v1）；
//2。2。廣度優先遍歷
cout << endl << “有向圖廣度優先遍歷序列：” << endl；
dg->Display_BFS（v2）；
//測試：無向網
cout << endl << “無向網：” << endl；
GraphAdjMat * udn = new GraphAdjMat（GraphAdjMat：：UDN）；
udn->Init（vexs， arcsList）；
udn->Display（）；
//測試：有向網
cout << endl << “有向網：” << endl；
GraphAdjMat * dn = new GraphAdjMat（GraphAdjMat：：DN）；
dn->Init（vexs， arcsList）；
dn->Display（）；
return 0；
}
