欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)鄰接表

 更新時間:2020年04月26日 10:35:26   作者:碣石觀海  
這篇文章主要為大家詳細(xì)介紹了C++數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)鄰接表,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

本文實(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)文章

  • linux下access函數(shù)的用法介紹

    linux下access函數(shù)的用法介紹

    access檢查用戶對一個文件的權(quán)限情況,根據(jù)mode的值檢查調(diào)用進(jìn)程對文件pathname是否具有讀、寫、或執(zhí)行的權(quán)限
    2013-08-08
  • C語言從代碼中加載動態(tài)鏈接庫過程解析

    C語言從代碼中加載動態(tài)鏈接庫過程解析

    這篇文章主要介紹了C語言從代碼中加載動態(tài)鏈接庫過程解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-12-12
  • 一文詳解C++中隱含的this指針

    一文詳解C++中隱含的this指針

    這篇文章主要帶大家詳細(xì)了解一下C++中隱含的this指針,文中通過代碼示例和圖文介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下
    2024-01-01
  • C++采用openfilename打開文件對話框用法實(shí)例

    C++采用openfilename打開文件對話框用法實(shí)例

    這篇文章主要介紹了C++采用openfilename打開文件對話框用法實(shí)例,是C++文件操作中非常實(shí)用的技巧,需要的朋友可以參考下
    2014-10-10
  • 淺析C語言中的數(shù)組及字符數(shù)組

    淺析C語言中的數(shù)組及字符數(shù)組

    這篇文章主要介紹了C語言中的數(shù)組及字符數(shù)組,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下
    2015-11-11
  • C++?Boost?Spirit進(jìn)階教程

    C++?Boost?Spirit進(jìn)階教程

    Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫,作為標(biāo)準(zhǔn)庫的后備,是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一,是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱
    2022-11-11
  • C語言中實(shí)現(xiàn)自定義數(shù)據(jù)類型的輸入輸出的方法和技巧

    C語言中實(shí)現(xiàn)自定義數(shù)據(jù)類型的輸入輸出的方法和技巧

    在 C 語言中,除了基本的數(shù)據(jù)類型(如整型、浮點(diǎn)型、字符型等),我們還經(jīng)常需要自定義數(shù)據(jù)類型來滿足特定的編程需求,所以本文給大家介紹了C語言中實(shí)現(xiàn)自定義數(shù)據(jù)類型的輸入輸出的方法和技巧,需要的朋友可以參考下
    2024-07-07
  • opencv3機(jī)器學(xué)習(xí)之EM算法示例詳解

    opencv3機(jī)器學(xué)習(xí)之EM算法示例詳解

    這篇文章主要介紹了opencv3機(jī)器學(xué)習(xí)之EM算法的示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-06-06
  • C語言實(shí)現(xiàn)無頭單向鏈表的示例代碼

    C語言實(shí)現(xiàn)無頭單向鏈表的示例代碼

    本文主要介紹了C語言實(shí)現(xiàn)無頭單向鏈表的示例代碼,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-09-09
  • C++實(shí)現(xiàn)通訊錄小功能

    C++實(shí)現(xiàn)通訊錄小功能

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)通訊錄小功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-06-06

最新評論