[数据结构]图基于邻接矩阵的BFS与DFS的C语言简单实现

80 阅读 0 评论 53 点赞

我是靠谱客的博主受伤蜜蜂，最近开发中收集的这篇文章主要介绍[数据结构]图基于邻接矩阵的BFS与DFS的C语言简单实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Github:(https://github.com/FlameCharmander/DataStructure)

上次给大家看了一下图的邻接矩阵的存储。接下来来看下图的广度优先搜索和深度优先搜索。

为了更好的展示BFS和DFS，我把上次的图改了一个边，改成上图那样。
好了，贴代码
由于我们的图广度遍历时需要借助一个队列来实现
所以我们需要用到一个之前实现的队列
把下面这个代码写成queue.c，因为我们图的源文件需要对它导入

#define MAXSIZE 100
#define ElemType char
#define BOOL int
#define TRUE 1
#define FALSE 0
typedef struct{
ElemType data[MAXSIZE];
int front, rear;
}Queue;
static void InitQueue(Queue *queue);
//初始化队列
static BOOL IsEmpty(Queue *queue); //判断是否为空
static void EnQueue(Queue *queue, ElemType x); //入队
static void DeQueue(Queue *queue, ElemType *x);
//出队
void InitQueue(Queue *queue){
queue->front = 0;
queue->rear = 0;
}
void EnQueue(Queue *queue, ElemType e){
queue->data[queue->rear] = e;
queue->rear = (queue->rear + 1) % MAXSIZE;
}
void DeQueue(Queue *queue, ElemType *e){
*e = queue->data[queue->front];
queue->front = (queue->front + 1) % MAXSIZE;
}
BOOL IsEmpty(Queue *queue){
if (queue->front == queue->rear) {
return TRUE;
} else {
return FALSE;
}
}

你可以拿上面的代码跟之前的代码做个比较。其实就是声明函数的那个部分加了static，加这个可以让别的源文件访问，然后main函数去掉了而已。
然后下面是图的代码。

#include <stdio.h>
#include <stdlib.h>
#define INFINTE 65535
#define MAXSIZE 100
#include "queue.c"
typedef char VertexType;
//顶点类型应由用户定义
typedef int EdgeType;
//边上的权值类型应由用户定义
typedef struct graph{
VertexType vexs[MAXSIZE];
//顶点表
EdgeType
arc[MAXSIZE][MAXSIZE];
//邻接矩阵
int numNodes, numEdges;
}Graph;
int visited[200];
void CreateGraph(Graph* graph); //创建图
VertexType* FirstAdjVex(Graph graph, VertexType data);
//获取第一邻接点
VertexType* NextAdjVex(Graph graph, VertexType data, VertexType adj);
//获取下一邻接点
void DFSTraversal(Graph graph); //深度优先遍历
void BFSTraversal(Graph graph); //广度优先遍历
void DFS(Graph graph, VertexType data); //深度优先搜索
void BFS(Graph graph, VertexType data); //广度优先搜索
int main(){
int i, j;
Graph graph;
CreateGraph(&graph);
//打印邻接矩阵
for (i = 0; i < graph.numNodes; ++i){
for (j = 0; j < graph.numNodes; ++j){
printf("%d ", graph.arc[i][j]);
}
printf("n");
}
VertexType* adj = FirstAdjVex(graph, 'A');
VertexType x = *adj;
printf("%c ", x);
adj = NextAdjVex(graph, 'A', x);
x = *adj;
printf("%c ", x);
x = *adj;
adj = FirstAdjVex(graph, 'D');
printf("%cn", *adj);
for (i = 0; i < 200; ++i){
visited[i] = 0;
}
BFSTraversal(graph);
printf("n");
for (i = 0; i < 200; ++i){
//访问数组置空
visited[i] = 0;
}
DFSTraversal(graph);
return 0;
}
void CreateGraph(Graph* graph){
int i, j;
//先把图的邻接矩阵置为0(0表示没边，1表示有边)
for (i = 0; i < graph->numNodes; ++i){
for (j = 0; j < graph->numNodes; ++j){
graph->arc[i][j] = 0;
}
}
//printf("请输入顶点数, 边数：");
//scanf("%d %d", &graph->numNodes, &graph->numEdges);
//getchar();
graph->numNodes = 6;
graph->numEdges = 6;
/*
for (i = 0; i < graph->numNodes; ++i){
printf("请输入顶点：");
scanf("%c", &graph->vexs[i]);
getchar();
//消除空白符
}
*/
graph->vexs[0] = 'A';
graph->vexs[1] = 'B';
graph->vexs[2] = 'C';
graph->vexs[3] = 'D';
graph->vexs[4] = 'E';
graph->vexs[5] = 'F';
VertexType start, end;
/*
for (i = 0; i < graph->numEdges; ++i){
printf("请输入起点， 终点：");
scanf("%c %c", &start, &end);
getchar();
//消除空白符
int startIndex, endIndex;
for (j = 0; j < graph->numNodes; ++j){
//找到起始点,终点
if (start == graph->vexs[j]){
startIndex = j;
}
if (end == graph->vexs[j]){
endIndex = j;
}
}
graph->arc[startIndex][endIndex] = 1;
//如果是无向图，需要双向保存
graph->arc[endIndex][startIndex] = 1;
}
*/
graph->arc[0][2] = 1;
graph->arc[0][3] = 1;
graph->arc[3][1] = 1;
graph->arc[2][4] = 1;
graph->arc[3][5] = 1;
graph->arc[4][5] = 1;
//如果是无向图，需要保存两个边
/*
graph->arc[2][0] = 1;
graph->arc[3][0] = 1;
graph->arc[1][3] = 1;
graph->arc[4][2] = 1;
graph->arc[5][3] = 1;
graph->arc[5][4] = 1;
*/
}
VertexType* FirstAdjVex(Graph graph, VertexType vex){
//先找到data这个结点
int i, j;
for (i = 0; i < graph.numNodes; ++i){
if (graph.vexs[i] == vex){
for (j = 0; j < graph.numNodes; ++j){
if (graph.arc[i][j] == 1){
//找到第一个邻接点
return &(graph.vexs[j]);
}
}
}
}
return NULL;
//这步说明没找到
}
VertexType* NextAdjVex(Graph graph, VertexType vex, VertexType adj){
int vexIndex, adjIndex, i;
for (i = 0; i < graph.numNodes; ++i){
if (graph.vexs[i] == vex){
vexIndex = i;
}
if (graph.vexs[i] == adj){
adjIndex = i;
}
}
for (i = adjIndex + 1; i < graph.numNodes; ++i){
//从当前邻接点的后面寻找
if (graph.arc[vexIndex][i] == 1){
return &(graph.vexs[i]);
}
}
return NULL;
//这步说明没找到
}
/* 深度优先遍历 */
void DFSTraversal(Graph graph){
int i;
for (i = 0; i < graph.numNodes; ++i){
if (visited[graph.vexs[i]] != 1) {
DFS(graph, graph.vexs[i]);
}
}
}
/* 广度优先遍历 */
void BFSTraversal(Graph graph){
int i;
for (i = 0; i < graph.numNodes; ++i){
if (visited[graph.vexs[i]] != 1) {
DFS(graph, graph.vexs[i]);
}
}
}
/*
广度优先搜索
*/
void BFS(Graph graph, VertexType vetex){
Queue queue;
InitQueue(&queue);
EnQueue(&queue, vetex);
VertexType adj;
VertexType *p;
visited[vetex] = 1;
while (!IsEmpty(&queue)){
DeQueue(&queue, &vetex);
printf("%c ", vetex);
for (p = FirstAdjVex(graph, vetex); p != NULL; p=NextAdjVex(graph, vetex, adj)){
adj = *p; //应该可以写成*p，但是不行
if (visited[adj] != 1){
EnQueue(&queue, adj);
visited[adj] = 1;
}
}
}
}
/*
深度优先搜索
*/
void DFS(Graph graph, VertexType vex){
visited[vex] = 1;
printf("%c ", vex);
VertexType *p;
VertexType x;
for (p = FirstAdjVex(graph, vex); p != NULL; p=NextAdjVex(graph, vex, x)){
x = *p;
if (visited[x] != 1){
//没访问过
DFS(graph, x);
}
}
}