C++数据结构之实现邻接表

本文实例为大家分享了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;

/*

. 图(邻接表实现) Graph Adjacency List

. 相关术语:

. 顶点 Vertex ; 边 Arc ;权 Weight ;

. 有向图 Digraph ;无向图 Undigraph ;

. 有向网 Directed Network ;无向网 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, //有向网,默认 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)

{

/*

. 初始化顶点、边数据,并构建 图|网

. 入参:

. vexs: 顶点 列表

. 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)

{

/*

. 定位顶点元素位置

. 后期可改成【字典树】,顶点数超过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;

}

//若不是该边,继续下一个边校验

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;

}

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

以上是 C++数据结构之实现邻接表 的全部内容, 来源链接: utcz.com/p/245131.html

回到顶部