题目描述: 分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。 下面邻接矩阵和邻接表均以下图为例,其中已标注了正确的dfs,bfs顺序图和相关的表示法。 几句话明白深度与广度搜索:深度优先就像你被困在了迷宫里面,想要出去必须一路走到底,直到走不通了才回溯,重点是回溯。而广度优先就像你丢了眼镜,看不清的时候满地寻找,辐射范围大。 上次实验四哈夫曼树全部完整代码见此处 已经上传深搜和广搜的专训题目,每一题都涉及2种解法,更加全方位地展现其中的不同。详情点击此处
邻接矩阵存储图 MGraph.cpp
#include <iostream>
#include <queue>
using namespace std;
typedef struct{
int v[500];
int e[500][500];
int vsum,esum;
bool visit[500];
}MGraph;
void Create(MGraph &g){
cout<<"请输入图的顶点总数和边数"<<endl;
cin>>g.vsum>>g.esum;
cout<<"输入图中节点信息"<<endl;
for(int i=0;i<g.vsum;i++){
cin>>g.v[i];
}
for(int i=0;i<g.vsum;i++){
g.visit[g.v[i]]=false;
for(int j=0;j<g.vsum;j++){
g.e[g.v[i]][g.v[j]]=-1;
}
}
cout<<"输入图中各边的两个顶点和边长"<<endl;
for(int i=0;i<g.esum;i++){
int v1,v2,w;
cin>>v1>>v2>>w;
g.e[v1][v2]=w;
g.e[v2][v1]=w;
}
}
void dfs(MGraph &g,int start,string &str){
str+=(start+48);
str+="->";
g.visit[start]=true;
for(int i=0;i<g.vsum;i++){
int temp=g.v[i];
if(g.visit[temp]==false&&g.e[start][temp]!=-1){
dfs(g,temp,str);
}
}
}
void bfs(MGraph &g,int start,string &str){
queue<int> q;
q.push(start);
g.visit[start]=true;
while(!q.empty()){
int top=q.front();
q.pop();
str+=(top+48);
str+="->";
for(int i=0;i<g.vsum;i++){
int temp=g.v[i];
if(g.e[top][temp]!=-1&&g.visit[temp]==false){
q.push(temp);
g.visit[temp]=true;
}
}
}
}
void traver1(MGraph &g){
for(int i=0;i<g.vsum;i++){
g.visit[g.v[i]]=false;
}
cout<<"\n广度搜索遍历:"<<endl;
string m="";
bfs(g,1,m);
m=m.substr(0,m.length()-2);
cout<<m<<endl;
}
void traver2(MGraph &g){
for(int i=0;i<g.vsum;i++){
g.visit[g.v[i]]=false;
}
cout<<"深度搜索遍历:"<<endl;
string m="";
dfs(g,1,m);
m=m.substr(0,m.length()-2);
cout<<m<<endl;
}
int main(){
MGraph g;
Create(g);
traver1(g);
traver2(g);
}
结果示意图
邻接表存储图 AGraph.cpp
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
bool visit[500];
typedef struct ArcNode{
int adv;
struct ArcNode *nextArc;
int data;
}ArcNode;
typedef struct VNode{
ArcNode *first;
string data;
}AdVlist;
typedef struct ALGraph{
AdVlist vts[500];
int v,e;
}ALGraph;
int find(ALGraph &g,string x){
for(int i=0;i<g.v;i++){
if(x==g.vts[i].data)
return i;
}
return -1;
}
void Create(ALGraph &g){
string v1,v2;
cout<<"输入图的顶点数和边数"<<endl;
cin>>g.v>>g.e;
cout<<"输入图中结点信息"<<endl;
for(int i=0;i<g.v;i++){
cin>>g.vts[i].data;
g.vts[i].first=NULL;
}
cout<<"输入图中两个顶点(起点和终点)"<<endl;
for(int i=0;i<g.e;i++){
cin>>v1>>v2;
int j,k;
j=find(g,v1);
k=find(g,v2);
ArcNode *p1=new ArcNode;
ArcNode *p2=new ArcNode;
p1->adv=k;
p1->nextArc=g.vts[j].first;
g.vts[j].first=p1;
p2->adv=j;
p2->nextArc=g.vts[k].first;
g.vts[k].first=p2;
}
}
void dfs(ALGraph &g,int n){
cout<<g.vts[n].data;
visit[n]=false;
ArcNode *p=g.vts[n].first;
while(p){
if(visit[p->adv]){
cout<<"->";
dfs(g,p->adv);
}
p=p->nextArc;
}
}
void bfs(ALGraph &g,int n){
queue<int> q;
q.push(n);
while(!q.empty()){
if(q.front()!=0) cout<<"->";
cout<<g.vts[q.front()].data;
visit[q.front()]=true;
ArcNode *p=g.vts[q.front()].first;
while(p){
if(!visit[p->adv]){
visit[p->adv]=true;
q.push(p->adv);
}
p=p->nextArc;
}
q.pop();
}
}
int main(){
ALGraph g;
Create(g);
memset(visit,true,sizeof(visit));
cout<<"深度优先遍历:"<<endl;
dfs(g,0);
cout<<"\n广度优先遍历:"<<endl;
bfs(g,0);
return 0;
}
结果运行图 注意看我上述图的说明,注意指针的位置,不是根据矩阵法的dfs/bfs,而是看我写的邻接表的图。
|