数据结构学习之图的深度优先遍历和广度优先遍历
程序员文章站
2022-05-20 19:06:15
...
图的遍历的关键是确定每个顶点的邻接顶点，也即是确定由顶点组成的邻接矩阵。
这里参考网上的一篇基于C++的邻接矩阵的实现过程
图类的实现：
#include<iostream>
#include<iomanip>
using namespace std;
//最大权值
#define MAXWEIGHT 100
//用邻接矩阵实现图
class Graph
{
private:
//是否带权
bool isWeighted;
//是否有向
bool isDirected;
//顶点数
int numV;
//边数
int numE;
//邻接矩阵
int **matrix;
public:
/*
构造方法
numV是顶点数，isWeighted是否带权值，isDirected是否有方向
*/
Graph(int numV, bool isWeighted = false, bool isDirected = false);
//建图
void createGraph();
//析构方法
~Graph();
//获取顶点数
int getVerNums()
{return numV;}
//获取边数
int getEdgeNums()
{return numE;}
//设置指定边的权值
void setEdgeWeight(int tail, int head, int weight);
//打印邻接矩阵
void printAdjacentMatrix();
//检查输入
bool check(int i, int j, int w = 1);
};/*
构造方法
numV是顶点数，isWeighted是否带权值，isDirected是否有方向
*/
Graph::Graph(int numV, bool isWeighted, bool isDirected)
{
while (numV <= 0)
{
cout << "输入的顶点数不正确！，重新输入 ";
cin >> numV;
}
this->numV = numV;
this->isWeighted = isWeighted;
this->isDirected = isDirected;
matrix = new int*[numV]; //指针数组
int i, j;
for (i = 0; i < numV; i++)
matrix[i] = new int[numV];
//对图进行初始化
if (!isWeighted) //无权图
{
//所有权值初始化为0
for (i = 0; i < numV; i++)
for (j = 0; j < numV; j++)
matrix[i][j] = 0;
}
else //有权图
{
//所有权值初始化为最大权值
for (i = 0; i < numV; i++)
for (j = 0; j < numV; j++)
matrix[i][j] = MAXWEIGHT;
}
}
//建图
void Graph::createGraph()
{
cout << "输入边数 ";
while (cin >> numE && numE < 0)
cout << "输入有误！，重新输入 ";
int i, j, w;
if (!isWeighted) //无权图
{
if (!isDirected) //无向图
{
cout << "输入每条边的起点和终点：\n";
for (int k = 0; k < numE; k++)
{
cin >> i >> j;
while (!check(i, j))
{
cout << "输入的边不对！重新输入\n";
cin >> i >> j;
}
matrix[i][j] = matrix[j][i] = 1;
}
}
else //有向图
{
cout << "输入每条边的起点和终点：\n";
for (int k = 0; k < numE; k++)
{
cin >> i >> j;
while (!check(i, j))
{
cout << "输入的边不对！重新输入\n";
cin >> i >> j;
}
matrix[i][j] = 1;
}
}
}
else //有权图
{
if (!isDirected) //无向图
{
cout << "输入每条边的起点、终点和权值：\n";
for (int k = 0; k < numE; k++)
{
cin >> i >> j >> w;
while (!check(i, j, w))
{
cout << "输入的边不对！重新输入\n";
cin >> i >> j >> w;
}
matrix[i][j] = matrix[j][i] = w;
}
}
else //有向图
{
cout << "输入每条边的起点、终点和权值：\n";
for (int k = 0; k < numE; k++)
{
cin >> i >> j >> w;
while (!check(i, j, w))
{
cout << "输入的边不对！重新输入\n";
cin >> i >> j >> w;
}
matrix[i][j] = w;
}
}
}
}
//析构方法
Graph::~Graph()
{
int i = 0;
for (i = 0; i < numV; i++)
delete[] matrix[i];
delete[]matrix;
}
//设置指定边的权值
void Graph::setEdgeWeight(int tail, int head, int weight)
{
if (isWeighted)
{
while (!check(tail, head, weight))
{
cout << "输入不正确，重新输入边的起点、终点和权值 ";
cin >> tail >> head >> weight;
}
if (isDirected)
matrix[tail][head] = weight;
else
matrix[tail][head] = matrix[head][tail] = weight;
}
else
{
while (!check(tail, head, 1))
{
cout << "输入不正确，重新输入边的起点、终点 ";
cin >> tail >> head;
}
if (isDirected)
matrix[tail][head] = 1-matrix[tail][head];
else
matrix[tail][head] = matrix[head][tail] = 1 - matrix[tail][head];
}
}
//输入检查
bool Graph::check(int i, int j, int w)
{
if (i >= 0 && i < numV && j >= 0 && j < numV && w > 0 && w <= MAXWEIGHT)
return true;
else
return false;
}
//打印邻接矩阵
void Graph::printAdjacentMatrix()
{
int i, j;
cout.setf(ios::left);
cout << setw(4) << " ";
for (i = 0; i < numV; i++)
cout << setw(4) << i;
cout << endl;
for (i = 0; i < numV; i++)
{
cout << setw(4) << i;
for (j = 0; j < numV; j++)
cout << setw(4) << matrix[i][j];
cout << endl;
}
}调用主函数main：
int main()
{
cout << "******使用邻接矩阵实现图结构***by David***" << endl;
bool isDirected, isWeighted;
int numV;
cout << "建图" << endl;
cout << "输入顶点数 ";
cin >> numV;
cout << "边是否带权值，0(不带) or 1(带) ";
cin >> isWeighted;
cout << "是否是有向图，0(无向) or 1(有向) ";
cin >> isDirected;
Graph graph(numV, isWeighted, isDirected);
cout << "这是一个";
isDirected ? cout << "有向、" : cout << "无向、";
isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;
graph.createGraph();
cout << "打印邻接矩阵" << endl;
graph.printAdjacentMatrix();
cout << endl;
int tail, head, weight;
cout << "修改指定边的权值" << endl;
if (isWeighted) //针对有权图
{
cout << "输入边的起点、终点和权值 ";
cin >> tail >> head >> weight;
graph.setEdgeWeight(tail, head, weight);
}
else //针对无权图
{
cout << "输入边的起点、终点 ";
cin >> tail >> head;
graph.setEdgeWeight(tail, head, 1);
}
cout << "修改成功！" << endl;
cout << "打印邻接矩阵" << endl;
graph.printAdjacentMatrix();
system("pause");
return 0;
}参考博文：http://blog.csdn.net/zhangxiangdavaid/article/details/38321327
下面是一个图的深度优先遍历和广度优先遍历的实例：
深度优先遍历：
/*
深度优先搜索
从vertex开始遍历，visit是遍历顶点的函数指针
*/
void Graph::dfs(int vertex, void (*visit)(int))
{
stack<int> s;
//visited[i]用于标记顶点i是否被访问过
bool *visited = new bool[numV];
//count用于统计已遍历过的顶点数
int i, count;
for (i = 0; i < numV; i++)
visited[i] = false;
count = 0;
while (count < numV)
{
visit(vertex);
visited[vertex] = true;
s.push(vertex);
count++;
if (count == numV)
break;
while (visited[vertex])
{
for (i = 0; i < numV
&& (visited[i]
|| matrix[vertex][i] == 0 || matrix[vertex][i] == MAXWEIGHT); i++);
if (i == numV) //当前顶点vertex的所有邻接点都已访问完了
{
if (!s.empty())
{
s.pop(); //此时vertex正是栈顶，应先出栈
if (!s.empty())
{
vertex = s.top();
s.pop();
}
else //若栈已空，则需从头开始寻找新的、未访问过的顶点
{
for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
}
}
else //若栈已空，则需从头开始寻找新的、未访问过的顶点
{
for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
}
}
else //找到新的顶点应更新当前访问的顶点vertex
vertex = i;
}
}
delete[]visited;
}
/*
广度优先搜索
从vertex开始遍历，visit是遍历顶点的函数指针
*/
void Graph::bfs(int vertex, void(*visit)(int))
{
//使用队列
queue<int> q;
//visited[i]用于标记顶点i是否被访问过
bool *visited = new bool[numV];
//count用于统计已遍历过的顶点数
int i, count;
for (i = 0; i < numV; i++)
visited[i] = false;
q.push(vertex);
visit(vertex);
visited[vertex] = true;
count = 1;
while (count < numV)
{
if (!q.empty())
{
vertex = q.front();
q.pop();
}
else
{
for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
visit(vertex);
visited[vertex] = true;
count++;
if (count == numV)
return;
q.push(vertex);
}
//代码走到这里，vertex是已经访问过的顶点
for (int i = 0; i < numV; i++)
{
if (!visited[i] && matrix[vertex][i] > 0 && matrix[vertex][i] < MAXWEIGHT)
{
visit(i);
visited[i] = true;
count ++;
if (count == numV)
return;
q.push(i);
}
}
}
delete[]visited;
}void visit(int vertex)
{
cout << setw(4) << vertex;
}
int main()
{
cout << "******图的遍历：深度优先、广度优先***by David***" << endl;
bool isDirected, isWeighted;
int numV;
cout << "建图" << endl;
cout << "输入顶点数 ";
cin >> numV;
cout << "边是否带权值，0(不带) or 1(带) ";
cin >> isWeighted;
cout << "是否是有向图，0(无向) or 1(有向) ";
cin >> isDirected;
Graph graph(numV, isWeighted, isDirected);
cout << "这是一个";
isDirected ? cout << "有向、" : cout << "无向、";
isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;
graph.createGraph();
cout << "打印邻接矩阵" << endl;
graph.printAdjacentMatrix();
cout << endl;
cout << "深度遍历" << endl;
for (int i = 0; i < numV; i++)
{
graph.dfs(i, visit);
cout << endl;
}
cout << endl;
cout << "广度遍历" << endl;
for (int i = 0; i < numV; i++)
{
graph.bfs(i, visit);
cout << endl;
}
system("pause");
return 0;
}下面是参考《大话数据结构》上的C语言实现的图的深度遍历和广度遍历：
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MAXVEX 100
#define MAX 100
#define INFINITY 65535
#define MAXSIZE 100
typedef int VertexType;
typedef int EdgeType;
typedef int Boolean;
Boolean visited[MAX];
typedef int QElemType;
typedef struct{
QElemType data[MAXSIZE];
int front;
int rear;
}Queue;
typedef struct{
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertexes,numEdges;
}MGraph;
void CreateMGraph(MGraph *g)
{
int i,j,k,w;
cout<<" 请输入顶点数和边数:"<<endl;
//scanf("%d,%d",&g->numVertexes,&g->numEdges);
cin>>g->numVertexes;
cin>>g->numEdges;
for(i=0;i<g->numVertexes;i++){
//scanf(&g->vexs[i]);
cin>>g->vexs[i];
}
for(i=0;i<g->numVertexes;i++){
for(j=0;j<g->numVertexes;j++){
g->arc[i][j]=INFINITY;
}
}
for(k=0;k<g->numEdges;k++){
cout<<"输入边（vi,vj)上的下标i，下标j和权w:"<<endl;
//scanf("%d,%d,%d",&i,&j,&w);
cin>>i;
cin>>j;
cin>>w;
g->arc[i][j]=w;
g->arc[j][i]=g->arc[i][j];
}
}
void DFS(MGraph *g,int i)
{
int j;
visited[i]=1;
cout<<" G.vexs[i]= "<<g->vexs[i]<<" i= "<<i<<endl;
for(j=0;j<g->numVertexes;j++){
if(g->arc[i][j]==1 && !visited[j]){
cout<<"j= "<<j;
DFS(g,j);
}
}
}
void DFSTraverse(MGraph *g)
{
int i;
for(i=0;i<g->numVertexes;i++){
visited[i]=0;
}
for(i=0;i<g->numVertexes;i++){
if(!visited[i]){
cout<<"in Traverse i= "<<i<<endl;
DFS(g,i);
}
}
}
int InitQueue(Queue *Q)
{
Q->front=0;
Q->rear=0;
return 0;
}
int EnQueue(Queue *Q,QElemType e)
{
if((Q->rear+1)%MAXSIZE == Q->front) ///判断队列是f否满
return -1;
Q->data[Q->rear]=e;
Q->rear=(Q->rear+1)%MAXSIZE;
return 0;
}
int DeQueue(Queue *Q,QElemType *e)
{
if(Q->front == Q->rear)
return -1;
*e=Q->data[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
return 0;
}
int QueueEmpty(Queue *Q)
{
if(Q->rear == Q->front)
return -1;
return 0;
}
///广度优先遍历
void BFSTraverse(MGraph *G)
{
int i,j;
Queue Q;
for(i=0;i<G->numVertexes;i++)
visited[i]=0;
InitQueue(&Q); ///初始化辅助队列
for(i=0;i<G->numVertexes;i++){ ///循环访问每一个顶点
if(!visited[i]){ ///处理未访问过的
visited[i]=1;
cout<<"G->vexs[i]= "<<G->vexs[i];
EnQueue(&Q,i); ///此顶点入队列
while(!QueueEmpty(&Q)){ ///判断当前队列是否为空
DeQueue(&Q,&i); ///队中元素出队列
for(j=0;j<G->numVertexes;j++){ ///判断其他与此顶点有共同边的顶点
if(G->arc[i][j]==1 &&!visited[j]){ ///判断是否访问过
visited[j]=1; ///标记已经访问过
cout<<" g->vexs[j]= "<<G->vexs[j]<<endl;
EnQueue(&Q,j); ///将找到的顶点入队列
}
}
}
}
}
}
int main()
{
MGraph *g;
g=(MGraph *)malloc(sizeof(MGraph));
CreateMGraph(g);
///DFSTraverse(g); ///深度优先遍历
BFSTraverse(g); ///广度优先遍历
return 0;
}