Question

求帮忙 图的遍历的实现 1）先任意创建创建一个图 2）图的DFS.BFS的递归和非递归算法的实现3)

3）要求用有向图和无向图分别实现
4）要求用邻接表。邻接矩阵多种结构存储实现

Answer 1

#include<iostream>
using namespace std;
#define MAX_VERTEX_NUM 20
bool visited[MAX_VERTEX_NUM];
struct Graph //无向图
{
char vex[MAX_VERTEX_NUM];
int vexnum,arcnum;
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//1表示相邻，0表示不相邻
};
struct QNode
{
int data;
QNode *next;
};
struct LinkQueue
{
QNode *front;
QNode *rear;
};
int (*VisitFunc)(Graph G,int v);
int LocateVex(Graph G,char v) //返回顶点所在位置
{
int i;
for(i=0;i<G.vexnum;i++)
if(v==G.vex [i]) return i;
return 0;
}
int CreateGraph(Graph &G) //创建无向图
{
cout<<"输入顶点数和边数："<<endl;
cin>>G.vexnum >>G.arcnum ;
int i;
cout<<"输入顶点字符"<<endl;
for(i=0;i<G.vexnum ;i++)
{
cin>>G.vex[i];
}
int j;
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arc[i][j]=0;
char v1,v2;
int k;
cout<<"输入相邻的两顶点"<<endl;
for(k=0;k<G.arcnum;k++)
{
cin>>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arc[i][j]=1;
G.arc[j][i]=1;
}
return 0;
}
int Visit(Graph G,int v)//访问顶点
{
cout<<G.vex[v]<<" ";
return 1;
}
int FirstAdjVex(Graph G,int v) //v的第一个邻接点
{
int j;
for(j=v+1;j<G.vexnum;j++)
{
if(G.arc[v][j]==1) return j;
}
return 0;
}
int NextAdjVex(Graph G,int v,int w)//v的下一个邻接点
{
int j;
for(j=w+1;j<G.vexnum ;j++)
{
if(G.arc[v][j]==1) return j;
}
return 0;
}
void DFS(Graph G,int v)
{
visited[v]=true;
VisitFunc(G,v);
int w;
for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))
if(!visited[w]) DFS(G,w);
}

void DFSTraverse(Graph G,int(*Visit)(Graph G,int v))//深度优先搜索
{
VisitFunc=Visit;
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=false;
for(v=0;v<G.vexnum;v++)
{
if(!visited[v]) DFS(G,v);
}
}
int InitQueue(LinkQueue &Q) //初始化队列
{
Q.front =Q.rear=new QNode;
if(!Q.front)return 0;
return 1;
}
int EnQueue(LinkQueue &Q,int v)//入队列
{
QNode *p=new QNode;
if(!p) return 0;
p->data =v;
p->next =NULL;
Q.rear->next =p;
Q.rear=p;
return 1;
}
int DeQueue(LinkQueue &Q,int &v)//出队列
{
if(Q.front ==Q.rear ) return 0;
QNode *p=Q.front ->next ;
v=p->data ;
Q.front ->next =p->next ;
if(Q.rear ==p)Q.rear =Q.front;
delete p;
return 1;
}
bool QueueEmpty(LinkQueue Q)//队列是否为空
{
if(Q.front ==Q.rear ) return true;
return false;
}

void BFSTraverse(Graph G,int (*Visit)(Graph G,int v))//广度优先搜索
{
int v;
int w,u;
for(v=0;v<G.vexnum ;v++) visited[v]=false;
LinkQueue Q;
InitQueue(Q);
for(v=0;v<G.vexnum;v++)
if(!visited[v]){
visited[v]=true;
Visit(G,v);
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
{
if(!visited[w])
{
visited[w]=true;
Visit(G,w);
EnQueue(Q,w);
}
}
}
}
}

int main()
{
Graph G;
CreateGraph(G);
/*
for(int i=0;i<G.vexnum ;i++)
{
for(int j=0;j<G.vexnum ;j++)
cout<<G.arc [i][j]<<" ";
cout<<endl;
}
*/
cout<<"深度优先搜索\n";
DFSTraverse(G,Visit);
cout<<"\n广度优先搜索\n";
BFSTraverse(G,Visit);
return 0;
}

Answer 2

邮箱拿来。给你发

追问

517544244@qq.com

追答

已发