图的遍历-深度优先和广度优先遍历
程序员文章站
2024-02-11 13:23:40
...
图的遍历
之前学数据机构学了图的深度遍历和广度遍历,但是都没有手动实现,直到做笔试题才发现问题很严重,通过对图的遍历,让我更加喜欢面向对象的方式来编程。
通过邻接矩阵的形成来存储图的信息。广度优先遍历和二叉树的按层遍历十分相似。
//
// Created by lss on 2020-03-23.
//
#include <iomanip>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define MAX 100
#define mainMatrixUDG main
class MatrixUDG{
private:
char mVexs[MAX]; //顶点集
int mVexNum; // 顶点数
int mEdgNum; // 边数
int mMatrix[MAX][MAX]; // 邻接矩阵
public:
MatrixUDG(); // 创建图(自己输入数据)
MatrixUDG(char vexs[],int vlen,char edges[][2],int elen); // 创建图(提供矩阵)
~MatrixUDG();
void DFS();
void BFS();
void print(); // 打印矩阵
private:
char readChar(); // 输入一个字符
int getPosition(char ch); // 返回ch在mMatrix中的位置
int firstVertex(int v); // 返回顶点的第一个临界顶点的索引
int nextVertex(int v,int w); // 返回顶点V相对于w的下一个邻接顶点的索引
void DFS(int i,int* visited);// 深度优先遍历的递归实现
};
/*
* 自己输入数据创建图
*/
MatrixUDG::MatrixUDG() {
char c1,c2;
int i,p1,p2;
cin>>mVexNum; // 顶点数
cin>>mEdgNum; // 边数
// 判断输入是否合法
if(mVexNum<1 ||mEdgNum<1 ||(mEdgNum > (mVexNum*(mVexNum-1))))
return;
for(i = 0;i<mVexNum;i++){
mVexs[i] = readChar();
}
for(i=0;i<mEdgNum;i++){
// 读取结束和起始顶点
c1 = readChar();
c2 = readChar();
p1 = getPosition(c1);
p2 = getPosition(c2);
if(p1==-1 || p2== -1){
return;
}
mMatrix[p1][p2] = 1;
mMatrix[p2][p1] = 1;
}
}
MatrixUDG::~MatrixUDG() {}
/*
* ch在mMatrix中的位置
*/
int MatrixUDG::getPosition(char ch) {
int i;
for(i=0;i<mVexNum;i++){
if(mVexs[i] == ch)
return i;
}
return -1;
}
/*
* 读取一个字符
*/
char MatrixUDG::readChar() {
char ch;
do{
cin>>ch;
}while(!(ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z'));
return ch;
}
/*
* 返回顶点v的第一个邻接顶点的索引
*/
int MatrixUDG::firstVertex(int v) {
int i;
if(v<0 || v>(mVexNum-1))
return -1;
for(i=0;i<mVexNum;i++)
if(mMatrix[v][i] == 1)
return i;
return -1;
}
/*
* 返回v相对于w的下一个邻接顶点的索引
*/
int MatrixUDG::nextVertex(int v, int w) {
int i;
if(v<0 || v>(mVexNum-1) || w<0 ||w>(mVexNum-1))
return -1;
for(i = w+1;i<mVexNum;i++){
if(mMatrix[v][i] == 1)
return i;
}
return -1;
}
/*
* 深度优先遍历的递归实现
*/
void MatrixUDG::DFS(int i, int* visited) {
int w;
visited[i] = 1;
cout<<mVexs[i]<<' ';
for(w = firstVertex(i);w>=0;w=nextVertex(i,w)){
if(!visited[w])
DFS(w,visited);
}
}
/*
* 深度优先搜索遍历图
*/
void MatrixUDG::DFS() {
int i;
int visited[MAX]; // 访问标记设置
for(i=0;i<mVexNum;i++)
visited[i] = 0;
for(i=0;i<mVexNum;i++){
if(!visited[i])
DFS(i,visited);
}
cout<<endl;
}
/*
* 广度优先遍历
*/
void MatrixUDG::BFS() {
int head = 0;
int rear = 0;
int queue[MAX];
int visited[MAX];
int i,j,k;
for(i=0;i<mVexNum;i++){
visited[i] = 0;
}
for(i=0;i<mVexNum;i++){
if(!visited[i]){
visited[i] = 1;
cout<<mVexs[i]<<" ";
queue[rear++] = i; // 入队列
}
while(head != rear){
j = queue[head++]; // 出队列
for(k = firstVertex(j);k>=0;k=nextVertex(j,k)){
if(!visited[k]){
visited[k] = 1;
cout<<mVexs[k]<<" ";
queue[rear++] = k;
}
}
}
}
cout<<endl;
}
void MatrixUDG::print() {
int i,j;
for(i=0;i<mVexNum;i++){
for(j=0;j<mVexNum;j++){
cout<<mMatrix[i][j]<<" ";
}
cout<<endl;
}
}
int mainMatrixUDG(){
MatrixUDG* matrixUdg = new MatrixUDG();
matrixUdg->print();
matrixUdg->DFS();
matrixUdg->BFS();
return 0;
}
结果:
参考博客: 参考博客
上一篇: java中的参数传递(值传递等)