//文件名："GraphAdjList.h"
#pragma once
#ifndef GRAPHADJLISL_H_
#define GRAPHADJLISL_H_
 
#include <string>
#include "ObjArrayList.h"
using namespace std;
 
/*
. 圖（鄰接表實現(xiàn)） Graph Adjacency List
. 相關術語：
. 頂點 Vertex ； 邊 Arc ；權 Weight ；
. 有向圖 Digraph ；無向圖 Undigraph ；
. 有向網(wǎng) Directed Network ；無向網(wǎng) Undirected Network ；
. 存儲結構：
. 1.頂點表只能采用順序結構。（因為若采用鏈式結構，頂點結點定義與邊表結點定義就相互引用，無法定義）
. 2.邊表采用鏈表結構。
*/
 
class GraphAdjList
{
 /*
 . 邊表（鏈表）結點
 */
 struct ArcNode
 {
 int adjVex; //鄰接頂點所在表中下標
 int weight; //邊權重
 ArcNode * next; //下一條邊
 };
 /*
 . 頂點表（順序表）結點
 */
 struct VNode
 {
 string name; //頂點名
 ArcNode * first; //指向的第一個依附該頂點的頂點邊結點
 };
public:
 /*
 . 圖 種類
 */
 enum GraphType
 {
 DG, //有向圖，默認 0
 UDG, //無向圖，默認 1
 DN, //有向網(wǎng)，默認 2
 UDN //無向網(wǎng)，默認 3
 };
 /*
 . 邊（弧）數(shù)據(jù)，注：供外部初始化邊數(shù)據(jù)使用
 */
 struct ArcData
 {
 string Tail; //弧尾
 string Head; //弧頭
 int Weight; //權重
 };
 
private:
 static const int _MAX_VERTEX_NUM = 10; //支持最大頂點數(shù)
 
 VNode vexs[_MAX_VERTEX_NUM]; //頂點表
 int vexs_visited[_MAX_VERTEX_NUM]; //頂點訪問標記數(shù)組：0|未訪問 1|已訪問
 int vexNum; //頂點數(shù)
 int arcNum; //邊數(shù)
 int type; //圖種類
 
 void _CreateVexSet(ObjArrayList<string> * vexs); //創(chuàng)建頂點集合
 void _CreateDG(ObjArrayList<ArcData> * arcsList); //創(chuàng)建有向圖
 void _CreateUDG(ObjArrayList<ArcData> * arcsList); //創(chuàng)建無向圖
 void _CreateDN(ObjArrayList<ArcData> * arcsList); //創(chuàng)建有向網(wǎng)
 void _CreateUDN(ObjArrayList<ArcData> * arcsList); //創(chuàng)建無向網(wǎng)
 
 int _Locate(string vertex);   //定位頂點元素位置
 void _InsertArc(int tail, int head, int weight); //插入邊（元操作，不分有向/無向）
 void _DeleteArc(int tail, int head);  //刪除邊（元操作，不分有向/無向）
 void _DFS_R(int index);   //深度優(yōu)先遍歷 遞歸
 void _DFS(int index);   //深度優(yōu)先遍歷 非遞歸
 
public:
 GraphAdjList(int type); //構造函數(shù)：初始化圖種類
 ~GraphAdjList();  //析構函數(shù)
 void Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList); //初始化頂點、邊數(shù)據(jù)為 圖|網(wǎng)
 void InsertArc(ArcData * arcData); //插入邊（含有向/無向操作）
 void DeleteArc(ArcData * arcData); //刪除邊（含有向/無向操作）
 void Display();  //顯示 圖|網(wǎng)
 void Display_DFS_R(string *vertex); //從指定頂點開始，深度優(yōu)先 遞歸 遍歷
 void Display_DFS(string *vertex); //從指定頂點開始，深度優(yōu)先 非遞歸 遍歷
 void Display_BFS(string *vertex); //從指定頂點開始，廣度優(yōu)先遍歷
 
};

//文件名："GraphAdjList.cpp"
#include "stdafx.h"
#include <string>
#include "ObjArrayList.h"
#include "LinkQueue.h"
#include "LinkStack.h"
#include "GraphAdjList.h"
using namespace std;
 
GraphAdjList::GraphAdjList(int type)
{
 /*
 . 構造函數(shù)：初始化圖類型
 */
 this->type = type;
 this->vexNum = 0;
 this->arcNum = 0;
}
 
GraphAdjList::~GraphAdjList()
{
 /*
 . 析構函數(shù)：銷毀圖
 */
}
 
