图深度优先搜索广度优先搜索，邻接表

本文主要是介绍图深度优先搜索广度优先搜索，邻接表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <stdafx.h>#include"iostream"#include"malloc.h"using namespace std;#define MaxVertexNum 50        //定义最大顶点数typedef struct node{       //边表结点char adjvex;          //邻接点域struct node *next;    //链域}EdgeNode;typedef struct vnode{     //顶点表结点char vertex;           //顶点域EdgeNode *firstedge; //边表头指针}VertexNode;typedef VertexNode AdjList[MaxVertexNum];       //AdjList是邻接表类型typedef struct {AdjList adjlist;     //邻接表int n,e;             //图中当前顶点数和边数} ALGraph;               //图类型//           建立图的邻接表          void CreatALGraph(ALGraph *G){int i,j,k;char a;EdgeNode *s;        //定义边表结点cout<<"请输入顶点数和边数: ";cin>>i;cin>>j;     //读入顶点数和边数G->n=i;G->e=j;cout<<"请输入顶点编号:";for(i=0;i<G->n;i++)     //建立边表{cin>>a;G->adjlist[i].vertex=a;      //读入顶点信息G->adjlist[i].firstedge=NULL; //边表置为空表}cout<<"请输入由两个顶点构成的边，示例：0 1"<<endl;for(k=0;k<G->e;k++){ //建立边表cin>>i;cin>>j;        //读入边（Vi，Vj）的顶点对序号s=(EdgeNode *)malloc(sizeof(EdgeNode));    //生成边表结点s->adjvex=j;                 //邻接点序号为js->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;     //将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode));s->adjvex=i;                  //邻接点序号为is->next=G->adjlist[j].firstedge;  G->adjlist[j].firstedge=s;      //将新结点*S插入顶点Vj的边表头部}}//定义标志向量为全局变量        typedef enum{FALSE,TRUE} Boolean;Boolean visited[MaxVertexNum];// DFS：深度优先遍历的递归算法      void DFSM(ALGraph *G,int i){                        //以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode *p;cout<<G->adjlist[i].vertex;   //访问顶点Vivisited[i]=TRUE;                    //标记Vi已访问p=G->adjlist[i].firstedge;           //取Vi边表的头指针while(p) {                 //依次搜索Vi的邻接点Vj，这里j=p->adjvexif(! visited[p->adjvex])      //若Vj尚未被访问DFSM(G,p->adjvex);       //则以Vj为出发点向纵深搜索p=p->next;                    //找Vi的下一个邻接点}}void DFS(ALGraph *G){for(int i=0;i<G->n;i++)visited[0]=FALSE;        //标志向量初始化for(int i=0;i<G->n;i++)if(!visited[0])              //Vi未访问过DFSM(G,0);                //以Vi为源点开始DFS搜索}//广度优先遍历       void BFS(ALGraph *G){  int k=0;                       /*以Vk为源点对用邻接链表表示的图G进行广度优先搜索*/int i,f=0,r=0;EdgeNode *p;int cq[MaxVertexNum];         //定义FIFO队列for(i=0;i<G->n;i++)visited[i]=FALSE;             //标志向量初始化for(i=0;i<=G->n;i++)cq[i]=-1;                          //初始化标志向量cout<<G->adjlist[k].vertex; //访问源点Vkvisited[k]=TRUE;cq[r]=k;           //Vk已访问，将其入队。注意，实际上是将其序号入队while(cq[f]!=-1) {   //队列非空则执行i=cq[f]; f=f+1;                //Vi出队p=G->adjlist[i].firstedge;     //取Vi的边表头指针while(p) {                //依次搜索Vi的邻接点Vj（令p->adjvex=j）if(!visited[p->adjvex]) {           //若Vj未访问过cout<<G->adjlist[p->adjvex].vertex;      //访问Vjvisited[p->adjvex]=TRUE;r=r+1; cq[r]=p->adjvex;           //访问过的Vj入队}p=p->next;               //找Vi的下一个邻接点}}                              }      int main(){int i,x;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph));CreatALGraph(G);cout<<"遍历结果与构造边的顺序有关。"<<endl;cout<<"深度优先 "<<endl;DFS(G);cout<<endl;cout<<"广度优先"<<endl;BFS(G);cout<<endl;}

这篇关于图深度优先搜索广度优先搜索，邻接表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---