【数据结构】实验十 图的遍历

实验内容：
使用邻接矩阵或链接表来存储图，并编程实现DFS和BFS算法。

#include
using namespace std;
#define MaxInt 32767    // 极大值 ∞
#define MVNum 100       // 最大顶点数
#define MAXSIZE 100     // 队列的最大长度

bool visit_DFS[MVNum] = { false }; // 定义一个DFS访问数组 并初始化为false(代表被访问过)
bool visit_BFS[MVNum] = { false }; // 定义一个BFS访问数组 并初始化为false(代表被访问过)

typedef char VerTexType; // 假设顶点的数据类型为字符型
typedef int ArcType; // 假设边的权值类型为整型
typedef struct
{
	VerTexType vexs[MVNum]; // 顶点表
	ArcType arcs[MVNum][MVNum]; // 邻接矩阵
	int vexnum, arcnum; // 图的当前点数和边数
}AMGraph;

typedef struct // 定义队列的结构体
{
	VerTexType* base; // 存储队列内元素 元素类型为Person
	int front; // 头指针 始终指向队列首元素
	int rear; // 尾指针 始终指向队列尾元素
}SqQueue;

void InitQueue(SqQueue& Q)// 队列的初始化
{
	Q.base = new VerTexType[MAXSIZE];
	if (!Q.base)
		exit(1);
	Q.front = Q.rear = 0; // 将队列头指针和尾指针置为0 此时队列为空
}

void EnQueue(SqQueue& Q, int e) // 在队尾插入元素 e
{
	if ((Q.rear + 1) % MAXSIZE == Q.front) // 队列已满
		return;
	Q.base[Q.rear] = e; // 尾指针始终指向队列尾元素的下一个元素
	Q.rear = (Q.rear + 1) % MAXSIZE; // 赋值完成后 尾指针加1
}

void DeQueue(SqQueue& Q, int& e) // 删除Q的队头元素，用e返回其值
{
	if (Q.front == Q.rear) // 判断是否队空
		return;
	e = Q.base[Q.front]; // 保存队头元素
	Q.front = (Q.front + 1) % MAXSIZE; // 队头指针加1
}

bool EmptyQueue(SqQueue Q) // 判断是否是空队列
{
	if (Q.front == Q.rear) // 空队列
	{
		return true;
	}
	else // 非空队列
	{
		return false;
	}
}

int LocateVex(AMGraph G, VerTexType v) // 返回顶点数组的下标
{
	for (int i = 0; i < G.arcnum; i++)
		if (G.vexs[i] == v)
			return i;
	return -1; // 未找到顶点时 返回-1
}

void CreateUDN(AMGraph& G) // 采用邻接矩阵表示法创建无向图
{
	cout << "请输入总顶点数和边数(以空格分隔开): ";
	cin >> G.vexnum >> G.arcnum;
	cout << "请依次输入各个点的信息: ";
	for (int i = 0; i < G.vexnum; i++) // 依次输入点的信息
		cin >> G.vexs[i];
	for (int i = 0; i < G.vexnum; i++) // 初始化邻接矩阵
		for (int j = 0; j < G.vexnum; j++)
			if (i == j) // 主对角线的元素值 置为0
				G.arcs[i][j] = 0;
			else // 边的权值置为最大值MaxInt
				G.arcs[i][j] = MaxInt;
	VerTexType v1, v2;
	ArcType w;
	for (int k = 0; k < G.arcnum; k++) // 构造邻接矩阵
	{
		cout << "请依次输入一条边依附的两个顶点及权值: ";
		cin >> v1 >> v2 >> w; // 输入一条边依附的顶点及权值
		int i = LocateVex(G, v1); // 确定v1在G中的位置(顶点数组的下标)
		int j = LocateVex(G, v2); // 确定v2在G中的位置(顶点数组的下标)
		if (i == -1 || j == -1) // 判断是否成功赋值 即是否存在输入的顶点
		{
			cout << "不存在输入顶点！" << endl;
			k--; // 遍历次数减一
			continue; // 直接进行下次循环
		}
		G.arcs[i][j] = w; // 边的权值置为w
		G.arcs[j][i] = G.arcs[i][j]; // 边的权值置为w
	}
}

void OutPut_LinJie(AMGraph G) // 输出邻接矩阵
{
	cout << "t";
	for (int i = 0; i < G.vexnum; i++) // 输出第一行 -> 各个点的信息
		cout << G.vexs[i] << "t";
	cout << endl;
	for (int i = 0; i < G.vexnum; i++) // 依次输出每一行各个点的信息(顶点信息 权值)
	{
		cout << G.vexs[i] << "t";
		for (int j = 0; j < G.vexnum; j++)
			cout << G.arcs[i][j] << "t";
		cout << endl;
	}
}

void DFS_AM(AMGraph G, int v) // 深度优先搜索
{
	cout << G.vexs[v]; // 访问第v个顶点
	visit_DFS[v] = true; // 将第v个顶点的标志数组的相应分量值置为true
	for (int w = 0; w < G.vexnum; w++) // 依次检查v的所有邻接点
	{
		if ((G.arcs[v][w] != MaxInt) && (!visit_DFS[w]))
		{ // 邻接点有值 且没被访问时
			cout << " -> ";
			DFS_AM(G, w); // 递归调用DFS
		}
	}
}

int FirstAdjVex(AMGraph G, int u) // 查找u的第一个邻接点 返回其下标
{
	for (int i = 0; i < G.vexnum; i++)
		if (G.arcs[u][i] != MaxInt)
			return i;
	return -1; // 未查找到 返回-1
}

int NextAdjVex(AMGraph G, int u, int w) // 查找u的第一个没被访问的邻接点
{
	for (int i = 0; i < G.vexnum; i++)
		if ((G.arcs[u][i] != MaxInt) && (!visit_BFS[i]))
			return i; // 返回其下标
	return -1; // 未查找到 返回-1
}

void BFS_AM(AMGraph G, int v) // 广度优先搜索
{
	cout << G.vexs[v]; // 访问第v个顶点
	visit_BFS[v] = true; // 将其访问标志数组的相应分量置为true
	SqQueue Q; // 定义一个队列
	InitQueue(Q); // 初始化定义的队列
	EnQueue(Q, v); // 第v个顶点进队
	while (!EmptyQueue(Q)) // 队列非空 执行循环条件
	{
		int u; // 定义u 存储顶点的下标
		DeQueue(Q, u); // 队首元素出队 赋值给u
		for (int w = FirstAdjVex(G, u); w >= 0 && w < G.vexnum; w = NextAdjVex(G, u, w))
		{// 从u的第一个邻接点遍历到最后一个邻接点
			if (!visit_BFS[w]) // 判断邻接点是否被访问过
			{// 没有被访问过 
				cout << " -> " << G.vexs[w]; // 访问该顶点
				visit_BFS[w] = true; // 并将标志数组的相应分量值置为true
				EnQueue(Q, w); // w进队
			}
		}
	}
}

int main()
{
	AMGraph G; // 定义一个邻接矩阵
	int t; // 临时记录查找开始位置
	CreateUDN(G); // 创建一个邻接矩阵 存储图的信息
	OutPut_LinJie(G); // 输出邻接矩阵
	cout << "请输入DFS的查找开始位置: ";
	cin >> t;
	cout << "DFS: ";
	DFS_AM(G, t - 1); // 深度优先搜索
	cout << endl;
	cout << "请输入BFS的查找开始位置: ";
	cin >> t;
	cout << "BFS: ";
	BFS_AM(G, t - 1); // 广度优先搜素
	cout << endl;
	system("pause");
	return 0;
}