本文实例为大家分享了C++数据结构之实现邻接表的具体代码，供大家参考，具体内容如下

一、图的邻接表实现

1.实现了以顶点顺序表、边链表为存储结构的邻接表；

2.实现了图的创建（有向/无向/图/网）、边的增删操作、深度优先递归/非递归遍历、广度优先遍历的算法；

3.采用顶点对象列表、边（弧）对象列表的方式，对图的创建进行初始化；引用 "ObjArrayList.h"头文件，头文件可参看之前博文“数据结构之顺序列表（支持对象元素）”代码；

4.深度优先遍历分别采用递归/非递归算法；非递归中用到的栈，引用"LinkStack.h"头文件，头文件可参看之前博文“数据结构之栈”代码；

5.广度优先遍历采用队列方式实现；用到的队列，引用 "LinkQueue.h"头文件，头文件可参看之前博文“数据结构之队列”代码；

6.测试代码中以有向网的所有带权边作为边的初始化数据，选择图类型（DG, UDG, DN, UDN）可创建成不同类型的图。

7.优劣分析：

7.1.（优势）邻接表存储结构，相比邻接矩阵，消除了无邻接关系顶点的边存储空间；

7.2.（优势）邻接表比邻接矩阵更容易访问某顶点的邻接顶点；

7.3.（优势）邻接表比邻接矩阵更易于统计边总数，无需逐行逐列遍历；

7.4.（劣势）在确定两顶点间是否有边的搜索过程中，邻接表不如邻接矩阵可直接寻址快，反而需要顶点到边链的遍历；

7.5.（劣势）邻接矩阵在删除顶点时，只需清除对应行列数据即可；而邻接表在清除顶点指向的边链后，还需遍历整个边表，清除所有邻接于此顶点的边结点；

7.6.（不足）邻接表在统计有向图出度时容易，只需遍历依附此顶点的边链；却在统计其入度时，需要遍历整个边表，比较麻烦；可采用十字链表（邻接表与逆邻接表的结合）解决这个问题；

7.7.（不足）邻接表在无向图的存储中，属于行列对称矩阵形式，因此会有一半重复的边数据，故可采用邻接多重表，只存储一半边，来优化存储。

二、测试代码中的图结构

深度优先遍历序列（从 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 后序无法遍历

注：有向图的遍历 是遵循出度方向遍历的，若无出度方向，则遍历终止。

三、代码

