当我们要从图中的某一个点开始要进行深度优先遍历的时候，首先要访问这个点，在访问完这个点后，就要看这个点是否有未被访问的邻接顶点，假如有，则访问这个邻接顶点，在访问完这个邻接顶点后我们还要继续判断这个邻接顶点是否也有未被访问到的邻接顶点，假如有那就继续访问…就这样不停的循环下去，直到图中所有的顶点都被访问到。举个例子：
假如现在我们要从这个无向图中标号为1的顶点开始深度遍历，那么它的遍历次序应该是这样的：
1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7
在访问一个点后，将这个点的所有未访问的邻接顶点一次性进行全部访问，然后依照访问邻接顶点的先后顺序，依次将邻接顶点的全部未访问的邻接顶点一次性进行全部访问，如果还有没有被访问到的点，那就依照上一次访问邻接顶点的顺序，依次将邻接顶点的全部未访问的邻接顶点一次性进行全部访问，直到最终将图内的顶点全部访问完成。为了将先后访问到的邻接顶点记录下来，我们需要一个先进先出的队列来进行辅助。每访问一个节点就将这个节点放入到这个队列中，当这个点的所有邻接顶点被访问后就将这个顶点从队列中删除。还是上面的那个无向图，假如我们要对其进行广度优先遍历，那么它的遍历次序应该是这样的：
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
Graph.h: #pragma once #include#include"LinkQueue.h" #include"MinHeap.h" using namespace std; //图中所包含最大顶点数目 #define MAX_VERTEX_NUMBER 10 //弧 struct Arc { //弧长 int length; //下一条弧 Arc *next_arc; }; //顶点 struct Vertex { //顶点在顶点数组中的位置/顶点的编号 int vertex_position; //依附于顶点的第一条边 Arc *first_arc; //邻接顶点的个数 int adjacent_number; //邻接顶点在顶点数组中的位置/邻接顶点的编号 int adjacent_vertexes_position[MAX_VERTEX_NUMBER]; //源节点到该节点的最短路径的权重 int weight; }; //图 class Graph { public: //顶点数组 Vertex *vertexes_array[MAX_VERTEX_NUMBER]; //图当前顶点数目 int vertex_number; //图的弧的数目 int arc_number; //图的种类 无向图 1 有向图 2 int graph_kind; //图的创建 void graph_creat(); //获取下一个未访问的邻接节点 假如该节点的所有邻接节点被访问 那么就返回null int get_next_adjacent(int *visit,int position); //dfs void dfs(int *visit,int position); //深度优先遍历 void dfs_traverse(); //广度优先遍历 void bfs_traverse(); };
Graph.cpp:
#include"Graph.h"
//图的创建
void Graph::graph_creat(){
//图的顶点数目
cout<<"请问该图一共有多少个节点?"<>vertex_number;
//弧的数目
cout<<"请问该图一共有多少条弧？"<>arc_number;
//请输入图的类型
cout<<"请输入该图的类型,无向图请输入1，有向图请输入2"<>graph_kind;
//依次输入各个节点的信息
for (int i = 1; i <= vertex_number; i++)
{
//创建顶点
vertexes_array[i] = new Vertex;
//顶点编号
vertexes_array[i]->vertex_position = i;
cout<<"请输入第"<>vertexes_array[i]->adjacent_number;
//依附于第i个节点的第一条弧
vertexes_array[i]->first_arc = new Arc;
//连接第i个节点与第j个节点的弧
Arc *temporary_arc = vertexes_array[i]->first_arc;
for (int j = 1; j <= vertexes_array[i]->adjacent_number; j++)
{
cout<<"请输入与第"<>vertexes_array[i]->adjacent_vertexes_position[j];
cout<<"请输入第"<>temporary_arc->length;
//下一条弧
temporary_arc->next_arc= new Arc;
temporary_arc = temporary_arc->next_arc;
}
temporary_arc->next_arc= NULL;
}
}
//获取下一个未访问的邻接节点 假如该节点的所有邻接节点被访问 那么就返回null
int Graph::get_next_adjacent(int *visit,int position){
for (int j = 1; j <= vertexes_array[position]->adjacent_number; j++)
{
//下一个邻接节点的编号
int adjacent_position = vertexes_array[position]->adjacent_vertexes_position[j];
if (visit[adjacent_position] == 0)
{
return adjacent_position;
}
}
return 0;
}
//dfs
void Graph::dfs(int *visit,int position){
//如果该节点为空就访问该节点并将该点的访问数组变为1
if (visit[position] == 0)
{
cout<vertex_position<<" ";
}
visit[position] = 1;
//依次深度遍历该节点的邻接节点
for (int i = 1; i <= vertexes_array[position]->adjacent_number; i++)
{
//获取该点的未访问的邻接节点在顶点数组中的位置
int next_adjacent = get_next_adjacent(visit,position);
//假如该节点有未访问的邻接节点
if (next_adjacent != 0)
{
//深度优先遍历邻接节点
dfs(visit,next_adjacent);
}
}
}
//深度优先遍历
void Graph::dfs_traverse(){
//创建访问标志数组 访问过后置1 未访问置0 这里数组的第0个位置舍弃从1开始
int visit[MAX_VERTEX_NUMBER+1];
//访问标志数组初始化
for (int i = 0; i < MAX_VERTEX_NUMBER+1; i++)
{
visit[i] = 0;
}
// dfs 从第一个节点进行深度遍历
dfs(visit,1);
}
//广度优先遍历
void Graph::bfs_traverse(){
//创建访问标志数组 访问过后置1 未访问置0 这里数组的第0个位置舍弃从1开始
int visit[MAX_VERTEX_NUMBER+1];
//访问标志数组初始化
for (int i = 0; i < MAX_VERTEX_NUMBER+1; i++)
{
visit[i] = 0;
}
//创建辅助队列
LinkQueue queue;
//从该图中第一个顶点开始遍历
if (visit[1] == 0)
{
//输出该节点并将该点的访问标志置1
cout<vertex_position<<" ";
visit[1] = 1;
//将该点进入队列
queue.insert(1);
//按照队列中的顶点依次遍历
while (!queue.quene_empty())
{
//队列中的第一元素
int first = queue.front->next_node->data;
//遍历队列中的第一个元素所指向的节点的邻接节点
for (int i = 1; i <= vertexes_array[first]->adjacent_number; i++)
{
int next_adjacent = get_next_adjacent(visit,first);
if (next_adjacent != 0)
{
//输出该节点并将该节点的访问标志置1
cout<vertex_position<<" ";
visit[next_adjacent] = 1;
//将访问过的节点插入队列
queue.insert(next_adjacent);
}
else
{
break;
}
}
//该节点的所有邻接节点都被遍历后从队列中删除
queue.delete_node();
}
}
}
