数据结构-图(邻接矩阵实现)

一、图的邻接矩阵实现


1.实现了以顶点数组、邻接矩阵为存储结构的图;

2.实现了图的创建(包含有向/无向图、有向/无向网)、顶点/边的增删操作、深度/广度优先遍历的算法;

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

4.采用将顶点数组空位的下标索引入队列的方式,解决顶点在数组(静态)中因增删操作造成的不连续存储的问题;引用 “LinkQueue.h”头文件,头文件可参看之前博文“数据结构之队列(循环队列、链队列的类模板实现)”代码;

5.深度优先遍历采用递归算法;广度优先遍历采用队列方式实现;

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

二、测试代码中的图结构图

数据结构-图(邻接矩阵实现)

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

注:有向图的遍历 是遵循出度方向遍历的,若无出度方向,则遍历终止。
数据结构-图(邻接矩阵实现)

三、代码

//文件名:"GraphAdjMat.h"
#pragma once
#ifndef GRAPHADJMAT_H_
#define GRAPHADJMAT_H_
 
#include <limits>
#include <string>
#include "ObjArrayList.h"
#include "LinkQueue.h"
using namespace std;
 
/*
.	图(邻接矩阵实现) Graph Adjacency Matrix
.	相关术语:
.		顶点 Vertex ; 边 Arc ;权 Weight ;
.		有向图 Digraph ;无向图 Undigraph ;
.		有向网 Directed Network ;无向网 Undirected Network ;
*/
 
class GraphAdjMat
{
	/*
	.	边(弧) 单元,注:邻接矩阵单元
	*/
	struct ArcCell
	{
		int adj;		//邻接顶点关系。图:0|不相邻 1|相邻 ;网:无穷(INT_MAX)|不相邻  权值(W)|相邻
		char * info;	//边(弧)信息
	};
	
public:
	/*
	.	图 种类
	*/
	enum GraphType
	{
		DG,			//有向图,默认 0
		UDG,		//无向图,默认 1
		DN,			//有向网,默认 2
		UDN			//无向网,默认 3
	};
	/*
	.	边(弧)数据,注:供外部初始化边数据使用
	*/
	struct ArcData
	{
		string Tail;	//弧尾
		string Head;	//弧头
		int Weight;		//权重
	};
 
private:
	const int _INFINITY = INT_MAX;				//无穷大  注:包含于头文件 <limits>
	static const int _MAX_VERTEX_NUM = 10;		//支持最大顶点数
 
	//静态存储结构
	string vexs[_MAX_VERTEX_NUM];						//顶点表
	ArcCell arcs[_MAX_VERTEX_NUM][_MAX_VERTEX_NUM];		//边(弧)矩阵
	int vexNum;			//顶点数
	int arcNum;			//边数
	int type;			//图种类
	int nonAdjInt;		//不相邻 int 值:0|无权 无穷|有权
 
	LinkQueue<int> *vexs_null_index_queue = new LinkQueue<int>();		//顶点数组中空顶点位置索引队列 (需要销毁)
	bool vexs_visited[_MAX_VERTEX_NUM];			//顶点访问标记数组:0|未访问 1|已访问
 
	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 _DFS_R(int index);						//深度优先遍历 递归
 
public:
	GraphAdjMat(int type);						//构造函数:初始化图类型
	~GraphAdjMat();								//析构函数:销毁图存储空间
	void Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList);		//初始化顶点、边数据为 图|网
	void Display();								//显示 图|网
	void InsertVertex(string *vertex);			//插入一个新顶点
	void DeleteVertex(string *vertex);			//删除一个顶点
	void InsertArc(ArcData *arc);				//插入一条新边(弧)
	void DeleteArc(ArcData *arc);				//删除一条边(弧)
	void Display_DFS(string *vertex);			//从指定顶点开始,深度优先遍历
	void Display_BFS(string *vertex);			//从指定顶点开始,广度优先遍历
 
	GraphAdjMat * MiniSpanTree_Prim(string * vertex);		//最小生成树(Prim 算法)
	GraphAdjMat * MiniSpanTree_Kruskal(string * vertex);	//最小生成树(Kruskal 算法)
 
};
 
#endif // !GRAPHADJMAT_H_
//文件名:"GraphAdjMat.cpp"
#include "stdafx.h"
#include <string>
#include "ObjArrayList.h"
#include "LinkQueue.h"
#include "GraphAdjMat.h"
using namespace std;
 
