图的遍历-邻接矩阵实现DFS和BFS，c语言实现

90 阅读 0 评论 60 点赞

我是靠谱客的博主沉静天空，最近开发中收集的这篇文章主要介绍图的遍历-邻接矩阵实现DFS和BFS，c语言实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

首先是我个渣对两种遍历方法的看法

BFS:寻找最优解,比如最短路径.时间复杂度更低，一圈一圈搜索,深度不大的时候比较适用，但是

DFS:不撞南墙不回头,所以相对于BFS 找到的不一定是最优解,但是其对于空间的消耗较少,因为不需要存储临时节点

对于DFS，其实现方法类似于先序遍历，不断递归的调用DFS函数，依次向下搜寻。

首先是图结构体的实现

struct GNode
{
int Nv;//顶点数
int Ne;//边数
int G[MaxSize][MaxSize];
};
typedef PtrToGNod MGraph;//图
typedef struct ENode *PtrToENod;
struct ENode{
Vertex V1,V2;
int Weigth;//权重
};
typedef PtrToENod Edge;//边

图的构建函数

MGraph CreatGraph(int size)//创建一个无边的图
{
MGraph Graph = (MGraph)malloc(sizeof(struct GNode));//给图分配存储空间
Graph->Nv = size;
Graph->Ne = 0;
for (int i = 0; i<Graph->Nv; i++) {
for (int j = 0; j<Graph->Nv; j++) {
Graph->G[i][j] = 0;
}
}
return Graph;
}
void InsertEdge(MGraph G,Edge E)
{
G->G[E->V1][E->V2] = E->Weigth;
//如果是无向图
G->G[E->V2][E->V1] = E->Weigth;
}
MGraph BuildGraph(int Nv)
{
MGraph Graph;
Graph = CreatGraph(Nv);
cout<<"请输入边的个数";
cin>>Graph->Ne;
if (Graph->Ne!=0) {
Edge E = (Edge)malloc(sizeof(struct ENode));
cout<<"依次输入节点1，2和权重"<<endl;
for (int i = 0; i<Graph->Ne; i++) {
cin>>E->V1>>E->V2>>E->Weigth;
InsertEdge(Graph, E);
}
}
return Graph;
}

图建立完后

实现DFS深度优先遍历搜索

void DFS(MGraph G,Vertex V)//深度优先遍历搜索,从V节点开始
{
int W;
/*以V为出发点对周围进行DFS搜索*/
cout<<"正在深度优先遍历第"<<v<<"个节点";
Visited[V] = true;//标记为以访问
for(W = 0;W<G->Nv;W++)
{
if (!Visited[W] && IsEdge(G, V, W)) {
DFS(G,W);
}
}
}

首先声明一个Visited数组，初始化为全false，每当标记一个节点后(即访问后),将标记位置1,表示完成访问,然后访问当前节点的领节点，如果该节点未被访问，依次调用DFS向下进行.

对于所有节点的深度优先遍历,定一个一个函数，完成对所有节点的深度优先遍历，以满足万一有节点与其他节点都不联通的情况

void DFSTraverseM(MGraph G)//深度优先遍历所有节点
{
int i;
for(i = 0;i<G->Nv;i++)
{
Visited[i] = false;
}
for (i=0; i<G->Nv; i++) {//这个语句是对与矩阵中所有元素都进行深度优先遍历搜索
if (!Visited[i])
DFS(G, i);
}
}

以上完成了对所有节点的深度优先遍历

对于BFS，广度优先搜索，类似于树的层次遍历，所以用队列实现是一个不错的方法，但不仅仅只能用队列实现，这里为了方便，我选择了队列实现，首先是构造结构体,并完成相关实现的函数

ypedef struct QNode *Queue;
struct QNode{
int front;
int rear;
int *data;
int maxsize;
};
Queue CreateQueue(int size)//创建队列
{
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->data = (int *)malloc(size*sizeof(int));
Q->front = Q->rear = 0;
Q->maxsize = size;
return Q;
}
bool IsFull(Queue Q)
{
if((Q->rear+1)%Q->maxsize == Q->front)
{
cout<<"队列满";
return true;
}
return false;
}
void AddQ(Queue Q,int x)
{
if (IsFull(Q)){
cout<<"已满";
}
else{
Q->rear = (Q->rear+1)%Q->maxsize;
Q->data[Q->rear] = x;
}
}
bool IsEmpty(Queue Q)
{
return (Q->front == Q->rear);
}
int DeletQueue(Queue Q)
{
int x;
if (IsEmpty(Q)) {
cout<<"队列空";
return -1;
}
else
{
x = Q->data[Q->front];
Q->front = (Q->front+1)%Q->maxsize;
return x;
}
}

实现队列后，来考虑BFS，广度优先搜索，依次搜索该节点周围所有节点，并置于队列当中，每当队列中的一个元素弹出，依次访问其周边所有节点，其原理近似于树的层次遍历。

void BFM(MGraph G,Vertex V)//广序遍历
{
int i,j;
Queue Q = CreateQueue(MaxSize);
cout<<"正在广度优先遍历第"<<V<<"个节点"<<endl;
Visited[V] = true;
AddQ(Q, V);//将v压入队列
while (!IsEmpty(Q)) {
i = DeletQueue(Q);
for (j = 0; j<G->Nv; j++) {
if (G->G[i][j] !=0 && !Visited[j]) {
cout<<"当前正在广度优先遍历第"<<j<<"个节点"
Visited[j] = true;//将i周围的存在的节点依次标记
AddQ(Q,j);//将j推入队列内 s
}
}
}
}
void BFTraver(MGraph G)
{
int i;
for (i = 0; i<G->Nv; i++) {
Visited[i] = 0;
}
for (i = 0; i<G->Nv; i++) {
if (!Visited[i])
BFM(G, i);
}
}

