目录

前言

已完成内容

图深度优先遍历实现

01-开发环境

02-文件布局

03-代码

01-主函数

02-头文件

03-AdjMatrixFunction.cpp

04-DFS.cpp

结语

前言

        此专栏包含408考研数据结构全部内容，除其中使用到C++引用外，全为C语言代码。使用C++引用主要是为了简化指针的使用，避免二重指针的出现。

已完成内容

[数据结构]：01-顺序表（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：02-单链表（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：03-栈（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：04-循环队列（数组）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：05-循环队列（链表）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：06-队列（链表带头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：07-二叉树（无头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：08-顺序查找（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：09-二分查找（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：10-二叉排序树（无头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：11-冒泡排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：12-快速排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：13-插入排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：14-选择排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：15-堆排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：16-归并排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：17-双链表（带头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：18-链栈（不带头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：19-串KMP模式匹配（数组）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：20-线索二叉树（无头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：21-并查集（数组）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：22-图（邻接矩阵）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：23-图（邻接表）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：24-图广度优先遍历（邻接矩阵）（C语言实现）_Chandni.的博客-CSDN博客

图深度优先遍历实现

01-开发环境

        语言：C/C++14

        编译器：MinGW64

        集成开发环境：CLion2022.1.3

02-文件布局

        请在CLion集成开发环境中创建C++可执行程序，否则无法运行，原因上面已解释。

                        ​​​​​                 

03-代码

01-主函数

        用于测试。

// 默认为无向图，若为有向图或网，请适当修改
#include "./Head/AdjMatrix.h"
#include "./Source/AdjMatrixFunction.cpp"
#include "./Source/DFS.cpp"int main() {// 初始化AdjMGraph Graph;InitGraph(Graph);CreateGraph(Graph);PrintGraph(Graph);printf("VertexNum = %d,EdgeNum = %d\\n", Graph.VexNum, Graph.EdgeNum);printf("-----------------------------------\\n");// 深度优先遍历//   0  1  4  5  2  6  3  7
//    DFSTraverse(Graph);// 删除0号结点插入8号结点DeleteVertex(Graph, 0);InsertVertex(Graph, 8);AddEdge(Graph, 8, 2);AddEdge(Graph, 4, 6);// 深度优先遍历//   8  2  3  6  4  5  1  7DFSTraverse(Graph);return 0;
}

02-头文件

        用于存储结构体和常量等。

//
// Created by 24955 on 2023-04-02.
// 默认为无向图，若为有向图或网，请适当修改
//#ifndef INC_01_ADJACENTMATRIX_ADJMATRIX_H
#define INC_01_ADJACENTMATRIX_ADJMATRIX_H
// 头文件
#include <stdio.h>
#include <stdlib.h>// 常量
#define MAXSIZE 8
typedef int VertexType;
typedef int EdgeType;// 结构体-邻接矩阵
typedef struct {VertexType Vex[MAXSIZE];// 可采用压缩存储EdgeType Edge[MAXSIZE][MAXSIZE];int VexNum, EdgeNum;
} AdjMGraph;
#endif //INC_01_ADJACENTMATRIX_ADJMATRIX_H

03-AdjMatrixFunction.cpp

        用于存储邻接矩阵的基本操作。

