[C]图遍历完整代码-无向（邻接矩阵和邻接表）
执行结果
完整代码奉上
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define MaxVertexNum 100 //定义最大顶点数
//=========定义标志向量，为全局变量=======
typedef enum {FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//*********************基于邻接矩阵图遍历*********************
typedef struct
{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，就是列和行
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[i]=a; //读入顶点信息，建立定点表
}
for(i=0; i<G->n; i++)
for(j=0; j<G->n; j++)
{
G->edges[i][j]=0; //初始化邻接矩阵
}
cout<<"Input edges, Create Adjacency Matrix :"<<endl;
for(k=0; k<G->e; k++)
{
cin>>i>>j; //输入边（Vi，Vj）的顶点序号 也就是可达
G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图可不需此步骤。
}
}
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G, int i)
{
//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0,1矩阵
int j;
cout<<G->vexs[i];
visited[i]=TRUE;
for(j=0; j<G->n; j++)
{
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
}
}
void DFS(MGraph *G)
{
int i;
for(i=0; i<G->n; i++)
visited[i]=FALSE; //标志向量初始化
for(i=0; i<G->n; i++)
if(!visited[i]) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
}
//===========BFS：广度优先遍历=======
void BFS(MGraph *G, int k)
{
//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列
for(i=0; i<G->n; i++)
visited[i]=FALSE; //标志向量初始化
for(i=0; i<G->n; i++)
cq[i]=-1; //队列初始化
cout<<G->vexs[k]; //访问源点Vk
visited[k]=TRUE; //将已访问标志位TRUE
cq[r]=k; //源点Vk进入队列
while(cq[f]!=-1) //队列非空就执行
{
i=cq[f];
f=f+1; //Vi出队
for(j=0 ; j<G->n; j++) //依次Vi
{
if(!visited[j] && G->edges[i][j]==1) //Vj未访问
{
cout<<G->vexs[j]; //访问Vj
visited[j]=TRUE;
r=r+1;
cq[r]=j; //通过访问Vj入队
}
}
}
}
//*********************基于邻接表图遍历*********************
typedef struct node //边表结点
{
int adjvex; //邻接点域
struct node *next; //链域
} EdgeNode;
typedef struct vnode //顶点表结点
{
char vertex; //顶点域
EdgeNode *firstedge; //边表头指针
} VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
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[i].vertex=a; //读入顶点信息
G->adjlist[i].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[i].firstedge;
G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部
}
}
//========DFS：深度优先遍历的递归算法======
void DFSM(ALGraph *G, int i)
{
//以Vi为出发点对邻接链表表示的图G进行DFS搜索
EdgeNode *p;
cout<<G->adjlist[i].vertex; //访问顶点Vi
visited[i]=TRUE; //标记Vi已访问
p=G->adjlist[i].firstedge; //取Vi边表的头指针
while(p) //依次搜索Vi的邻接点Vj，这里vj=p->adjvex
{
if(! visited[p->adjvex]) //若Vj尚未被访问
DFSM(G,p->adjvex); //则以Vj为出发点向纵深搜索
p=p->next; //找Vi的下一个邻接点
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0; i<G->n; i++)
visited[i]=FALSE; //标志向量初始化
for(i=0; i<G->n; i++)
if(!visited[i]) //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[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; //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq[f]!=-1) //队列非空则执行
{
i=cq[f];
f=f+1;
p=G->adjlist[i].firstedge; //取Vi的边表头指针
while(p) //依次搜索Vi的邻接点Vj（令p->adjvex=j）
{
if(!visited[p->adjvex]) //若Vj未访问过，Vj是指的邻接点
{
cout<<G->adjlist[p->adjvex].vertex; //访问Vj
visited[p->adjvex]=TRUE;
r=r+1;
cq[r]=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");
}
| 
发表于 2021-6-13 20:58
