无向图遍历-完整代码（基于邻接矩阵|邻接表）
# 图遍历完整代码-无向（邻接矩阵和邻接表）## 执行结果
!(https://gitee.com/gylq/cloudimages/raw/master/img/image-20210613205513948.png)
## 完整代码奉上
```c
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define MaxVertexNum 100 //定义最大顶点数
//=========定义标志向量，为全局变量=======
typedef enum {FALSE,TRUE} Boolean;
Boolean visited;
//*********************基于邻接矩阵图遍历*********************
typedef struct
{
char vexs;//顶点表
int edges; //邻接矩阵，就是列和行
int n,e; //图中的顶点数n和边数e
}MGraph; //Adjacency Matrix(邻接矩阵)表示的图的类型
//=========建立无向邻接矩阵========
void CreateMGraph(MGraph *G)
{
int i,j,k;
char a;
cout<<"(输入顶点和边：)input VertexNum(n) and EdgesNum(e):";
cin>>G->n>>G->e; //输入顶点数和边数
cout<<"Input Vertx string : ";
for(i=0; i<G->n; i++)
{
cin>>a;
G->vexs=a; //读入顶点信息，建立定点表
}
for(i=0; i<G->n; i++)
for(j=0; j<G->n; j++)
{
G->edges=0;//初始化邻接矩阵
}
cout<<"Input edges, Create Adjacency Matrix :"<<endl;
for(k=0; k<G->e; k++)
{
cin>>i>>j;//输入边（Vi，Vj）的顶点序号 也就是可达
G->edges=1;
G->edges=1; //若为无向图，矩阵为对称矩阵；若建立有向图可不需此步骤。
}
}
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G, int i)
{
//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0,1矩阵
int j;
cout<<G->vexs;
visited=TRUE;
for(j=0; j<G->n; j++)
{
if(G->edges==1 && ! visited)
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
}
}
void DFS(MGraph *G)
{
int i;
for(i=0; i<G->n; i++)
visited=FALSE; //标志向量初始化
for(i=0; i<G->n; i++)
if(!visited) //Vi未访问过
DFSM(G,i);//以Vi为源点开始DFS搜索
}
//===========BFS：广度优先遍历=======
void BFS(MGraph *G, int k)
{
//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
int i,j,f=0,r=0;
int cq;//定义队列
for(i=0; i<G->n; i++)
visited=FALSE; //标志向量初始化
for(i=0; i<G->n; i++)
cq=-1; //队列初始化
cout<<G->vexs; //访问源点Vk
visited=TRUE;//将已访问标志位TRUE
cq=k; //源点Vk进入队列
while(cq!=-1)//队列非空就执行
{
i=cq;
f=f+1; //Vi出队
for(j=0 ; j<G->n; j++)//依次Vi
{
if(!visited && G->edges==1)//Vj未访问
{
cout<<G->vexs; //访问Vj
visited=TRUE;
r=r+1;
cq=j;//通过访问Vj入队
}
}
}
}
//*********************基于邻接表图遍历*********************
typedef struct node //边表结点
{
int adjvex;//邻接点域
struct node *next; //链域
} EdgeNode;
typedef struct vnode//顶点表结点
{
char vertex; //顶点域
EdgeNode *firstedge; //边表头指针
} VertexNode;
typedef VertexNode AdjList;
typedef struct
{
AdjList adjlist; //邻接表
int n,e; //图中当前顶点数和边数
} ALGraph; //图类型 -Adjacency List 邻接表
//=========建立图的邻接表=======
void CreateALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定义边表结点
cout<<"（输入顶点和边）Input VertexNum(n) and EdgesNum(e): ";
cin>>G->n>>G->e; //读入顶点数和边数
fflush(stdin); //清空内存缓冲
cout<<"(输入顶点信息)Input Vertex string:";
for(i=0; i<G->n; i++)//建立顶点表
{
cin>>a;
G->adjlist.vertex=a; //读入顶点信息
G->adjlist.firstedge=NULL; //边表置为空
}
cout<<"(输入边，创建邻接表)Input edges,Creat Adjacency List"<<endl;
for(k=0; k<G->e; k++) //无向建立边表
{
cin>>i>>j;//读入边（Vi， Vj）的顶点对应序号
s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成边表结点
s->adjvex=j;//邻接点序号为j
s->next=G->adjlist.firstedge;
G->adjlist.firstedge=s; //将新结点*S插入顶点Vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist.firstedge;
G->adjlist.firstedge=s;//将新结点*S插入顶点Vj的边表头部
}
}
//========DFS：深度优先遍历的递归算法======
void DFSM(ALGraph *G, int i)
{
//以Vi为出发点对邻接链表表示的图G进行DFS搜索
EdgeNode *p;
cout<<G->adjlist.vertex;//访问顶点Vi
visited=TRUE;//标记Vi已访问
p=G->adjlist.firstedge; //取Vi边表的头指针
while(p) //依次搜索Vi的邻接点Vj，这里vj=p->adjvex
{
if(! visited) //若Vj尚未被访问
DFSM(G,p->adjvex);//则以Vj为出发点向纵深搜索
p=p->next; //找Vi的下一个邻接点
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0; i<G->n; i++)
visited=FALSE;//标志向量初始化
for(i=0; i<G->n; i++)
if(!visited) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
}
//==========BFS：广度优先遍历=========
void BFS(ALGraph *G, int k)
{
//以Vk为源点对用邻接链表表示的图G进行广度优先搜索
int i,f=0,r=0;
EdgeNode *p;
int cq; //定义FIFO队列
for(i=0; i<G->n; i++)
visited=FALSE; //标志向量初始化
for(i=0; i<=G->n; i++)
cq=-1; //初始化队列
cout<<G->adjlist.vertex; //访问源点Vk
visited=TRUE;
cq=k;//Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq!=-1) //队列非空则执行
{
i=cq;
f=f+1;
p=G->adjlist.firstedge; //取Vi的边表头指针
while(p) //依次搜索Vi的邻接点Vj（令p->adjvex=j）
{
if(!visited) //若Vj未访问过，Vj是指的邻接点
{
cout<<G->adjlist.vertex; //访问Vj
visited=TRUE;
r=r+1;
cq=p->adjvex; //访问过的Vj入队
}
p=p->next;//找Vi的下一个邻接点
}
}//endwhile
}
int main()
{
int a,b;
//基于邻接矩阵遍历图
cout<<"*********************基于邻接矩阵无向图遍历*********************"<<endl;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph));
CreateMGraph(G); //建立邻接矩阵
cout<<"(-基于邻接矩阵-输出深度优先搜索)Print Graph DFS: "<<endl;
DFS(G);
cout<<endl;
cout<<"-基于邻接矩阵-输入从哪个顶点开始遍历: ";
cin>>a;
cout<<"(-基于邻接矩阵-输出广度优先搜索)Print Graph BFS: "<<endl;
BFS(G,a);
cout<<endl;
cout<<endl;
cout<<endl;
//基于邻接表遍历图
cout<<"*********************基于邻接表无向图遍历*********************"<<endl;
ALGraph *A;
A=(ALGraph *)malloc(sizeof(ALGraph));
CreateALGraph(A);
cout<<"(-基于邻接表-输出深度优先搜索)Print Graph DFS: "<<endl;
DFS(G);
cout<<"(-基于邻接表-输出广度优先搜索)Print Graph BFS: "<<endl;
cin>>b;
BFS(G,b);
cout<<endl;
system("pause");
}
``` 邻接矩阵意义不大，时间复杂度相近，但内存占用远大于邻接表 邻接矩阵和邻接表 这种算法贴，确实是很高明的个人展示 很强啊，楼主在哪里呀？
页:
[1]