void GraphAdjList::Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList)
{
 /*
 . 初始化頂點、邊數(shù)據(jù)，并構建 圖|網(wǎng)
 . 入?yún)ⅲ?
 . vexs: 頂點 列表
 . arcsList: 邊數(shù)據(jù) 列表
 */
 //1.創(chuàng)建頂點集
 _CreateVexSet(vexs);
 //2.根據(jù)圖類型，創(chuàng)建指定的圖
 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 GraphAdjList::_CreateVexSet(ObjArrayList<string> * vexs)
{
 /*
 . 創(chuàng)建頂點集合
 */
 string vertex = "";
 //頂點最大數(shù)校驗
 if (vexs->Length() > this->_MAX_VERTEX_NUM)
 {
 return;
 }
 //遍歷頂點表，無重復插入頂點，并計數(shù)頂點數(shù)
 for (int i = 0; i < vexs->Length(); i++)
 {
 vertex = *vexs->Get(i);
 if (_Locate(vertex) == -1)
 {
 this->vexs[this->vexNum].name = vertex;
 this->vexs[this->vexNum].first = NULL;
 this->vexNum++;
 }
 }
}
 
void GraphAdjList::_CreateDG(ObjArrayList<ArcData> * arcsList)
{
 /*
 . 創(chuàng)建有向圖
 . 鄰接矩陣為 非對稱邊
 */
 //初始化臨時 邊對象
 ArcData * arcData = NULL;
 //初始化 Tail Head 頂點下標索引
 int tail = 0, head = 0;
 //遍歷邊數(shù)據(jù)列表
 for (int i = 0; i < arcsList->Length(); i++)
 {
 //按序獲取邊（?。?
 arcData = arcsList->Get(i);
 //定位（或設置）邊的兩端頂點位置
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //插入邊
 _InsertArc(tail, head, 0);
 }
}
 
void GraphAdjList::_CreateUDG(ObjArrayList<ArcData> * arcsList)
{
 /*
 . 創(chuàng)建無向圖
 . 鄰接矩陣為 對稱邊
 */
 //初始化臨時 邊對象
 ArcData * arcData = NULL;
 //初始化 Tail Head 頂點下標索引
 int tail = 0, head = 0;
 //遍歷邊數(shù)據(jù)列表
 for (int i = 0; i < arcsList->Length(); i++)
 {
 //按序獲取邊（?。?
 arcData = arcsList->Get(i);
 //定位（或設置）邊的兩端頂點位置
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //插入對稱邊
 _InsertArc(tail, head, 0);
 _InsertArc(head, tail, 0);
 }
}
 
void GraphAdjList::_CreateDN(ObjArrayList<ArcData> * arcsList)
{
 /*
 . 創(chuàng)建有向網(wǎng)
 . 鄰接矩陣為 非對稱矩陣
 */
 //初始化臨時 邊對象
 ArcData * arcData = NULL;
 //初始化 Tail Head 頂點下標索引
 int tail = 0, head = 0;
 //遍歷邊數(shù)據(jù)列表
 for (int i = 0; i < arcsList->Length(); i++)
 {
 //按序獲取邊（?。?
 arcData = arcsList->Get(i);
 //定位（或設置）邊的兩端頂點位置
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //插入邊
 _InsertArc(tail, head, arcData->Weight);
 }
}
 
void GraphAdjList::_CreateUDN(ObjArrayList<ArcData> * arcsList)
{
 /*
 . 創(chuàng)建無向網(wǎng)
 . 鄰接矩陣為 對稱矩陣
 */
 //初始化臨時 邊對象
 ArcData * arcData = NULL;
 //初始化 Tail Head 頂點下標索引
 int tail = 0, head = 0;
 //遍歷邊數(shù)據(jù)列表
 for (int i = 0; i < arcsList->Length(); i++)
 {
 //按序獲取邊（弧）
 arcData = arcsList->Get(i);
 //定位（或設置）邊的兩端頂點位置
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //插入對稱邊
 _InsertArc(tail, head, arcData->Weight);
 _InsertArc(head, tail, arcData->Weight);
 }
}
 
int GraphAdjList::_Locate(string vertex)
{
 /*
 . 定位頂點元素位置
 . 后期可改成【字典樹】，頂點數(shù)超過100個后定位頂點位置可更快
 */
 //遍歷定位頂點位置
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 if (vertex == this->vexs[i].name)
 {
 return i;
 }
 }
 //cout << endl << "頂點[" << vertex << "]不存在。" << endl;
 return -1;
}
 