//
// Created by 24955 on 2023-04-02.
// 默认为无向图，若为有向图或网，请适当修改
//
// 初始化图
void InitGraph(AdjMGraph &Graph) {// 初始化顶点for (int i = 0; i < MAXSIZE; i++) {Graph.Vex[i] = -1;}// 初始化边for (int i = 0; i < MAXSIZE; i++) {for (int j = 0; j < MAXSIZE; j++) {Graph.Edge[i][j] = 0;}}Graph.VexNum = 0;Graph.EdgeNum = 0;
}// 输出邻接矩阵
void PrintGraph(AdjMGraph Graph) {for (int i = 0; i < MAXSIZE; i++) {printf("%2d\\t", Graph.Vex[i]);for (int j = 0; j < MAXSIZE; j++) {printf("%2d", Graph.Edge[i][j]);}printf("\\n");}
}// 获取元素下标
int GetIndex(AdjMGraph Graph, VertexType x) {/  1. 获取元素真实下标*/int xIndex = -1;for (int i = 0; i < MAXSIZE; i++) {if (Graph.Vex[i] == x) {xIndex = i;break;}}return xIndex;
}// 插入顶点x
void InsertVertex(AdjMGraph &Graph, VertexType x) {/  1. 插入，顶点个数+1*/if (Graph.VexNum == MAXSIZE) {return;}for (int i = 0; i < MAXSIZE; i++) {if (Graph.Vex[i] == -1) {Graph.Vex[i] = x;break;}}Graph.VexNum++;
}// 删除顶点x
void DeleteVertex(AdjMGraph &Graph, VertexType x) {/  1. 清除顶点，并修改顶点个数*  2. 清除边，并修改边个数*/// 清除顶点,将其值设为-1表示该顶点为空int xIndex = GetIndex(Graph, x);if (xIndex == -1) {return;}Graph.Vex[xIndex] = -1;Graph.VexNum--;// 清除边for (int i = 0; i < MAXSIZE; i++) {if (Graph.Edge[xIndex][i]) {Graph.EdgeNum--;Graph.Edge[xIndex][i] = 0;Graph.Edge[i][xIndex] = 0;}}
}// 添加边
void AddEdge(AdjMGraph &Graph, VertexType x, VertexType y) {/  1. 获取顶点值实际下标*  2. 插入边*/int xIndex = GetIndex(Graph, x);int yIndex = GetIndex(Graph, y);if (xIndex == -1 || yIndex == -1) {return;}// 添加边Graph.Edge[xIndex][yIndex] = 1;Graph.Edge[yIndex][xIndex] = 1;Graph.EdgeNum++;
}// 删除边
void RemoveEdge(AdjMGraph &Graph, VertexType x, VertexType y) {/  1. 获取顶点值实际下标*  2. 删除边*/int xIndex = GetIndex(Graph, x);int yIndex = GetIndex(Graph, y);if (xIndex == -1 || yIndex == -1) {return;}// 删除边Graph.Edge[xIndex][yIndex] = 0;Graph.Edge[yIndex][xIndex] = 0;Graph.EdgeNum--;
}// 寻找图中顶点x的第一个邻接点
int FirstNeighbor(AdjMGraph Graph, VertexType x) {/  1. 寻找第一个不为0的值，并返回顶点值*/int xIndex = GetIndex(Graph, x);if (xIndex == -1) {return -1;}for (int i = 0; i < MAXSIZE; i++) {if (Graph.Edge[xIndex][i]) {return Graph.Vex[i];}}return -1;
}// 图的下一个邻接点-除y以外的下一个邻接点顶点号
int NextNeighbor(AdjMGraph Graph, VertexType x, VertexType y) {/  1. 寻找y之后第一个不为0的值，并返回顶点值*/int xIndex = GetIndex(Graph, x);int yIndex = GetIndex(Graph, y);if (xIndex == -1 || yIndex == -1) {return -1;}// 寻找y之后的下一个邻接点for (int i = yIndex + 1; i < MAXSIZE; i++) {if (Graph.Edge[xIndex][i]) {return Graph.Vex[i];}}return -1;
}// 创建图 - 主要方便测试，并非图的正确创建方式，应根据具体情况具体分析
void CreateGraph(AdjMGraph &Graph) {Graph.VexNum = 8;for (int i = 0; i < Graph.VexNum; i++) {Graph.Vex[i] = i;}// 无向图AddEdge(Graph, 0, 1);AddEdge(Graph, 0, 4);AddEdge(Graph, 1, 5);AddEdge(Graph, 2, 5);AddEdge(Graph, 2, 3);AddEdge(Graph, 2, 6);AddEdge(Graph, 5, 6);AddEdge(Graph, 3, 6);AddEdge(Graph, 3, 7);AddEdge(Graph, 6, 7);Graph.EdgeNum = 10;
}

04-DFS.cpp

        用于存储DFS函数。

//
// Created by 24955 on 2023-04-06.
// 默认为无向图，若为有向图或网，请适当修改
//
// 访问函数
void visit(AdjMGraph Graph, int x) {printf("%3d", Graph.Vex[x]);
}// 连通图深度优先遍历
void DFS(AdjMGraph Graph, int x, bool *visited) {/ 1. 类似树的前序遍历*/int xIndex = GetIndex(Graph, x);visit(Graph, xIndex);visited[xIndex] = true;for (int w = FirstNeighbor(Graph, x); w != -1; w = NextNeighbor(Graph, x, w)) {int wIndex = GetIndex(Graph, w);// 若当前结点未被访问，访问并入队if (!visited[wIndex]) {DFS(Graph, w, visited);}}
}// 深度优先遍历
void DFSTraverse(AdjMGraph Graph) {/  1. 设置结点是否已访问*  2. 访问多个连通子图*/bool visited[MAXSIZE];for (int i = 0; i < MAXSIZE; i++) {visited[i] = false;}for (int i = 0; i < MAXSIZE; i++) {// 数组所存结点值和数组下标未必对应if (!visited[i] && Graph.Vex[i] != -1) {DFS(Graph, Graph.Vex[i], visited);}}
}

结语

        此博客主要用于408考研数据结构C语言实现记录，内有不足，可留言，可讨论。