C++數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)鄰接表
本文實(shí)例為大家分享了C++數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)鄰接表的具體代碼,供大家參考,具體內(nèi)容如下
一、圖的鄰接表實(shí)現(xiàn)
1.實(shí)現(xiàn)了以頂點(diǎn)順序表、邊鏈表為存儲結(jié)構(gòu)的鄰接表;
2.實(shí)現(xiàn)了圖的創(chuàng)建(有向/無向/圖/網(wǎng))、邊的增刪操作、深度優(yōu)先遞歸/非遞歸遍歷、廣度優(yōu)先遍歷的算法;
3.采用頂點(diǎn)對象列表、邊(?。ο罅斜淼姆绞?,對圖的創(chuàng)建進(jìn)行初始化;引用 "ObjArrayList.h"頭文件,頭文件可參看之前博文“數(shù)據(jù)結(jié)構(gòu)之順序列表(支持對象元素)”代碼;
4.深度優(yōu)先遍歷分別采用遞歸/非遞歸算法;非遞歸中用到的棧,引用"LinkStack.h"頭文件,頭文件可參看之前博文“數(shù)據(jù)結(jié)構(gòu)之?!贝a;
5.廣度優(yōu)先遍歷采用隊(duì)列方式實(shí)現(xiàn);用到的隊(duì)列,引用 "LinkQueue.h"頭文件,頭文件可參看之前博文“數(shù)據(jù)結(jié)構(gòu)之隊(duì)列”代碼;
6.測試代碼中以有向網(wǎng)的所有帶權(quán)邊作為邊的初始化數(shù)據(jù),選擇圖類型(DG, UDG, DN, UDN)可創(chuàng)建成不同類型的圖。
7.優(yōu)劣分析:
7.1.(優(yōu)勢)鄰接表存儲結(jié)構(gòu),相比鄰接矩陣,消除了無鄰接關(guān)系頂點(diǎn)的邊存儲空間;
7.2.(優(yōu)勢)鄰接表比鄰接矩陣更容易訪問某頂點(diǎn)的鄰接頂點(diǎn);
7.3.(優(yōu)勢)鄰接表比鄰接矩陣更易于統(tǒng)計(jì)邊總數(shù),無需逐行逐列遍歷;
7.4.(劣勢)在確定兩頂點(diǎn)間是否有邊的搜索過程中,鄰接表不如鄰接矩陣可直接尋址快,反而需要頂點(diǎn)到邊鏈的遍歷;
7.5.(劣勢)鄰接矩陣在刪除頂點(diǎn)時,只需清除對應(yīng)行列數(shù)據(jù)即可;而鄰接表在清除頂點(diǎn)指向的邊鏈后,還需遍歷整個邊表,清除所有鄰接于此頂點(diǎn)的邊結(jié)點(diǎn);
7.6.(不足)鄰接表在統(tǒng)計(jì)有向圖出度時容易,只需遍歷依附此頂點(diǎn)的邊鏈;卻在統(tǒng)計(jì)其入度時,需要遍歷整個邊表,比較麻煩;可采用十字鏈表(鄰接表與逆鄰接表的結(jié)合)解決這個問題;
7.7.(不足)鄰接表在無向圖的存儲中,屬于行列對稱矩陣形式,因此會有一半重復(fù)的邊數(shù)據(jù),故可采用鄰接多重表,只存儲一半邊,來優(yōu)化存儲。
二、測試代碼中的圖結(jié)構(gòu)
深度優(yōu)先遍歷序列(從 v1 頂點(diǎn)開始):
1.無向圖/網(wǎng):v1-v2-v3-v5-v4-v6-v7
2.有向圖/網(wǎng):v1-v2-v5-v3-v4-v6-v7
廣度優(yōu)先遍歷序列(從 v2 頂點(diǎn)開始):
1.無向圖/網(wǎng):v2-v1-v3-v5-v4-v6-v7
2.有向圖/網(wǎng):v2-v5 后序無法遍歷
注:有向圖的遍歷 是遵循出度方向遍歷的,若無出度方向,則遍歷終止。
三、代碼
//文件名:"GraphAdjList.h" #pragma once #ifndef GRAPHADJLISL_H_ #define GRAPHADJLISL_H_ #include <string> #include "ObjArrayList.h" using namespace std; /* . 圖(鄰接表實(shí)現(xiàn)) Graph Adjacency List . 相關(guān)術(shù)語: . 頂點(diǎn) Vertex ; 邊 Arc ;權(quán) Weight ; . 有向圖 Digraph ;無向圖 Undigraph ; . 有向網(wǎng) Directed Network ;無向網(wǎng) Undirected Network ; . 存儲結(jié)構(gòu): . 1.頂點(diǎn)表只能采用順序結(jié)構(gòu)。(因?yàn)槿舨捎面準(zhǔn)浇Y(jié)構(gòu),頂點(diǎn)結(jié)點(diǎn)定義與邊表結(jié)點(diǎn)定義就相互引用,無法定義) . 2.邊表采用鏈表結(jié)構(gòu)。 */ class GraphAdjList { /* . 邊表(鏈表)結(jié)點(diǎn) */ struct ArcNode { int adjVex; //鄰接頂點(diǎn)所在表中下標(biāo) int weight; //邊權(quán)重 ArcNode * next; //下一條邊 }; /* . 頂點(diǎn)表(順序表)結(jié)點(diǎn) */ struct VNode { string name; //頂點(diǎn)名 ArcNode * first; //指向的第一個依附該頂點(diǎn)的頂點(diǎn)邊結(jié)點(diǎn) }; public: /* . 圖 種類 */ enum GraphType { DG, //有向圖,默認(rèn) 0 UDG, //無向圖,默認(rèn) 1 DN, //有向網(wǎng),默認(rèn) 2 UDN //無向網(wǎng),默認(rèn) 3 }; /* . 邊(?。?shù)據(jù),注:供外部初始化邊數(shù)據(jù)使用 */ struct ArcData { string Tail; //弧尾 string Head; //弧頭 int Weight; //權(quán)重 }; private: static const int _MAX_VERTEX_NUM = 10; //支持最大頂點(diǎn)數(shù) VNode vexs[_MAX_VERTEX_NUM]; //頂點(diǎn)表 int vexs_visited[_MAX_VERTEX_NUM]; //頂點(diǎn)訪問標(biāo)記數(shù)組:0|未訪問 1|已訪問 int vexNum; //頂點(diǎn)數(shù) int arcNum; //邊數(shù) int type; //圖種類 void _CreateVexSet(ObjArrayList<string> * vexs); //創(chuàng)建頂點(diǎn)集合 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); //定位頂點(diǎn)元素位置 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); //構(gòu)造函數(shù):初始化圖種類 ~GraphAdjList(); //析構(gòu)函數(shù) void Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList); //初始化頂點(diǎn)、邊數(shù)據(jù)為 圖|網(wǎng) void InsertArc(ArcData * arcData); //插入邊(含有向/無向操作) void DeleteArc(ArcData * arcData); //刪除邊(含有向/無向操作) void Display(); //顯示 圖|網(wǎng) void Display_DFS_R(string *vertex); //從指定頂點(diǎn)開始,深度優(yōu)先 遞歸 遍歷 void Display_DFS(string *vertex); //從指定頂點(diǎn)開始,深度優(yōu)先 非遞歸 遍歷 void Display_BFS(string *vertex); //從指定頂點(diǎn)開始,廣度優(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) { /* . 構(gòu)造函數(shù):初始化圖類型 */ this->type = type; this->vexNum = 0; this->arcNum = 0; } GraphAdjList::~GraphAdjList() { /* . 析構(gòu)函數(shù):銷毀圖 */ } void GraphAdjList::Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList) { /* . 初始化頂點(diǎn)、邊數(shù)據(jù),并構(gòu)建 圖|網(wǎng) . 入?yún)ⅲ? . vexs: 頂點(diǎn) 列表 . arcsList: 邊數(shù)據(jù) 列表 */ //1.創(chuàng)建頂點(diǎn)集 _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)建頂點(diǎn)集合 */ string vertex = ""; //頂點(diǎn)最大數(shù)校驗(yàn) if (vexs->Length() > this->_MAX_VERTEX_NUM) { return; } //遍歷頂點(diǎn)表,無重復(fù)插入頂點(diǎn),并計(jì)數(shù)頂點(diǎn)數(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 頂點(diǎn)下標(biāo)索引 int tail = 0, head = 0; //遍歷邊數(shù)據(jù)列表 for (int i = 0; i < arcsList->Length(); i++) { //按序獲取邊(弧) arcData = arcsList->Get(i); //定位(或設(shè)置)邊的兩端頂點(diǎn)位置 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 頂點(diǎn)下標(biāo)索引 int tail = 0, head = 0; //遍歷邊數(shù)據(jù)列表 for (int i = 0; i < arcsList->Length(); i++) { //按序獲取邊(?。? arcData = arcsList->Get(i); //定位(或設(shè)置)邊的兩端頂點(diǎn)位置 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 頂點(diǎn)下標(biāo)索引 int tail = 0, head = 0; //遍歷邊數(shù)據(jù)列表 for (int i = 0; i < arcsList->Length(); i++) { //按序獲取邊(?。? arcData = arcsList->Get(i); //定位(或設(shè)置)邊的兩端頂點(diǎn)位置 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 頂點(diǎn)下標(biāo)索引 int tail = 0, head = 0; //遍歷邊數(shù)據(jù)列表 for (int i = 0; i < arcsList->Length(); i++) { //按序獲取邊(?。? arcData = arcsList->Get(i); //定位(或設(shè)置)邊的兩端頂點(diǎn)位置 tail = _Locate(arcData->Tail); head = _Locate(arcData->Head); //插入對稱邊 _InsertArc(tail, head, arcData->Weight); _InsertArc(head, tail, arcData->Weight); } } int GraphAdjList::_Locate(string vertex) { /* . 定位頂點(diǎn)元素位置 . 后期可改成【字典樹】,頂點(diǎn)數(shù)超過100個后定位頂點(diǎn)位置可更快 */ //遍歷定位頂點(diǎn)位置 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { if (vertex == this->vexs[i].name) { return i; } } //cout << endl << "頂點(diǎn)[" << vertex << "]不存在。" << endl; return -1; } void GraphAdjList::_InsertArc(int tail, int head, int weight) { /* . 插入邊(元操作,不分有向/無向) */ //邊結(jié)點(diǎn)指針:初始化為 弧尾 指向的第一個邊 ArcNode * p = this->vexs[tail].first; //初始化 前一邊結(jié)點(diǎn)的指針 ArcNode * q = NULL; //重復(fù)邊布爾值 bool exist = false; //1.邊的重復(fù)性校驗(yàn) while (p != NULL) { //若已存在該邊,則標(biāo)記為 存在 true if (p->adjVex == head) { exist = true; break; } //若不是該邊,繼續(xù)下一個邊校驗(yàn) 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.邊 計(jì)數(shù) this->arcNum++; } void GraphAdjList::InsertArc(ArcData * arcData) { /* . 插入邊(含有向/無向操作) */ //初始化 Tail Head 頂點(diǎn)下標(biāo)索引 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) { /* . 刪除邊(元操作,不分有向/無向) */ //邊結(jié)點(diǎn)指針:初始化為 弧尾 指向的第一個邊 ArcNode * p = this->vexs[tail].first; //初始化 前一邊結(jié)點(diǎn)的指針 ArcNode * q = NULL; //1.遍歷查找邊 while (p != NULL) { //若存在該邊,則結(jié)束循環(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 頂點(diǎn)下標(biāo)索引 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) */ //初始化邊表結(jié)點(diǎn)指針 ArcNode * p = NULL; cout << endl << "鄰接表:" << endl; //遍歷頂點(diǎn)表 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { //空頂點(diǎn)(在刪除頂點(diǎn)的操作后會出現(xiàn)此類情況) if (this->vexs[i].name == "") { continue; } //輸出頂點(diǎn) cout << "[" << i << "]" << this->vexs[i].name << " "; //遍歷輸出邊頂點(diǎn) 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.訪問頂點(diǎn),并標(biāo)記已訪問 cout << this->vexs[index].name << " "; this->vexs_visited[index] = 1; //2.遍歷訪問其相鄰頂點(diǎn) ArcNode * p = this->vexs[index].first; int adjVex = 0; while (p != NULL) { adjVex = p->adjVex; //當(dāng)頂點(diǎn)未被訪問過時,可訪問 if (this->vexs_visited[adjVex] != 1) { _DFS_R(adjVex); } p = p->next; } } void GraphAdjList::Display_DFS_R(string *vertex) { /* . 從指定頂點(diǎn)開始,深度優(yōu)先 遞歸 遍歷 */ //1.判斷頂點(diǎn)是否存在 int index = _Locate(*vertex); if (index == -1) return; //2.初始化頂點(diǎn)訪問數(shù)組 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { this->vexs_visited[i] = 0; } //3.深度優(yōu)先遍歷 遞歸 cout << "深度優(yōu)先遍歷(遞歸):(從頂點(diǎn)" << *vertex << "開始)" << endl; _DFS_R(index); } void GraphAdjList::_DFS(int index) { /* . 深度優(yōu)先遍歷 非遞歸 */ //1.訪問第一個結(jié)點(diǎn),并標(biāo)記為 已訪問 cout << this->vexs[index].name << " "; vexs_visited[index] = 1; //初始化 邊結(jié)點(diǎn) 棧 LinkStack<ArcNode> * s = new LinkStack<ArcNode>(); //初始化邊結(jié)點(diǎn) 指針 ArcNode * p = this->vexs[index].first; //2.尋找下一個(未訪問的)鄰接結(jié)點(diǎn) while (!s->Empty() || p != NULL) { //2.1.未訪問過,則訪問 (縱向遍歷) if (vexs_visited[p->adjVex] != 1) { //訪問結(jié)點(diǎn),標(biāo)記為訪問,并將其入棧 cout << this->vexs[p->adjVex].name << " "; vexs_visited[p->adjVex] = 1; s->Push(p); //指針 p 移向 此結(jié)點(diǎn)的第一個鄰接結(jié)點(diǎn) p = this->vexs[p->adjVex].first; } //2.2.已訪問過,移向下一個邊結(jié)點(diǎn) (橫向遍歷) else p = p->next; //3.若無鄰接點(diǎn),則返回上一結(jié)點(diǎn)層,并出棧邊結(jié)點(diǎn) if (p == NULL) { p = s->Pop(); } } //釋放 棧 delete s; } void GraphAdjList::Display_DFS(string *vertex) { /* . 從指定頂點(diǎn)開始,深度優(yōu)先 非遞歸 遍歷 */ //1.判斷頂點(diǎn)是否存在 int index = _Locate(*vertex); if (index == -1) return; //2.初始化頂點(diǎn)訪問數(shù)組 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { this->vexs_visited[i] = 0; } //3.深度優(yōu)先遍歷 遞歸 cout << "深度優(yōu)先遍歷(非遞歸):(從頂點(diǎn)" << *vertex << "開始)" << endl; _DFS(index); } void GraphAdjList::Display_BFS(string *vertex) { /* . 從指定頂點(diǎn)開始,廣度優(yōu)先遍歷 */ //1.判斷頂點(diǎn)是否存在 int index = _Locate(*vertex); if (index == -1) return; //2.初始化頂點(diǎn)訪問數(shù)組 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { this->vexs_visited[i] = 0; } //3.廣度優(yōu)先遍歷 cout << "廣度優(yōu)先遍歷:(從頂點(diǎn)" << *vertex << "開始)" << endl; //3.1.初始化隊(duì)列 LinkQueue<int> * vexQ = new LinkQueue<int>(); //3.2.訪問開始頂點(diǎn),并標(biāo)記訪問、入隊(duì) cout << this->vexs[index].name << " "; this->vexs_visited[index] = 1; vexQ->EnQueue(new int(index)); //3.3.出隊(duì),并遍歷鄰接頂點(diǎn)(下一層次),訪問后入隊(duì) ArcNode * p = NULL; int adjVex = 0; while (vexQ->GetHead() != NULL) { index = *vexQ->DeQueue(); p = this->vexs[index].first; //遍歷鄰接頂點(diǎn) while (p != NULL) { adjVex = p->adjVex; //未訪問過的鄰接頂點(diǎn) if (this->vexs_visited[adjVex] != 1) { //訪問頂點(diǎn),并標(biāo)記訪問、入隊(duì) cout << this->vexs[adjVex].name << " "; this->vexs_visited[adjVex] = 1; vexQ->EnQueue(new int(adjVex)); } p = p->next; } } //4.釋放隊(duì)列 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() { //初始化頂點(diǎn)數(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; }
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C++采用openfilename打開文件對話框用法實(shí)例
這篇文章主要介紹了C++采用openfilename打開文件對話框用法實(shí)例,是C++文件操作中非常實(shí)用的技巧,需要的朋友可以參考下2014-10-10C語言中實(shí)現(xiàn)自定義數(shù)據(jù)類型的輸入輸出的方法和技巧
在 C 語言中,除了基本的數(shù)據(jù)類型(如整型、浮點(diǎn)型、字符型等),我們還經(jīng)常需要自定義數(shù)據(jù)類型來滿足特定的編程需求,所以本文給大家介紹了C語言中實(shí)現(xiàn)自定義數(shù)據(jù)類型的輸入輸出的方法和技巧,需要的朋友可以參考下2024-07-07opencv3機(jī)器學(xué)習(xí)之EM算法示例詳解
這篇文章主要介紹了opencv3機(jī)器學(xué)習(xí)之EM算法的示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-06-06