图的操作------建图，DFS,BFS遍历图

83 阅读 0 评论 55 点赞

我是靠谱客的博主妩媚大米，最近开发中收集的这篇文章主要介绍图的操作------建图，DFS,BFS遍历图，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

图的基本操作——建图，DFS,BFS遍历图
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照"{ v1 v2 … vk }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
思路：1.用什么存储图呢？邻接矩阵or邻接表，在这道题中有一个要求“总是从编号最小的顶点出发，按编号递增的顺序访问邻接点”，邻接表是按边的输入顺序插入的，也就是编号无序，而矩阵存储是从0开始，依次递增，所以这里选择用邻接矩阵
2.接下来书写代码
（1）头文件

#include<stdio.h>

（2）存储结构

typedef struct ENode{
vertex V1,V2;
}*Edge;
typedef struct GNode{
int Nv;
int Ne;
int G[MaxSize][MaxSize];
}*MGraph;

（3）主函数（我的习惯是先写主函数形成一个思路，在根据主函数所需要的的函数去编写

int main(){
int N,E;
MGraph Graph;
scanf("%d%d",&N,&E); //输入点和边的个数
Graph=InitGraph(N);
//初始化图
Graph=CreateGraph(Graph,E);//构造图
total_DFS(Graph); //DFS遍历
total_BFS(Graph);//BFS遍历
return 0;
}

（4）初始化图

MGraph InitGraph(int N){
MGraph Graph;
Graph=(MGraph)malloc(sizeof(struct GNode));
Graph->Nv=N;
//点个数
Graph->Ne=0;
//边个数初始化为0
int V,W;
for(V=0;V<Graph->Nv;V++)
for(W=0;W<Graph->Nv;W++)
Graph->G[V][W]=0;
for(V=0;V<Graph->Nv;V++){
Visited_DFS[V]=0;
//在前面定义
Visited_BFS[V]=0;
//没有访问过
}
return Graph;
}

插入边

void InsertEdge(MGraph Graph,Edge E){
Graph->G[E->V1][E->V2]=1;
Graph->G[E->V2][E->V1]=1;
}

构造图

MGraph CreateGraph(MGraph Graph,int Ne){
Graph->Ne=Ne;
Edge E;
if(Graph->Ne!=0){
E=(Edge)malloc(sizeof(struct ENode));
for(int i=0;i<Graph->Ne;i++){
scanf("%d %d",&E->V1,&E->V2);
InsertEdge(Graph,E);
}
}
return Graph;
}

DFS遍历

void DFS(MGraph Graph,vertex V){
printf(" %d",V);
Visited_DFS[V]=1;
vertex W;
for(W=0;W<Graph->Nv;W++)
if(!Visited_DFS[W]&&Graph->G[V][W]==1)
DFS(Graph,W);
}
void total_DFS(MGraph Graph){
vertex V;
for(V=0;V<Graph->Nv;V++){
if(Visited_DFS[V]==0)
{ printf("{");
DFS(Graph,V);
printf(" }");
printf("n");}
}
}

BFS遍历

void BFS(MGraph Graph,vertex V){
Queue Q;
Q=InitQ();
AddQ(Q,V);
Visited_BFS[V]=1;
printf(" %d",V);
vertex W;
while(!IsEmpty(Q)) {
V=DeleteQ(Q);
for(W=0;W<Graph->Nv;W++){
if(!Visited_BFS[W]&&Graph->G[V][W]==1){
printf(" %d",W);
AddQ(Q,W);
Visited_BFS[W]=1;
}
}
}
}

我们这里需要进行建队列，出队，入队的操作
队列类型定义

typedef struct QNode{
int Data[10];
int front;
int rear;
}*Queue;

初始化

Queue InitQ(){
Queue Q;
Q=(Queue)malloc(sizeof(struct QNode));
Q->front=Q->rear=0;
return Q;
}
//判断队列是否为空
int IsEmpty(Queue Q){
return Q->front==Q->rear;
}

入队