GraphAdjMat::GraphAdjMat(int type)
{
	/*
	.	构造函数:初始化图类型
	*/
	this->type = type;
	this->vexNum = 0;
	this->arcNum = 0;
	if (this->type == DG || this->type == UDG)
	{
		//图的不相邻 int 值 0
		this->nonAdjInt = 0;
	}
	else
	{
		//网的不相邻 int 值 无穷大
		this->nonAdjInt = this->_INFINITY;
	}
}
 
GraphAdjMat::~GraphAdjMat()
{
	/*
	.	析构函数:销毁图
	*/
	//1.释放顶点空位置索引队列
	int * e;
	while (vexs_null_index_queue->GetHead() != NULL)
	{
		e = vexs_null_index_queue->DeQueue();
		delete e;
	}
	delete vexs_null_index_queue;
 
}
 
void GraphAdjMat::Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList)
{
	/*
	.	初始化顶点、边数据,并构建 图|网
	.	入参:
	.		vexs: 顶点 列表
	.		arcsList: 边数据 列表
	*/
	//1.初始化顶点数据
	if (vexs->Length() > this->_MAX_VERTEX_NUM)
	{
		return;
	}
	for (int i = 0; i < vexs->Length(); i++)
	{
		this->vexs[i] = *vexs->Get(i);
	}
	this->vexNum = vexs->Length();
	//1.1.初始化顶点数组空顶点位置索引队列
	for (int i = vexs->Length(); i < _MAX_VERTEX_NUM; i++)
	{
		vexs_null_index_queue->EnQueue(new int(i));
	}
	//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 GraphAdjMat::_CreateDG(ObjArrayList<ArcData> * arcsList)
{
	/*
	.	创建有向图
	.	顶点相邻关系:0|不相邻 1|相邻
	.	邻接矩阵为 非对称矩阵
	*/
	//初始化临时 边对象
	ArcData * arcData = NULL;
	//初始化 矩阵二维坐标
	int m = 0, n = 0;
	//初始化边的邻接矩阵
	for (int i = 0; i < _MAX_VERTEX_NUM; i++)
	{
		for (int j = 0; j < _MAX_VERTEX_NUM; j++)
		{
			this->arcs[i][j].adj = 0;
			this->arcs[i][j].info = NULL;
		}
	}
	//遍历边数据列表
	for (int i = 0; i < arcsList->Length(); i++)
	{
		//按序获取边(弧)
		arcData = arcsList->Get(i);
		//定位(或设置)边的两端顶点位置
		m = _Locate(arcData->Tail);
		n = _Locate(arcData->Head);
		//设置顶点相邻 为 1 (无向)
		if (this->arcs[m][n].adj == 1)
		{
			//去除重复边
			continue;
		}
		this->arcs[m][n].adj = 1;
		//边 计数
		this->arcNum++;
	}
}
 
void GraphAdjMat::_CreateUDG(ObjArrayList<ArcData> * arcsList)
{
	/*
	.	创建无向图
	.	顶点相邻关系:0|不相邻 1|相邻
	.	邻接矩阵为 对称矩阵
	*/
	//初始化临时 边对象
	ArcData * arcData = NULL;
	//初始化 矩阵二维坐标
	int m = 0, n = 0;
	//初始化边的邻接矩阵
	for (int i = 0; i < _MAX_VERTEX_NUM; i++)
	{
		for (int j = 0; j < _MAX_VERTEX_NUM; j++)
		{
			this->arcs[i][j].adj = 0;
			this->arcs[i][j].info = NULL;
		}
	}
	//遍历边数据列表
	for (int i = 0; i < arcsList->Length(); i++)
	{
		//按序获取边(弧)
		arcData = arcsList->Get(i);
		//定位(或设置)边的两端顶点位置
		m = _Locate(arcData->Tail);
		n = _Locate(arcData->Head);
		//设置顶点相邻 为 1 (有向)
		if (this->arcs[m][n].adj == 1 || this->arcs[n][m].adj == 1)
		{
			//去除重复边
			continue;
		}
		this->arcs[m][n].adj = 1;
		this->arcs[n][m].adj = 1;
		//边 计数
		this->arcNum++;
	}
}
 
void GraphAdjMat::_CreateDN(ObjArrayList<ArcData> * arcsList)
{
	/*
	.	创建有向网
	.	顶点相邻关系:infinity|不相邻 w|相邻
	.	邻接矩阵为 非对称矩阵
	*/
	//初始化临时 边对象
	ArcData * arcData = NULL;
	//初始化 矩阵二维坐标
	int m = 0, n = 0;
	//初始化边的邻接矩阵
	for (int i = 0; i < _MAX_VERTEX_NUM; i++)
	{
		for (int j = 0; j < _MAX_VERTEX_NUM; j++)
		{
			this->arcs[i][j].adj = this->_INFINITY;	//无穷大
			this->arcs[i][j].info = NULL;
		}
	}
	//遍历边数据列表
	for (int i = 0; i < arcsList->Length(); i++)
	{
		//按序获取边(弧)
		arcData = arcsList->Get(i);
		//定位(或设置)边的两端顶点位置
		m = _Locate(arcData->Tail);
		n = _Locate(arcData->Head);
		//设置顶点相邻 为 weight 权重
		if (this->arcs[m][n].adj != this->_INFINITY)
		{
			//去除重复边
			continue;
		}
		this->arcs[m][n].adj = arcData->Weight;
		//边 计数
		this->arcNum++;
	}
}
 
void GraphAdjMat::_CreateUDN(ObjArrayList<ArcData> * arcsList)
{
	/*
	.	创建无向网
	.	顶点相邻关系:infinity|不相邻 w|相邻
	.	邻接矩阵为 对称矩阵
	*/
	//初始化临时 边对象
	ArcData * arcData = NULL;
	//初始化 矩阵二维坐标
	int m = 0, n = 0;
	//初始化边的邻接矩阵
	for (int i = 0; i < _MAX_VERTEX_NUM; i++)
	{
		for (int j = 0; j < _MAX_VERTEX_NUM; j++)
		{
			this->arcs[i][j].adj = this->_INFINITY;	//无穷大
			this->arcs[i][j].info = NULL;
		}
	}
	//遍历边数据列表
	for (int i = 0; i < arcsList->Length(); i++)
	{
		//按序获取边(弧)
		arcData = arcsList->Get(i);
		//定位(或设置)边的两端顶点位置
		m = _Locate(arcData->Tail);
		n = _Locate(arcData->Head);
		//设置顶点相邻 为 weight 权重
		if (this->arcs[m][n].adj != this->_INFINITY || this->arcs[n][m].adj != this->_INFINITY)
		{
			//去除重复边
			continue;
		}
		if (arcData->Weight == this->_INFINITY)
		{
			//去除权重为 无穷 的边
			continue;
		}
		this->arcs[m][n].adj = arcData->Weight;
		this->arcs[n][m].adj = arcData->Weight;
		//边 计数
		this->arcNum++;
	}
}
 
int GraphAdjMat::_Locate(string vertex)
{
	/*
	.	定位顶点元素位置
	.		后期可改成【字典树】,顶点数超过100个后定位顶点位置可更快
	*/
	//遍历定位顶点位置
	for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
	{
		if (vertex == this->vexs[i])
		{
			return i;
		}
	}
	cout << endl << "顶点[" << vertex << "]不存在。" << endl;
	return -1;
}
 
void GraphAdjMat::Display()
{
	/*
	.	显示 图|网 (输出顶点数组、邻接矩阵)
	*/
	//显示顶点数组
	//注:当删除某个中间序号顶点后,顶点数组就不是连续的
	cout << endl << "顶点数组:" << endl;
	for (int i = 0, num = 0; i < this->_MAX_VERTEX_NUM && num < this->vexNum; i++)
	{
		if (this->vexs[i] != "")
		{
			cout << " (" << i << ")" << this->vexs[i];
			num++;
		}
	}
	//显示边(邻接矩阵)
	cout << endl << "边(邻接矩阵):" << endl;
	cout << "    ";
	for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
	{
		cout << "[" << i << "]";
	}
	cout << endl;
	for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
	{
		cout << "[" << i << "] ";
		for (int j = 0; j < this->_MAX_VERTEX_NUM; j++)
		{
			if (this->arcs[i][j].adj == this->_INFINITY)
				cout << " + ";
			else
				cout << " " << this->arcs[i][j].adj << " ";
		}
		cout << endl;
	}
}
 
void GraphAdjMat::InsertVertex(string *vertex)
{
	/*
	.	插入一个新顶点
	*/
	//1.判断顶点是否已存在
	if (_Locate(*vertex) > -1)
	{
		cout << endl << "该顶点已存在。" << endl;
		return;
	}
	//2.判断顶点数是否达到上限
	if (this->vexNum >= this->_MAX_VERTEX_NUM)
	{
		cout << endl << "顶点数已达上限。" << endl;
		return;
	}
	//3.插入新顶点,并自增顶点总数
	int * index = vexs_null_index_queue->DeQueue();	//从空位置索引队列中取
	this->vexs[*index] = *vertex;
	this->vexNum++;
	//4.新增的顶点在邻接矩阵中不需要作任何操作(已初始化)
 
}
 
void GraphAdjMat::DeleteVertex(string *vertex)
{
	/*
	.	删除一个顶点
	*/
	//1.判断顶点是否已存在
	int index = _Locate(*vertex);
	if (index == -1)
	{
		cout << endl << "该顶点不存在。" << endl;
		return;
	}
	//2.删除该顶点,并自减顶点总数
	this->vexs[index] = "";
	this->vexNum--;
	//3.清除邻接矩阵 index 行列的数据,即将此行列 恢复初始化状态
	if (this->type == DG || this->type == UDG)
	{
		//图
		for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
		{
			this->arcs[i][index].adj = 0;
			this->arcs[index][i].adj = 0;
		}
	}
	else
	{
		//网
		for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
		{
			this->arcs[i][index].adj = this->_INFINITY;
			this->arcs[index][i].adj = this->_INFINITY;
		}
	}
}
 
 
void GraphAdjMat::InsertArc(ArcData *arc)
{
	/*
	.	插入一条新边(弧)
	.		若已存在,将对其更新
	*/
	//1.定位顶点位置
	int i = _Locate(arc->Tail);
	int j = _Locate(arc->Head);
	//2.判断顶点是否存在
	if (i == -1 || j == -1)
	{
		cout << endl << "该边顶点不存在。" << endl;
		return;
	}
	//3.插入/更新一条边
	if (this->type == DG)
	{
		//有向无权图
		this->arcs[i][j].adj = 1;
	}
	else if (this->type == UDG)
	{
		//无向无权图
		this->arcs[i][j].adj = 1;
		this->arcs[j][i].adj = 1;
	}
	else if (this->type == DN)
	{
		//有向有权网
		this->arcs[i][j].adj = arc->Weight;
	}
	else
	{
		//无向有权网
		this->arcs[i][j].adj = arc->Weight;
		this->arcs[j][i].adj = arc->Weight;
	}
}
 
void GraphAdjMat::DeleteArc(ArcData *arc)
{
	/*
	.	删除一条边(弧)
	*/
	//1.定位顶点位置
	int i = _Locate(arc->Tail);
	int j = _Locate(arc->Head);
	//2.判断顶点是否存在
	if (i == -1 || j == -1)
	{
		cout << endl << "该边顶点不存在。" << endl;
		return;
	}
	//3.删除一条边,即 恢复初始化状态
	if (this->type == DG)
	{
		//有向无权图
		this->arcs[i][j].adj = 0;
	}
	else if (this->type == UDG)
	{
		//无向无权图
		this->arcs[i][j].adj = 0;
		this->arcs[j][i].adj = 0;
	}
	else if (this->type == DN)
	{
		//有向有权网
		this->arcs[i][j].adj = this->_INFINITY;
	}
	else
	{
		//无向有权网
		this->arcs[i][j].adj = this->_INFINITY;
		this->arcs[j][i].adj = this->_INFINITY;
	}
}
 
void GraphAdjMat::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_R(index);
}
 
