|
//文件名："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;
}
|
0
0
已为社区贡献56条内容
所有评论(0)