//文件名："GraphAdjList.h"#pragma once#ifndef GRAPHADJLISL_H_#define GRAPHADJLISL_H_ #include <string>#include "ObjArrayList.h"using namespace std; class GraphAdjList{ struct ArcNode { int adjVex; //邻接顶点所在表中下标 int weight; //边权重 ArcNode * next; //下一条边 }; struct VNode { string name; //顶点名 ArcNode * first; //指向的第一个依附该顶点的顶点边结点 };public: enum GraphType { DG, //有向图，默认 0 UDG, //无向图，默认 1 DN, //有向网，默认 2 UDN //无向网，默认 3 }; struct ArcData { string Tail; //弧尾 string Head; //弧头 int Weight; //权重 }; private: static const int _MAX_VERTEX_NUM = 10; //支持最大顶点数 VNode vexs[_MAX_VERTEX_NUM]; //顶点表 int vexs_visited[_MAX_VERTEX_NUM]; //顶点访问标记数组：0|未访问 1|已访问 int vexNum; //顶点数 int arcNum; //边数 int type; //图种类 void _CreateVexSet(ObjArrayList<string> * vexs); //创建顶点集合 void _CreateDG(ObjArrayList<ArcData> * arcsList); //创建有向图 void _CreateUDG(ObjArrayList<ArcData> * arcsList); //创建无向图 void _CreateDN(ObjArrayList<ArcData> * arcsList); //创建有向网 void _CreateUDN(ObjArrayList<ArcData> * arcsList); //创建无向网 int _Locate(string vertex); //定位顶点元素位置 void _InsertArc(int tail, int head, int weight); //插入边（元操作，不分有向/无向） void _DeleteArc(int tail, int head); //删除边（元操作，不分有向/无向） void _DFS_R(int index); //深度优先遍历 递归 void _DFS(int index); //深度优先遍历 非递归 public: GraphAdjList(int type); //构造函数：初始化图种类 ~GraphAdjList(); //析构函数 void Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList); //初始化顶点、边数据为 图|网 void InsertArc(ArcData * arcData); //插入边（含有向/无向操作） void DeleteArc(ArcData * arcData); //删除边（含有向/无向操作） void Display(); //显示 图|网 void Display_DFS_R(string *vertex); //从指定顶点开始，深度优先 递归 遍历 void Display_DFS(string *vertex); //从指定顶点开始，深度优先 非递归 遍历 void Display_BFS(string *vertex); //从指定顶点开始，广度优先遍历 };//文件名："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){ this->type = type; this->vexNum = 0; this->arcNum = 0;} GraphAdjList::~GraphAdjList(){ } void GraphAdjList::Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList){ //1.创建顶点集 _CreateVexSet(vexs); //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 GraphAdjList::_CreateVexSet(ObjArrayList<string> * vexs){ string vertex = ""; //顶点最大数校验 if (vexs->Length() > this->_MAX_VERTEX_NUM) { return; } //遍历顶点表，无重复插入顶点，并计数顶点数 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){ //初始化临时 边对象 ArcData * arcData = NULL; //初始化 Tail Head 顶点下标索引 int tail = 0, head = 0; //遍历边数据列表 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){ //初始化临时 边对象 ArcData * arcData = NULL; //初始化 Tail Head 顶点下标索引 int tail = 0, head = 0; //遍历边数据列表 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){ //初始化临时 边对象 ArcData * arcData = NULL; //初始化 Tail Head 顶点下标索引 int tail = 0, head = 0; //遍历边数据列表 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){ //初始化临时 边对象 ArcData * arcData = NULL; //初始化 Tail Head 顶点下标索引 int tail = 0, head = 0; //遍历边数据列表 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){ //遍历定位顶点位置 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; } //若不是该边，继续下一个边校验 q = p; p = p->next; } //2.1.如果边存在，则跳过，不做插入 if (exist) return; //2.2.边不存在时，创建边 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.边 计数 this->arcNum++;} void GraphAdjList::InsertArc(ArcData * arcData){ //初始化 Tail Head 顶点下标索引 int tail = 0, head = 0; tail = _Locate(arcData->Tail); head = _Locate(arcData->Head); //根据图类型，插入边 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) { //若存在该边，则结束循环 if (p->adjVex == head) { break; } //若不是该边，继续下一个边 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); //根据图类型，删除边 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(){ //初始化边表结点指针 ArcNode * p = NULL; cout << endl << "邻接表：" << endl; //遍历顶点表 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { //空顶点（在删除顶点的操作后会出现此类情况） 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){ //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){ //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 GraphAdjList::_DFS(int index){ //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){ //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(index);} void GraphAdjList::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<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(){ //初始化顶点数据 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); //初始化边（弧）数据 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.深度优先遍历 cout << endl << "无向图深度优先遍历序列：（递归）" << endl; udg->Display_DFS_R(v1); cout << endl << "无向图深度优先遍历序列：（非递归）" << endl; udg->Display_DFS(v1); //1.2.广度优先遍历 cout << endl << "无向图广度优先遍历序列：" << 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.深度优先遍历 cout << endl << "有向图深度优先遍历序列：（递归）" << endl; dg->Display_DFS_R(v1); cout << endl << "有向图深度优先遍历序列：（非递归）" << endl; dg->Display_DFS(v1); //2.2.广度优先遍历 cout << endl << "有向图广度优先遍历序列：" << endl; dg->Display_BFS(v2); //测试：无向网 cout << endl << "无向网：" << endl; GraphAdjList * udn = new GraphAdjList(GraphAdjList::UDN); udn->Init(vexs, arcsList); udn->Display(); //测试：有向网 cout << endl << "有向网：" << endl; GraphAdjList * dn = new GraphAdjList(GraphAdjList::DN); dn->Init(vexs, arcsList); dn->Display(); return 0;}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。