void GraphAdjList::_InsertArc(int tail, int head, int weight)
{
 /*
 . 插入邊（元操作，不分有向/無向）
 */
 //邊結點指針：初始化為 弧尾 指向的第一個邊
 ArcNode * p = this->vexs[tail].first;
 //初始化 前一邊結點的指針
 ArcNode * q = NULL;
 //重復邊布爾值
 bool exist = false;
 //1.邊的重復性校驗
 while (p != NULL)
 {
 //若已存在該邊，則標記為 存在 true
 if (p->adjVex == head)
 {
 exist = true;
 break;
 }
 //若不是該邊，繼續(xù)下一個邊校驗
 q = p;
 p = p->next;
 }
 //2.1.如果邊存在，則跳過，不做插入
 if (exist)
 return;
 //2.2.邊不存在時，創(chuàng)建邊
 ArcNode * newArc = new ArcNode();
 newArc->adjVex = head;
 newArc->weight = weight;
 newArc->next = NULL;
 //3.1.插入第一條邊
 if (q == NULL)
 {
 this->vexs[tail].first = newArc;
 }
 //3.2.插入后序邊
 else
 {
 q->next = newArc;
 }
 //4.邊 計數(shù)
 this->arcNum++;
}
 
void GraphAdjList::InsertArc(ArcData * arcData)
{
 /*
 . 插入邊（含有向/無向操作）
 */
 //初始化 Tail Head 頂點下標索引
 int tail = 0, head = 0;
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //根據(jù)圖類型，插入邊
 switch (this->type)
 {
 case DG:
 _InsertArc(tail, head, 0);
 break;
 case UDG:
 _InsertArc(tail, head, 0);
 _InsertArc(head, tail, 0);
 break;
 case DN:
 _InsertArc(tail, head, arcData->Weight);
 break;
 case UDN:
 _InsertArc(tail, head, arcData->Weight);
 _InsertArc(head, tail, arcData->Weight);
 break;
 default:
 break;
 }
}
 
void GraphAdjList::_DeleteArc(int tail, int head)
{
 /*
 . 刪除邊（元操作，不分有向/無向）
 */
 //邊結點指針：初始化為 弧尾 指向的第一個邊
 ArcNode * p = this->vexs[tail].first;
 //初始化 前一邊結點的指針
 ArcNode * q = NULL;
 //1.遍歷查找邊
 while (p != NULL)
 {
 //若存在該邊，則結束循環(huán)
 if (p->adjVex == head)
 {
 break;
 }
 //若不是該邊，繼續(xù)下一個邊
 q = p;
 p = p->next;
 }
 //2.1.邊不存在
 if (p == NULL)
 {
 cout << endl << "邊[" << this->vexs[head].name << "->" << this->vexs[head].name << "]不存在。" << endl;
 return;
 }
 //2.2.邊存在，刪除邊
 //2.2.1.若為第一條邊
 if (q == NULL)
 {
 this->vexs[tail].first = p->next;
 }
 //2.2.2.非第一條邊
 else
 {
 q->next = p->next;
 }
 //3.釋放 p
 delete p;
}
 
void GraphAdjList::DeleteArc(ArcData * arcData)
{
 /*
 . 刪除邊（含有向/無向操作）
 */
 //初始化 Tail Head 頂點下標索引
 int tail = 0, head = 0;
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //根據(jù)圖類型，刪除邊
 switch (this->type)
 {
 case DG:
 _DeleteArc(tail, head);
 break;
 case UDG:
 _DeleteArc(tail, head);
 _DeleteArc(head, tail);
 break;
 case DN:
 _DeleteArc(tail, head);
 break;
 case UDN:
 _DeleteArc(tail, head);
 _DeleteArc(head, tail);
 break;
 default:
 break;
 }
}
 
void GraphAdjList::Display()
{
 /*
 . 顯示 圖|網(wǎng)
 */
 //初始化邊表結點指針
 ArcNode * p = NULL;
 cout << endl << "鄰接表：" << endl;
 //遍歷頂點表
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 //空頂點（在刪除頂點的操作后會出現(xiàn)此類情況）
 if (this->vexs[i].name == "")
 {
 continue;
 }
 //輸出頂點
 cout << "[" << i << "]" << this->vexs[i].name << " ";
 //遍歷輸出邊頂點
 p = this->vexs[i].first;
 while (p != NULL)
 {
 cout << "[" << p->adjVex << "," << p->weight << "] ";
 p = p->next;
 }
 cout << endl;
 }
}
 