void GraphAdjMat::_DFS_R(int index)
{
	/*
	.	深度优先遍历 递归
	.		有向/无向算法是一样的
	.		有向图|网,以当前顶点的出度方向遍历
	.		无向图|网,以当前顶点的相邻结点方向遍历(可理解为“出度”,但不是出度)
	*/
	//1.访问顶点,并标记已访问
	cout << this->vexs[index] << " ";
	this->vexs_visited[index] = 1;
	//2.访问其相邻顶点
	for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
	{
		//当边值 不是 不相邻int值(0|无权  无穷|有权),且未被访问过时,可访问
		if (this->arcs[index][i].adj != this->nonAdjInt && this->vexs_visited[i] != 1)
		{
			_DFS_R(i);
		}
	}
}
 
void GraphAdjMat::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] << " ";
	this->vexs_visited[index] = 1;
	vexQ->EnQueue(new int(index));
	//3.3.出队,并遍历邻接顶点(下一层次),访问后入队
	while (vexQ->GetHead() != NULL)
	{
		index = *vexQ->DeQueue();
		for (int j = 0; j < _MAX_VERTEX_NUM; j++)
		{
			//未访问过的邻接顶点
			if (this->arcs[index][j].adj != this->nonAdjInt && this->vexs_visited[j] != 1)
			{
				//访问顶点,并标记访问、入队
				cout << this->vexs[j] << " ";
				this->vexs_visited[j] = 1;
				vexQ->EnQueue(new int(j));
			}
		}
	}
 
	//4.释放队列
	int * e;
	while (vexQ->GetHead() != NULL)
	{
		e = vexQ->DeQueue();
		delete e;
	}
	delete vexQ;
}

 

