图的遍历
1403张柯
实验要求：以邻接表存储方式创建一个有向图，并对图进行深度遍历和广度遍历。
#include<iostream>
#define MaxInt 32767
#define MVnum 100
typedef char VerTex;
using namespace std;
typedef struct QNode{ //队列的存储，后面广度遍历会用到
催屎按哪里 int data;
QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
typedef struct Queuefun{ //队列的操作函数
int QueueEmpty(LinkQueue q)
{
ar==q.front)
return 1;
el return 0;
}
void InitQueue(LinkQueue&q)
{
q.ar=new QNode;
q.front->next=NULL;
}
void EnQueue(LinkQueue&q,int e)
{
QueuePtr p;
p=new QNode;
p->data=e;
p->next=ar->next=p;
q.rear=p; }
void DeQueue(LinkQueue&q,int &e)
{
QueuePtr p;
if(q.front==q.rear)return;
p=q.front->next;
e=p->data;
梦幻法宝合成
q.front->next=p->next;
ar==ar=q.front;
delete p;
}
}Queuefun;
Queuefun Q;
typedef struct ArcNode{ //图的存储结构
int adjvex;
ArcNode *nextarc;
int info;
}ArcNode;
typedef struct VNode{
VerTex data;
ArcNode *firstarc;
}VNode,AdjList[MVnum];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef struct funs{
int FirstAdjVex(ALGraph G,int u) //找到某顶点第一个邻接点
{
if(G.vertices[u].firstarc)
return G.vertices[u].firstarc->adjvex;
el return -1;
}
int LocateVex(ALGraph G,char a)
{
int i;
for(i=0;i<G.vexnum;++i)
{
if(G.vertices[i].data==a)
简短的每日工作总结 return i;
}
}
void CreateUDG(ALGraph &G) //创建图
{
ArcNode *p1,*p2;
char v1,v2;
地毯满铺
int i,k,j;
cout<<"分别输入顶点个数，和边的个数:";
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;i++)
{
cout<<"请输入第"<<i<<"个顶点的信息：";
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
for(k=0;k<G.arcnum;++k)
{
char a,b;
cout<<"输入以有向线段连接的两个顶点，如a->b:";
cin>>v1>>a>>b>>v2;
i=LocateVex(G,v1);j=LocateVex(G,v2);
p1=new ArcNode;
p1->adjvex=j;
p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;雨层云
}
}
bool visited[MVnum];
void DFS(ALGraph G,int v) //深度遍历
{
ArcNode *p;int w;
cout<<G.vertices[v].data;
visited[v]=1;
p=G.vertices[v].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(!visited[w])DFS(G,w);
p=p->nextarc;
}
}
void DFSTraver(ALGraph G) //深度遍历对于全部顶点逐一遍历
{
int v;
for(v=0;v<G.vexnum;++v)visited[v]=0;
for(v=0;v<G.vexnum;++v)
if(!visited[v])
DFS(G,v);
}
如何写总结 int NextAdjVex(ALGraph G,int u,int w) //相对于某个邻接点的下个邻接点
{
ArcNode *p;
p=G.vertices[u].firstarc;
if(!p)return -1;
while(p)
{
if(p->adjvex==w&&p->nextarc)
return p->nextarc->adjvex;
el if(p->adjvex==w&&!p->nextarc)
return -1;
el p=p->nextarc;
}
return -1;
}
void BFS(ALGraph G,int v) //广度遍历
{
LinkQueue q;int u,w;
cout<<G.vertices[v].data;visited[v]=1;
Q.InitQueue(q);
Q.EnQueue(q,v);
while(!Q.QueueEmpty(q))
{
Q.DeQueue(q,u);
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
if(!visited[w])
{
cout<<G.vertices[w].data;
visited[w]=1;
Q.EnQueue(q,w);
}
}
}
void BFSTraver(ALGraph G) //对于所有节点为起点逐一遍历
{
int v;
稻草人的读后感 for(v=0;v<G.vexnum;++v)visited[v]=0;
for(v=0;v<G.vexnum;++v)
if(!visited[v])
BFS(G,v);
}
}funs;
funs F;
main()
{
int i;
ALGraph G;int v;
F.CreateUDG(G);
cout<<"该图的深度优先遍历结果为:";
F.DFSTraver(G);
cout<<endl;
cout<<"该图的广度优先遍历结果为:";
F.BFSTraver(G);
cout<<endl;
}
希望能帮到你哦~~~后腰疼。
