文章目录
编程语言
C++
需求分析
实验目的
通过建立无向非连通图，并对图进行DFS及BFS遍历，了解图的构建算法，并加深对DFS及BFS的理解。
实验内容
1）建立无向非连通图的邻接表存储结构，要求顶点个数不少于15个。 2）用DFS及BFS对此邻接表进行遍历，打印出两种遍历的顶点访问顺序。3）给定图中任意两个顶点v1和v2及整数k，判断是否存在从v1到v2的路径长度为k的简单路径，若有打印出路径上的顶点序列（要求路径上不含回路）。进一步：找出从v1到v2的所有路径长度为k的简单路径。（简单路径：顶点序列中不含重现的顶点的路径。）
概要设计
数据结构
本实验实现DFS算法是利用栈储存待访问的节点，利用栈的FILO（先入后出）来实现深度搜索；实现BFS是利用队列储存待访问的节点，利用队列的FIFO（先入后出）来实现广度搜索。
测试用例
测试以下5节点图和12节点图
详细设计
首先创建节点结构（包括该路径指向的顶点位置、指向下一个路径、该路径的相关信息）和连线结构（顶点信息、指向第一条依附该节点路径的指针、访问情况），然后根据输入逐个插入邻接表点从而创建邻接表。
本实验实现DFS算法是利用栈储存待访问的节点，利用栈的FILO（先入后出）来实现深度搜索：从根节点开始，遍历节点的连接表，跳过已访问的节点值，将未访问过的节点加入栈，然后逐一取走栈内元素并对取走的节点邻接表进行遍历，重复相同过程，直至栈为空结束；实现BFS是利用队列储存待访问的节点，利用队列的FIFO（先入后出）来实现广度搜索：从根节点开始，遍历节点的连接表，跳过已访问的节点值，将未访问过的节点加入队列，然后逐一取走队列内元素并对取走的节点邻接表进行遍历，重复相同过程，直至队列为空结束。
调试分析
示例测试
遇到的问题
1.有重复遍历的节点情况出现
解决方法：对每个节点增加一个访问情况值，访问邻接表时跳过已访问过的值。
2.寻找简单路径暂无思路
使用说明和测试结果
使用说明
用Visual Studio打开.sln文件即可运行
测试结果
测试通过，符合程序设计要求和需求分析
详细结果见调试分析-示例测试
体会心得
通过本次课程实验，我对数据结构的了解进一步加深，并产生了浓厚的兴趣。虽然在写代码过程中遇到了一些问题，但我通过思考、网上找资料、询问同学等方式最终解决了问题。这次实验让我进一步巩固了建立无向非连通图的方法，及对图进行DFS及BFS遍历算法，了解了图的构建算法，并加深了对DFS及BFS的理解，进一步加强了自学能力，拓展了思路。
程序清单
graph.cpp
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
//节点遍历情况
enum visitCondition
{
no, //未访问
visiting, //正在访问，邻接点还没访问完
yes //访问完毕
};
template<typename VertexType, typename InfoType>
class Graph
{
public:
Graph(int vertexNum) :m_vertexNum(vertexNum), m_arcNum(0)
{
for (int i = 0; i < MAX_VERTEX_NUM; ++i)
{
m_vertices[i].firstArc = nullptr;
}
}
//输出图的信息
void Display()
{
for (int i = 0; i < m_vertexNum; ++i)
{
cout << "第" << i + 1 << "个节点为" << m_vertices[i].data << " 邻接表为：";
ArcNode* node = m_vertices[i].firstArc;
while (node)
{
cout << "->" << m_vertices[node->vertexIndex].data;
node = node->next;
}
cout << endl;
}
}
void BFS()
{
for (int i = 0; i < m_vertexNum; ++i)
{
m_vertices[i].visitconditions = no;
}
cout << "图的广度优先遍历为：";
BFS(&m_vertices[0]);
cout << endl;
}
void DFS()
{
for (int i = 0; i < m_vertexNum; ++i)
{
m_vertices[i].visitconditions = no;
}
cout << "图的深度优先遍历为：";
DFS(&m_vertices[0]);
cout << endl;
}
//创建无向无权图
void Create()
{
InitVertices();
cout << "请分别输入每条边的起始节点和终止节点:" << endl;
int head, tail;
while (cin >> head >> tail)
{
//无向图head->tail tail->head插入两次
Insert(head, tail, 0);
Insert(tail, head, 0);
}
}
void FindMinRoad(int v1, int v2, int k)
{
}
private:
struct ArcNode
{
int vertexIndex; //该路径指向的顶点位置
struct ArcNode* next; //指向下一个路径
InfoType info; //该路径的相关信息，如权重等
};
struct Vertex
{
VertexType data; //顶点信息
ArcNode* firstArc; //指向第一条依附该节点路径的指针
visitCondition visitconditions; //访问情况
};
//最大顶点数
static const int MAX_VERTEX_NUM = 20;
Vertex m_vertices[MAX_VERTEX_NUM]; //顶点列表
int m_vertexNum; //当前顶点数量
int m_arcNum; //当前路径数量
private:
//初始化顶点列表
void InitVertices()
{
cout << "请输入每个顶点的关键字" << endl;
VertexType data;
for (int i = 0; i < m_vertexNum; ++i)
{
cin >> data;
m_vertices[i].data = data;
}
}
//插入一个表节点
void Insert(int headVertex, int tailVertex, InfoType info)
{
//构造一个邻接表节点，即创建一条路径
ArcNode* newNode = new ArcNode;
newNode->info = info;
newNode->next = nullptr;
newNode->vertexIndex = tailVertex;
//找到邻接表的最后一个节点
ArcNode* lastNode = m_vertices[headVertex].firstArc;
if (lastNode == nullptr)
m_vertices[headVertex].firstArc = newNode;
else
{
while (lastNode->next)
{
lastNode = lastNode->next;
}
lastNode->next = newNode;
}
++m_arcNum;
}
void BFS(Vertex* vertex)
{
vertex->visitconditions = visiting;
queue<Vertex*> vertices;
vertices.push(vertex);
while (!vertices.empty())
{
Vertex* curVertex = vertices.front();
vertices.pop();
cout << curVertex->data << "->";
ArcNode* node = curVertex->firstArc;
while (node)
{
Vertex* tmpVertex = &m_vertices[node->vertexIndex];
if (tmpVertex->visitconditions == no)
{
tmpVertex->visitconditions = visiting;
vertices.push(tmpVertex);
}
node = node->next;
}
curVertex->visitconditions = yes;
}
}
void DFS(Vertex* vertex)
{
vertex->visitconditions = visiting;
stack<Vertex*> vertices;
vertices.push(vertex);
while (!vertices.empty())
{
Vertex* curVertex = vertices.top();
vertices.pop();
cout << curVertex->data << "->";
ArcNode* node = curVertex->firstArc;
while (node)
{
Vertex* tmp = &m_vertices[node->vertexIndex];
if (tmp->visitconditions == no)
{
tmp->visitconditions = visiting;
vertices.push(tmp);
}
node = node->next;
}
curVertex->visitconditions = yes;
}
}
};
int main()
{
int vertexNum, v1, v2 , k;
cout << "请输入要创建的图的节点数：";
cin >> vertexNum;
Graph<char, int> g(vertexNum);
g.Create();
g.Display();
g.BFS();
g.DFS();
//cout << "请依次输入需要寻找简单路径的起点和重点v1 v2和路径长度k：";
//cin >> v1 >> v2 >> k;
//g.FindMinRoad(v1, v2, k);
}
原创声明
文章作者：Zam9036
版权声明: 本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0 许可协议
。转载请注明来自
Zam9036的博客
！