//文件名:"GraphAdjMat_Test.cpp"
#include "stdafx.h"
#include <iostream>
#include "GraphAdjMat.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);
 
	//初始化边(弧)数据
	GraphAdjMat::ArcData * arc1 = new GraphAdjMat::ArcData{ "v1", "v2", 2 };
	GraphAdjMat::ArcData * arc2 = new GraphAdjMat::ArcData{ "v1", "v3", 3 };
	GraphAdjMat::ArcData * arc3 = new GraphAdjMat::ArcData{ "v1", "v4", 4 };
	GraphAdjMat::ArcData * arc4 = new GraphAdjMat::ArcData{ "v3", "v1", 5 };
	GraphAdjMat::ArcData * arc5 = new GraphAdjMat::ArcData{ "v3", "v2", 6 };
	GraphAdjMat::ArcData * arc6 = new GraphAdjMat::ArcData{ "v3", "v5", 7 };
	GraphAdjMat::ArcData * arc7 = new GraphAdjMat::ArcData{ "v2", "v5", 8 };
	GraphAdjMat::ArcData * arc8 = new GraphAdjMat::ArcData{ "v4", "v6", 9 };
	GraphAdjMat::ArcData * arc9 = new GraphAdjMat::ArcData{ "v4", "v7", 9 };
	GraphAdjMat::ArcData * arc10 = new GraphAdjMat::ArcData{ "v6", "v7", 9 };
	ObjArrayList<GraphAdjMat::ArcData> * arcsList = new ObjArrayList<GraphAdjMat::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;
	GraphAdjMat * udg = new GraphAdjMat(GraphAdjMat::UDG);
	udg->Init(vexs, arcsList);
	udg->Display();
	//1.1.深度优先遍历
	cout << endl << "无向图深度优先遍历序列:" << endl;
	udg->Display_DFS(v1);
	//1.2.广度优先遍历
	cout << endl << "无向图广度优先遍历序列:" << endl;
	udg->Display_BFS(v2);
	//1.3.插入新顶点、新边
	cout << endl << "无向图插入新顶点、新边:" << endl;
	udg->InsertVertex(new string("v8"));
	udg->InsertArc(new GraphAdjMat::ArcData{ "v8", "v1", 8 });
	udg->Display();
	//1.4.删除顶点、边
	cout << endl << "无向图删除顶点v1、边arc9:" << endl;
	udg->DeleteVertex(v1);
	udg->DeleteArc(arc9);
	udg->Display();
 
	//测试2:有向图
	cout << endl << "有向图:" << endl;
	GraphAdjMat * dg = new GraphAdjMat(GraphAdjMat::DG);
	dg->Init(vexs, arcsList);
	dg->Display();
	//2.1.深度优先遍历
	cout << endl << "有向图深度优先遍历序列:" << endl;
	dg->Display_DFS(v1);
	//2.2.广度优先遍历
	cout << endl << "有向图广度优先遍历序列:" << endl;
	dg->Display_BFS(v2);
 
	//测试:无向网
	cout << endl << "无向网:" << endl;
	GraphAdjMat * udn = new GraphAdjMat(GraphAdjMat::UDN);
	udn->Init(vexs, arcsList);
	udn->Display();
 
	//测试:有向网
	cout << endl << "有向网:" << endl;
	GraphAdjMat * dn = new GraphAdjMat(GraphAdjMat::DN);
	dn->Init(vexs, arcsList);
	dn->Display();
	
	return 0;
}

 

上一篇:【PAT】A1072 Gas Station【Dijkstra算法】


下一篇:Leetcode 8. 字符串转换整数 (atoi)(DAY 165)---- LeetCode 精选 TOP 面试题