void GraphAdjList::_DFS_R(int index)
{
 /*
 . 深度優(yōu)先遍歷 遞歸
 */
 //1.訪問頂點，并標記已訪問
 cout << this->vexs[index].name << " ";
 this->vexs_visited[index] = 1;
 //2.遍歷訪問其相鄰頂點
 ArcNode * p = this->vexs[index].first;
 int adjVex = 0;
 while (p != NULL)
 {
 adjVex = p->adjVex;
 //當頂點未被訪問過時，可訪問
 if (this->vexs_visited[adjVex] != 1)
 {
 _DFS_R(adjVex);
 }
 p = p->next;
 }
}
 
void GraphAdjList::Display_DFS_R(string *vertex)
{
 /*
 . 從指定頂點開始，深度優(yōu)先 遞歸 遍歷
 */
 //1.判斷頂點是否存在
 int index = _Locate(*vertex);
 if (index == -1)
 return;
 //2.初始化頂點訪問數(shù)組
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 this->vexs_visited[i] = 0;
 }
 //3.深度優(yōu)先遍歷 遞歸
 cout << "深度優(yōu)先遍歷（遞歸）：（從頂點" << *vertex << "開始）" << endl;
 _DFS_R(index);
}
 
void GraphAdjList::_DFS(int index)
{
 /*
 . 深度優(yōu)先遍歷 非遞歸
 */
 //1.訪問第一個結點，并標記為 已訪問
 cout << this->vexs[index].name << " ";
 vexs_visited[index] = 1;
 //初始化 邊結點 棧
 LinkStack<ArcNode> * s = new LinkStack<ArcNode>();
 //初始化邊結點 指針
 ArcNode * p = this->vexs[index].first;
 //2.尋找下一個（未訪問的）鄰接結點
 while (!s->Empty() || p != NULL)
 {
 //2.1.未訪問過，則訪問 （縱向遍歷）
 if (vexs_visited[p->adjVex] != 1)
 {
 //訪問結點，標記為訪問，并將其入棧
 cout << this->vexs[p->adjVex].name << " ";
 vexs_visited[p->adjVex] = 1;
 s->Push(p);
 //指針 p 移向 此結點的第一個鄰接結點
 p = this->vexs[p->adjVex].first;
 }
 //2.2.已訪問過，移向下一個邊結點 （橫向遍歷）
 else
 p = p->next;
 //3.若無鄰接點，則返回上一結點層，并出棧邊結點
 if (p == NULL)
 {
 p = s->Pop();
 }
 }
 //釋放 棧
 delete s;
}
 
void GraphAdjList::Display_DFS(string *vertex)
{
 /*
 . 從指定頂點開始，深度優(yōu)先 非遞歸 遍歷
 */
 //1.判斷頂點是否存在
 int index = _Locate(*vertex);
 if (index == -1)
 return;
 //2.初始化頂點訪問數(shù)組
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 this->vexs_visited[i] = 0;
 }
 //3.深度優(yōu)先遍歷 遞歸
 cout << "深度優(yōu)先遍歷（非遞歸）：（從頂點" << *vertex << "開始）" << endl;
 _DFS(index);
}
 
void GraphAdjList::Display_BFS(string *vertex)
{
 /*
 . 從指定頂點開始，廣度優(yōu)先遍歷
 */
 //1.判斷頂點是否存在
 int index = _Locate(*vertex);
 if (index == -1)
 return;
 //2.初始化頂點訪問數(shù)組
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 this->vexs_visited[i] = 0;
 }
 //3.廣度優(yōu)先遍歷
 cout << "廣度優(yōu)先遍歷：（從頂點" << *vertex << "開始）" << endl;
 //3.1.初始化隊列
 LinkQueue<int> * vexQ = new LinkQueue<int>();
 //3.2.訪問開始頂點，并標記訪問、入隊
 cout << this->vexs[index].name << " ";
 this->vexs_visited[index] = 1;
 vexQ->EnQueue(new int(index));
 //3.3.出隊，并遍歷鄰接頂點（下一層次），訪問后入隊
 ArcNode * p = NULL;
 int adjVex = 0;
 while (vexQ->GetHead() != NULL)
 {
 index = *vexQ->DeQueue();
 p = this->vexs[index].first;
 //遍歷鄰接頂點
 while (p != NULL)
 {
 adjVex = p->adjVex;
 //未訪問過的鄰接頂點
 if (this->vexs_visited[adjVex] != 1)
 {
 //訪問頂點，并標記訪問、入隊
 cout << this->vexs[adjVex].name << " ";
 this->vexs_visited[adjVex] = 1;
 vexQ->EnQueue(new int(adjVex));
 }
 p = p->next;
 }
 }
 
 //4.釋放隊列
 int * e;
 while (vexQ->GetHead() != NULL)
 {
 e = vexQ->DeQueue();
 delete e;
 }
 delete vexQ;
}