void AddQ(Queue Q,vertex V){
if((Q->rear+1)%MaxSize!=Q->front)
{
Q->rear=(Q->rear+1)%MaxSize;
Q->Data[Q->rear]=V;
}
}

出队

int DeleteQ(Queue Q){
if(Q->front==Q->rear) return -1;
else {
Q->front=(Q->front+1)%MaxSize;
return Q->Data[Q->front];
}
}

整体代码

#include<stdio.h>
#include<stdlib.h>
typedef int vertex;
#define MaxSize 10
int Visited_DFS[MaxSize];
int Visited_BFS[MaxSize];
typedef struct ENode{
vertex V1,V2;
}*Edge;
typedef struct GNode{
int Nv;
int Ne;
int G[MaxSize][MaxSize];
}*MGraph;
typedef struct QNode{
int Data[10];
int front;
int rear;
}*Queue;
//队列
Queue InitQ(){
Queue Q;
Q=(Queue)malloc(sizeof(struct QNode));
Q->front=Q->rear=0;
return Q;
}
int IsEmpty(Queue Q){
return Q->front==Q->rear;
}
void AddQ(Queue Q,vertex V){
if((Q->rear+1)%MaxSize!=Q->front)
{
Q->rear=(Q->rear+1)%MaxSize;
Q->Data[Q->rear]=V;
}
}
int DeleteQ(Queue Q){
if(Q->front==Q->rear) return -1;
else {
Q->front=(Q->front+1)%MaxSize;
return Q->Data[Q->front];
}
}
MGraph InitGraph(int N){
MGraph Graph;
Graph=(MGraph)malloc(sizeof(struct GNode));
Graph->Nv=N;
Graph->Ne=0;
int V,W;
for(V=0;V<Graph->Nv;V++)
for(W=0;W<Graph->Nv;W++)
Graph->G[V][W]=0;
for(V=0;V<Graph->Nv;V++){
Visited_DFS[V]=0;
Visited_BFS[V]=0;
}
return Graph;
}
void InsertEdge(MGraph Graph,Edge E){
Graph->G[E->V1][E->V2]=1;
Graph->G[E->V2][E->V1]=1;
}
MGraph CreateGraph(MGraph Graph,int Ne){
Graph->Ne=Ne;
Edge E;
if(Graph->Ne!=0){
E=(Edge)malloc(sizeof(struct ENode));
for(int i=0;i<Graph->Ne;i++){
scanf("%d %d",&E->V1,&E->V2);
InsertEdge(Graph,E);
}
}
return Graph;
}
void DFS(MGraph Graph,vertex V){
printf(" %d",V);
Visited_DFS[V]=1;
vertex W;
for(W=0;W<Graph->Nv;W++)
if(!Visited_DFS[W]&&Graph->G[V][W]==1)
DFS(Graph,W);
}
void total_DFS(MGraph Graph){
vertex V;
for(V=0;V<Graph->Nv;V++){
if(Visited_DFS[V]==0)
{ printf("{");
DFS(Graph,V);
printf(" }");
printf("n");}
}
}
void BFS(MGraph Graph,vertex V){
Queue Q;
Q=InitQ();
AddQ(Q,V);
Visited_BFS[V]=1;
printf(" %d",V);
vertex W;
while(!IsEmpty(Q)) {
V=DeleteQ(Q);
for(W=0;W<Graph->Nv;W++){
if(!Visited_BFS[W]&&Graph->G[V][W]==1){
printf(" %d",W);
AddQ(Q,W);
Visited_BFS[W]=1;
}
}
}
}
void total_BFS(MGraph Graph){
vertex V;
for(V=0;V<Graph->Nv;V++){
if(Visited_BFS[V]==0)
{ printf("{");
BFS(Graph,V);
printf(" }");
printf("n");}
}
}
int main(){
int N,E;
MGraph Graph;
scanf("%d%d",&N,&E);
Graph=InitGraph(N);
Graph=CreateGraph(Graph,E);
total_DFS(Graph);
total_BFS(Graph);
return 0;
}