邻接表表示图DFS与BFS

#include<iostream>
#define MAX_VERTEX_NUM 50
using namespace std;
typedef char VerType;
typedef struct ArcNode
//定义弧结点所在位置，
{
int adj;
int info;
ArcNode *next;
}ArcNode;
typedef struct VerNode
//定义顶点(顶点数据，顶点所指向第一条弧的指针)
{
VerType data;
ArcNode *first;
}VerNode;
typedef struct AdjList
//图的定义
{
VerNode VerNodes[MAX_VERTEX_NUM]; //顶点集
int verNum,arcNum;
//顶点数，弧数
}AdjList;
typedef struct Queue
//FIFO队列
{
int Item[MAX_VERTEX_NUM];
int front,rear;
}Queue;
int visited[MAX_VERTEX_NUM];
//顶点访问标志数组
//定位某一结点的位置,找不到返回0
int LocateGraph(AdjList *g,char data)
{
for(int i=1;i<=g->verNum;i++)
{
if(g->VerNodes[i].data==data)
return i;
}
return 0;
}
//初始化队列
void InitQueue(Queue *Q)
{
for(int i=1;i<=MAX_VERTEX_NUM;i++)
{
Q->Item[i]=0;
}
Q->front=Q->rear=1;
}
//创建图的邻接表
void CreateAdjList(AdjList *g)
{
int s,d,weigth;
char sChar,dChar;
ArcNode *q=NULL;
cout<<"输入图的顶点数,弧数n";
cin>>g->verNum>>g->arcNum;
cout<<"输入每个顶点的信息n";
//初始化顶点
for(int i=1;i<=g->verNum;i++)
{
cin>>g->VerNodes[i].data;
g->VerNodes[i].first=NULL;
}
//初始化弧
for(i=1;i<=g->arcNum;i++)
{
cout<<"输入第"<<i<<"条弧的起始,目的,弧的权值"<<endl;
cin>>sChar>>dChar>>weigth;
s=LocateGraph(g,sChar);
d=LocateGraph(g,dChar);
//定位该顶点的位置
q=(ArcNode *)malloc(sizeof(ArcNode));
q->adj=d;q->info=weigth;
q->next=g->VerNodes[s].first;
g->VerNodes[s].first=q;
}
}
//
void InitVisited(AdjList *g)
{
for(int i=1;i<=g->verNum;i++)
{
visited[i]=0;
}
}
//访问顶点值
void visit(AdjList *g,int v)
{
cout<<g->VerNodes[v].data<<endl;
}
//深度遍历图
void DFSTransfer(AdjList *g,int v)
{
visit(g,v);visited[v]=1;
ArcNode *q=NULL;
q=g->VerNodes[v].first;
while(q!=NULL)
{
if(!visited[q->adj])
{
DFSTransfer(g,q->adj);
q=q->next;
}
}
}
//广度遍历v顶点
void BFS(AdjList *g,int v)
{
ArcNode *q=NULL;
Queue *Q=(Queue *)malloc(sizeof(Queue));
InitQueue(Q);
Q->Item[Q->rear]=v;visit(g,v);visited[v]=1;
Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;
while(Q->front!=Q->rear)
{
v=Q->Item[Q->front];
Q->front=(Q->front+1)%MAX_VERTEX_NUM;
q=g->VerNodes[v].first;
while(q!=NULL)
{
if(!visited[q->adj])
{
visit(g,q->adj);
visited[q->adj]=1;
Q->Item[Q->rear]=q->adj;
Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;
q=q->next;
}
}
}
}
//广度遍历图
void BFSTransfer(AdjList *g)
{
InitVisited(g);
for(int i=1;i<=g->verNum;i++)
{
if(!visited[i])
{
BFS(g,i);
}
}
cout<<endl;
}
int main()
{
AdjList *g=(AdjList*)malloc(sizeof(AdjList));
CreateAdjList(g);
cout<<"---------------------广度优先搜索----------------------"<<endl;
BFSTransfer(g);
cout<<"---------------------深度优先搜索----------------------"<<endl;
InitVisited(g);
DFSTransfer(g,1);
return 0;
}

最后

以上就是动人飞机为你收集整理的邻接表表示图DFS与BFS的全部内容，希望文章能够帮你解决邻接表表示图DFS与BFS所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。