//文件名："GraphAdjList_Test.cpp"
#include "stdafx.h"
#include <iostream>
#include "GraphAdjList.h"
#include "ObjArrayList.h"
using namespace std;
 
int main()
{
 //初始化頂點數(shù)據(jù)
 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<string> * vexs = new ObjArrayList<string>();
 vexs->Add(v1);
 vexs->Add(v2);
 vexs->Add(v3);
 vexs->Add(v4);
 vexs->Add(v5);
 vexs->Add(v6);
 vexs->Add(v7);
 
 //初始化邊（弧）數(shù)據(jù)
 GraphAdjList::ArcData * arc1 = new GraphAdjList::ArcData{ "v1", "v2", 2 };
 GraphAdjList::ArcData * arc2 = new GraphAdjList::ArcData{ "v1", "v3", 3 };
 GraphAdjList::ArcData * arc3 = new GraphAdjList::ArcData{ "v1", "v4", 4 };
 GraphAdjList::ArcData * arc4 = new GraphAdjList::ArcData{ "v3", "v1", 5 };
 GraphAdjList::ArcData * arc5 = new GraphAdjList::ArcData{ "v3", "v2", 6 };
 GraphAdjList::ArcData * arc6 = new GraphAdjList::ArcData{ "v3", "v5", 7 };
 GraphAdjList::ArcData * arc7 = new GraphAdjList::ArcData{ "v2", "v5", 8 };
 GraphAdjList::ArcData * arc8 = new GraphAdjList::ArcData{ "v4", "v6", 9 };
 GraphAdjList::ArcData * arc9 = new GraphAdjList::ArcData{ "v4", "v7", 9 };
 GraphAdjList::ArcData * arc10 = new GraphAdjList::ArcData{ "v6", "v7", 9 };
 ObjArrayList<GraphAdjList::ArcData> * arcsList = new ObjArrayList<GraphAdjList::ArcData>();
 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;
 GraphAdjList * udg = new GraphAdjList(GraphAdjList::UDG);
 udg->Init(vexs, arcsList);
 udg->Display();
 //1.1.深度優(yōu)先遍歷
 cout << endl << "無向圖深度優(yōu)先遍歷序列：（遞歸）" << endl;
 udg->Display_DFS_R(v1);
 cout << endl << "無向圖深度優(yōu)先遍歷序列：（非遞歸）" << endl;
 udg->Display_DFS(v1);
 //1.2.廣度優(yōu)先遍歷
 cout << endl << "無向圖廣度優(yōu)先遍歷序列：" << endl;
 udg->Display_BFS(v2);
 //1.3.插入新邊
 cout << endl << "無向圖新邊：" << endl;
 udg->InsertArc(new GraphAdjList::ArcData{ "v7", "v1", 8 });
 udg->Display();
 //1.4.刪除邊
 cout << endl << "無向圖刪除邊arc9：" << endl;
 udg->DeleteArc(arc9);
 udg->Display();
 
 //測試2：有向圖
 cout << endl << "有向圖：" << endl;
 GraphAdjList * dg = new GraphAdjList(GraphAdjList::DG);
 dg->Init(vexs, arcsList);
 dg->Display();
 //2.1.深度優(yōu)先遍歷
 cout << endl << "有向圖深度優(yōu)先遍歷序列：（遞歸）" << endl;
 dg->Display_DFS_R(v1);
 cout << endl << "有向圖深度優(yōu)先遍歷序列：（非遞歸）" << endl;
 dg->Display_DFS(v1);
 //2.2.廣度優(yōu)先遍歷
 cout << endl << "有向圖廣度優(yōu)先遍歷序列：" << endl;
 dg->Display_BFS(v2);
 
 //測試：無向網(wǎng)
 cout << endl << "無向網(wǎng)：" << endl;
 GraphAdjList * udn = new GraphAdjList(GraphAdjList::UDN);
 udn->Init(vexs, arcsList);
 udn->Display();
 
 //測試：有向網(wǎng)
 cout << endl << "有向網(wǎng)：" << endl;
 GraphAdjList * dn = new GraphAdjList(GraphAdjList::DN);
 dn->Init(vexs, arcsList);
 dn->Display();
 
 return 0;
}