不难看出，广度优先遍历一层一层搜索，而深度优先遍历不撞南墙不回头，但两种遍历都非常的棒,对于学习数据结构很有帮助

以下是全部代码实现

#include <iostream>
using namespace std;
typedef struct GNode *PtrToGNod;
#define MaxSize 10
#define Vertex int
bool Visited[MaxSize];
struct GNode
{
int Nv;//顶点数
int Ne;//边数
int G[MaxSize][MaxSize];
};
typedef PtrToGNod MGraph;//图
typedef struct ENode *PtrToENod;
struct ENode{
Vertex V1,V2;
int Weigth;//权重
};
typedef PtrToENod Edge;
typedef struct QNode *Queue;
struct QNode{
int front;
int rear;
int *data;
int maxsize;
};
Queue CreateQueue(int size)//创建队列
{
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->data = (int *)malloc(size*sizeof(int));
Q->front = Q->rear = 0;
Q->maxsize = size;
return Q;
}
bool IsFull(Queue Q)
{
if((Q->rear+1)%Q->maxsize == Q->front)
{
cout<<"队列满";
return true;
}
return false;
}
void AddQ(Queue Q,int x)
{
if (IsFull(Q)){
cout<<"已满";
}
else{
Q->rear = (Q->rear+1)%Q->maxsize;
Q->data[Q->rear] = x;
}
}
bool IsEmpty(Queue Q)
{
return (Q->front == Q->rear);
}
int DeletQueue(Queue Q)
{
int x;
if (IsEmpty(Q)) {
cout<<"队列空";
return -1;
}
else
{
x = Q->data[Q->front];
Q->front = (Q->front+1)%Q->maxsize;
return x;
}
}
MGraph CreatGraph(int size)//创建一个无边的图
{
MGraph Graph = (MGraph)malloc(sizeof(struct GNode));//给图分配存储空间
Graph->Nv = size;
Graph->Ne = 0;
for (int i = 0; i<Graph->Nv; i++) {
for (int j = 0; j<Graph->Nv; j++) {
Graph->G[i][j] = 0;
}
}
return Graph;
}
void InsertEdge(MGraph G,Edge E)
{
G->G[E->V1][E->V2] = E->Weigth;
//如果是无向图
G->G[E->V2][E->V1] = E->Weigth;
}
MGraph BuildGraph(int Nv)
{
MGraph Graph;
Graph = CreatGraph(Nv);
cout<<"请输入边的个数";
cin>>Graph->Ne;
if (Graph->Ne!=0) {
Edge E = (Edge)malloc(sizeof(struct ENode));
cout<<"依次输入节点1，2和权重"<<endl;
for (int i = 0; i<Graph->Ne; i++) {
cin>>E->V1>>E->V2>>E->Weigth;
InsertEdge(Graph, E);
}
}
return Graph;
}
void visit(Vertex V)//访问
{
cout<<"正在访问第"<<V<<"个节点"<<endl;
}
bool IsEdge(MGraph G,Vertex V,Vertex W)
{
if(G->G[V][W]!=0 || G->G[W][V]!=0)//无向图
return true;
return false;
}
void DFS(MGraph G,Vertex V)//深度优先遍历搜索,从V节点开始
{
int W;
/*以V为出发点对周围进行DFS搜索*/
cout<<"正在深度优先遍历第"<<V<<"个节点"<<endl;
Visited[V] = true;//标记为以访问
for(W = 0;W<G->Nv;W++)
{
if (!Visited[W] && IsEdge(G, V, W)) {
DFS(G,W);
}
}
}
void DFSTraverseM(MGraph G)//深度优先遍历所有节点
{
int i;
for(i = 0;i<G->Nv;i++)
{
Visited[i] = false;
}
for (i=0; i<G->Nv; i++) {//这个语句是对与矩阵中所有元素都进行深度优先遍历搜索
if (!Visited[i])
DFS(G, i);
}
}
void BFM(MGraph G,Vertex V)//广序遍历
{
int i,j;
Queue Q = CreateQueue(MaxSize);
cout<<"正在广度优先遍历第"<<V<<"个节点"<<endl;
Visited[V] = true;
AddQ(Q, V);//将v压入队列
while (!IsEmpty(Q)) {
i = DeletQueue(Q);
for (j = 0; j<G->Nv; j++) {
if (G->G[i][j] !=0 && !Visited[j]) {
cout<<"正在广度优先遍历第"<<j<<"个节点"<<endl;
Visited[j] = true;//将i周围的存在的节点依次标记
AddQ(Q,j);//将j推入队列内 s
}
}
}
}
void BFTraver(MGraph G)
{
int i;
for (i = 0; i<G->Nv; i++) {
Visited[i] = 0;
}
for (i = 0; i<G->Nv; i++) {
if (!Visited[i])
BFM(G, i);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
int Nv;
cout<<"请输入节点个数";
cin>>Nv;
MGraph Graph=BuildGraph(Nv);
DFSTraverseM(Graph);
cout<<"广度优先遍历"<<endl;
BFTraver(Graph);
return 0;
}