最近发现一个不错的项目，Github上数据结构所有算法源码实现：
图的邻接矩阵存储结构定义:
// 图的类型
typedef enum {
DG, // 0-有向图
DN, // 1-有向网(带权值)
UDG, // 2-无向图
UDN // 3-无向网(带权值)
} GraphKind;
// 边的相关附加信息
typedef struct {
// 如果有的话，后续会添加相应的属性
void* v; // 添加一个无意义的变量来占位，如果结构体为空的话，在VC++中会报错
} InfoType;
// 边的类型，每条边上可能有附加信息info
typedef struct ArcCell {
VRType adj; // 顶点关系，在有权图跟无权图中的含义不同
InfoType* info; // 边的附加信息，通常忽略
} ArcCell;
/* 图/网的数组(邻接矩阵)存储表示类型定义 */
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, arcnum; // 图/网的顶点数和弧数
GraphKind kind; // 图的类型标志
} MGraph;完整代码第三部分里，读取文件的测试文件在第四部分。
1.测试方式有两种，手动控制台输入图；直接使用测试文件
手动控制台输入方式：
直接读取文件方式：
2.输出结果展示
完整代码分为两部分：头文件(MGraph.h) 和 c文件(MGraph.c)
头文件：MGraph.h
#include "stdafx.h"
#include <stdio.h>
#include <limits.h> // 提供宏INT_MAX
#include <string.h> // 提供memset、strcmp 原型
#include <stdarg.h> // 提供宏va_list、va_start、va_arg、va_end
#include <ctype.h> // 提供isprint原型
#include <stdlib.h> // 提供malloc、realloc、free、exit原型
/* 状态码 */
#define TRUE 1 // 真/是
#define FALSE 0 // 假/否
#define OK 1 // 通过/成功
#define ERROR 0 // 错误/失败
//系统中已有此状态码定义，要防止冲突
#ifndef OVERFLOW
#define OVERFLOW -2 //堆栈上溢
#endif
//系统中已有此状态码定义，要防止冲突
#ifndef NULL
#define NULL ((void*)0)
#endif
/* 状态码类型 */
typedef int Status;
/* 布尔类型 */
typedef int Boolean;
/* 全局变量*/
extern Boolean debug; // 是否使用debug模式
/* 宏定义 */
#define INFINITE INT_MAX // 最大值，用来表示网中的两个顶点不直接连接
#define MAX_VERTEX_NUM 26 // 最大顶点个数
#pragma region 定义图以及相关方法
// 图的类型
typedef enum {
DG, // 0-有向图
DN, // 1-有向网(带权值)
UDG, // 2-无向图
UDN // 3-无向网(带权值)
} GraphKind;
// 顶点类型
typedef char VertexType;
/*
* 顶点关系类型
*/
typedef int VRType;
// 边的相关附加信息
typedef struct {
// 如果有的话，后续会添加相应的属性
void* v; // 添加一个无意义的变量来占位，如果结构体为空的话，在VC++中会报错
} InfoType;
// 边的类型，每条边上可能有附加信息info
typedef struct ArcCell {
VRType adj; // 顶点关系，在有权图跟无权图中的含义不同
InfoType* info; // 边的附加信息，通常忽略
} ArcCell;
/* 图/网的数组(邻接矩阵)存储表示类型定义 */
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, arcnum; // 图/网的顶点数和弧数
GraphKind kind; // 图的类型标志
} MGraph;
// 边/弧上是否存在附加信息
extern Boolean IncInfo;
/*
* 创建有向图
*/
Status CreateGraph(MGraph* G, char* path[]);
/*
* 构造有向图
*/
static Status CreateDG(MGraph* G);
/*
* 构造有向网
*/
static Status CreateDN(MGraph* G);
/*
* 构造无向图
*/
static Status CreateUDG(MGraph* G);
/*
* 构造无向网
*/
static Status CreateUDN(MGraph* G);
/*
* 录入边的相关附加信息
*/
static void Input(MGraph G, InfoType** info);
/*
* 销毁，邻接矩阵存储的图无需释放内存，只需重置相关遍历即可。
*/
Status DestroyGraph(MGraph* G);
/*
* 查找，返回顶点u在图/网中的位置
*/
int LocateVex(MGraph G, VertexType u);
/*
* 取值，返回索引v处的顶点值
*/
VertexType GetVex(MGraph G, int v);
/*
* 赋值，将顶点v赋值为value
*/
Status PutVex(MGraph* G, VertexType v, VertexType value);
/*
* 首个邻接点，返回顶点v的首个邻接点
*/
int FirstAdjVex(MGraph G, VertexType v);
/*
* 下一个邻接点
* 返回顶点v的(相对于w的)下一个邻接点
*/
int NextAdjVex(MGraph G, VertexType v, VertexType w);
/*
* 插入顶点
* 将指定的顶点v追加到顶点集中，未建立该顶点与其他顶点的关系
*/
Status InsertVex(MGraph* G, VertexType v);
/*
* 删除顶点
*
* 从顶点集中删除指定的顶点v，注意需要更新相关的顶点关系
*/
Status DeleteVex(MGraph* G, VertexType v);
/*
* 插入边/弧<v, w>
*/
Status InsertArc(MGraph* G, VertexType v, VertexType w, ...);
/*
* 删除边/弧<v, w>
*/
Status DeleteArc(MGraph* G, VertexType v, VertexType w);
/*
* 深度优先遍历(此处借助递归实现)
*/
void DFSTraverse(MGraph G, Status(Visit)(VertexType));
/*
* 深度优先遍历核心函数
*/
static void DFS(MGraph G, int v);
/*
* 广度优先遍历(此处借助队列实现)
*/
void BFSTraverse(MGraph G, Status(Visit)(VertexType));
/*
* 以图形化形式输出当前结构
*/
void PrintGraph(MGraph G);
#pragma endregion
#pragma region 定义队列以及相关方法
/* 链队元素类型定义 */
typedef int QElemType;
// 队列元素结构
typedef struct QNode {
QElemType data;
struct QNode* next;
} QNode, *QueuePtr;
// 队列结构
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LinkQueue; // 队列的链式存储表示
/*
* 构造一个空的链队。
*/
Status InitQueue(LinkQueue* Q);
/*
* 判断链队中是否包含有效数据。
*/
Status QueueEmpty(LinkQueue Q);
/*
* 入队
*/
Status EnQueue(LinkQueue* Q, QElemType e);
/*
* 出队
*/
Status DeQueue(LinkQueue* Q, QElemType* e);
#pragma endregion
#pragma region 其他方法
/*
* 从文件中读取预设的英文符号
*/
int ReadData(FILE* fp, char* format, ...);
/*
* 跳过空白，寻找下一个"可读"符号。
*/
void skipBlank(FILE* fp);
#pragma endregion主文件：MGraph.c
#include "stdafx.h"
#include "MGraph.h"
// 录入数据的源文件；fp为null时，说明需要从控制台录入
static FILE* fp = NULL;
/*
* IncInfo指示该图/网的边/弧上是否存在附加信息。
* 如果其值不为0，则表示无附加信息，否则，表示存在附加信息。
*/
Boolean IncInfo = FALSE;
// 访问标志数组，记录访问过的顶点
static Boolean visited[MAX_VERTEX_NUM];
// 函数变量
static Status(*VisitFunc)(VertexType e);
/* 全局变量*/
Boolean debug = FALSE; // 是否使用debug模式。测试时可设置为TRUE，发布时可设置为FALSE(修改debug值后，一般需要重新生成静态库)。
#pragma region 其他方法实现
/*
* 从文件中读取预设的英文符号
*
* 这是自定义的数据录入函数，用于从文件fp中读取格式化的输入，
* 与fscanf的不同之处在于此函数只会读取英文字符，对于中文字符，则直接跳过。
*
* 注：
* 1. 这里约定所有格式串为简单形式，如：%d%c%s等，而不是%2d%5s等
* 2. 读取字符串时，遇到空格或非打印字符会停止读取
*/
int ReadData(FILE* fp, char* format, ...) {
int* i; // 存储读取到的整型
float* f; // 存储读取到的浮点型
char* ch; // 存储读取到的字符型
char* s; // 存储读取到的字符串型
int n; // 遍历存储字符串的字符数组
int len; // 格式串format的长度
int k; // 遍历格式串时的游标
int tmp; // 暂存从文件中读取到的字符
va_list ap; // 可变参数指针，指向存储数据的变量
// 累计成功读取到的字符数
int count = 0;
/*
* 获取格式串的长度
* 这里预设格式串仅由简单
*/
len = strlen(format);
// ap指向首个可变参数
va_start(ap, format);
// 只遍历奇数索引，因为偶数索引下都是%
for (k = 1; k <= len; k = k + 2) {
// 跳过所有非西文字符
while ((tmp = getc(fp)) != EOF) {
// 遇到首个西文字符，将此西文字符重新放入输入流
if ((tmp >= 0 && tmp <= 127)) {
ungetc(tmp, fp);
break;
}
}
// 如果已读到文件结尾，结束读取
if (tmp == EOF) {
break;
}
// 遇到了"%c"，应该读取字符
if (format[k] == 'c') {
ch = va_arg(ap, char*);
count += fscanf(fp, "%c", ch);
}
// 遇到了"%d"，应该读取整型
if (format[k] == 'd') {
i = va_arg(ap, int*);
while ((tmp = getc(fp)) != EOF) {
// 寻找整数区域
if ((tmp >= '0' && tmp <= '9') || tmp == '-' || tmp == '+') {
ungetc(tmp, fp);
break;
}
}
if (tmp != EOF) {
count += fscanf(fp, "%d", i);
}
}
// 读取浮点型，一律存储为double类型
if (format[k] == 'f') {
f = va_arg(ap, float*);
while ((tmp = getc(fp)) != EOF) {
if ((tmp >= '0' && tmp <= '9') || tmp == '-' || tmp == '+' || tmp == '.') {
ungetc(tmp, fp);
break;
}
}
if (tmp != EOF) {
count += fscanf(fp, "%f", f);
}
}
// 读取字符串
if (format[k] == 's') {
s = va_arg(ap, char*);
n = 0;
// 查找排除空格的可打印字符
while ((tmp = getc(fp)) != EOF && (!isprint(tmp) || tmp == ' ')) {
}
// 如果未到文件结尾
if (!feof(fp)) {
// 将上面读到的字符重新放入流中
ungetc(tmp, fp);
while ((tmp = getc(fp)) != EOF) {
// 存储排除空格的可打印字符
if (isprint(tmp) && tmp != ' ') {
s[n++] = tmp;
}
else {
ungetc(tmp, fp);
break;
}
}
count++;
}
// 字符串最后一个字符为空字符
s[n] = '\0';
}
}// for
va_end(ap);
return count;
}
/*
* 跳过空白，寻找下一个"可读"符号。
*
* 此方法常用在读取字符的语句之前，这会跳过遇到目标字符之前的空白符号，
* 比如跳过'\r'、'\n'、'\r\n'、' '、'\t'、'\f'。
*/
void skipBlank(FILE* fp) {
int ch;
if (fp == NULL) {
return;
}
while ((ch = getc(fp)) != EOF) {
// 如果遇到ANSI码之外的符号，比如汉字，则直接跳过
if (ch >= 0 && ch <= 127) {
// 如果遇到的ANSI码不是空白，比如'\r'、'\n'、'\r\n'、' '、'\t'、'\f'，则表示该符号"可读"
if (ch != '\r' && ch != '\n' && ch != ' ' && ch != '\t' && ch != '\f') {
// 将"可读"符号放入输入流，以待后续工具来读取它
ungetc(ch, fp);
break; // 可以跳出循环了，因为已经找到了"可读"符号
}
}
}
}
#pragma endregion
/*
* 创建图/表
* 如果需要从控制台读取数据，则path为NULL，或path[kind]为""。
* 如果需要从文件中读取数据，则需要在path中填写文件名信息。
*/
Status CreateGraph(MGraph* G, char* path[]) {
int readFromConsole; // 是否从控制台读取数据
int kind;
Status flag;
printf("请输入图的类型(0-有向图 │ 1-有向网 │ 2-无向图 │ 3-无向网)：");
scanf("%d", &kind);
// 类型不合规
if (kind < 0 || kind > 3) {
return ERROR;
}
// 如果没有文件路径信息，则从控制台读取输入
readFromConsole = (path == NULL) || strcmp(path[kind], "") == 0;
// 需要从文件读取
if (readFromConsole) {
(*G).kind = GraphKind(kind); // 记录图/网的类型
}
else {
// 打开文件，准备读取测试数据
fp = fopen(path[kind], "r");
if (fp == NULL) {
return ERROR;
}
// 录入图的类型
ReadData(fp, "%d", &((*G).kind));
}
// 随机创建有向图/网或无向图/网的一种
switch ((*G).kind) {
case DG:
flag = CreateDG(G);
break;
case DN:
flag = CreateDN(G);
break;
case UDG:
flag = CreateUDG(G);
break;
case UDN:
flag = CreateUDN(G);
break;
default:
flag = ERROR;
break;
}
if (fp != NULL) {
fclose(fp);
fp = NULL;
}
return flag;
}
/*
* 构造有向图
*/
static Status CreateDG(MGraph* G) {
int i, j, k;
ArcCell arcs = { 0, NULL }; // 有向图每条边的初始值
VertexType v1, v2;
if (fp == NULL) {
printf("请输入有向图的顶点数：");
scanf("%d", &((*G).vexnum));
printf("请输入有向图的弧数：");
scanf("%d", &((*G).arcnum));
printf("该有向图的弧上是否包含其他附加信息(0-不包含│1-包含)：");
scanf("%d", &IncInfo);
// 录入顶点集
printf("请录入 %d 个顶点，不同顶点之间用空格隔开：", (*G).vexnum);
for (i = 0; i < (*G).vexnum; i++) {
// 跳过空白，寻找下一个"可读"符号
skipBlank(stdin);
scanf("%c", &((*G).vexs[i]));
}
}
else {
ReadData(fp, "%d", &((*G).vexnum)); // 录入顶点数
ReadData(fp, "%d", &((*G).arcnum)); // 录入弧数
ReadData(fp, "%d", &IncInfo); // 判断弧上是否包含附加信息
// 录入顶点集
for (i = 0; i < (*G).vexnum; i++) {
// 跳过空白，寻找下一个"可读"符号
skipBlank(fp);
ReadData(fp, "%c", &((*G).vexs[i]));
}
}
// 初始化有向图的邻接矩阵
for (i = 0; i < (*G).vexnum; i++) {
for (j = 0; j < (*G).vexnum; j++) {
(*G).arcs[i][j] = arcs;
}
}
// 仅在控制台录入信息时输出此提示
if (fp == NULL && (*G).arcnum != 0) {
printf("请为有向图依次录入 %d 条弧的信息，顶点之间用空格隔开：\n", (*G).arcnum);
}
// 录入弧的信息
for (k = 0; k < (*G).arcnum; k++) {
if (fp == NULL) {
printf("第 %2d 条弧：", k + 1);
skipBlank(stdin); // 跳过空白，寻找下一个可读符号
scanf("%c", &v1);
skipBlank(stdin); // 跳过空白，寻找下一个可读符号
scanf("%c", &v2);
}
else {
// 跳过空白，寻找下一个可读符号
skipBlank(fp);
ReadData(fp, "%c%c", &v1, &v2);
}
i = LocateVex(*G, v1); // 获取顶点v1在顶点集中的位置
j = LocateVex(*G, v2); // 获取顶点v2在顶点集中的位置
// 将指定的顶点关系设置为1，指示这两个顶点是直接连接的(注：这里没有验证下标是否越界)
(*G).arcs[i][j].adj = 1;
// 如果需要录入弧的其他附加信息
if (IncInfo) {
// 最后录入附加信息
Input(*G, &((*G).arcs[i][j].info));
}
}
// 从文件中读取数据时，最后其实应当判断一下是否读到了足够的信息
return OK;
}
/*
* 构造有向网
*/
static Status CreateDN(MGraph* G) {
int i, j, k;
ArcCell arcs = { INFINITE, NULL }; // 有向网每条弧的初始值
VertexType v1, v2;
VRType w;
if (fp == NULL) {
printf("请输入有向网的顶点数：");
scanf("%d", &((*G).vexnum));
printf("请输入有向网的弧数：");
scanf("%d", &((*G).arcnum));
printf("该有向网的弧上是否包含其他附加信息(0-不包含│1-包含)：");
scanf("%d", &IncInfo);
// 录入顶点集
printf("请录入 %d 个顶点，不同顶点之间用空格隔开：", (*G).vexnum);
for (i = 0; i < (*G).vexnum; i++) {
// 跳过空白，寻找下一个"可读"符号
skipBlank(stdin);
scanf("%c", &((*G).vexs[i]));
}
}
else {
ReadData(fp, "%d", &((*G).vexnum)); // 录入顶点数
ReadData(fp, "%d", &((*G).arcnum)); // 录入弧数
ReadData(fp, "%d", &IncInfo); // 判断弧上是否包含附加信息
// 录入顶点集
for (i = 0; i < (*G).vexnum; i++) {
// 跳过空白，寻找下一个"可读"符号
skipBlank(fp);
ReadData(fp, "%c", &((*G).vexs[i]));
}
}
// 初始化有向网的邻接矩阵
for (i = 0; i < (*G).vexnum; i++) {
for (j = 0; j < (*G).vexnum; j++) {
(*G).arcs[i][j] = arcs;
}
}
// 仅在控制台录入信息时输出此提示
if (fp == NULL && (*G).arcnum != 0) {
printf("请为有向网依次录入 %d 条弧(带权值)的信息，顶点及权值之间用空格隔开：\n", (*G).arcnum);
}
// 录入弧的信息
for (k = 0; k < (*G).arcnum; k++) {
if (fp == NULL) {
printf("第 %2d 条弧及其权值：", k + 1);
skipBlank(stdin); // 跳过空白，寻找下一个可读符号
scanf("%c", &v1);
skipBlank(stdin); // 跳过空白，寻找下一个可读符号
scanf("%c", &v2);
scanf("%d", &w);
}
else {
// 跳过空白，寻找下一个可读符号
skipBlank(fp);
ReadData(fp, "%c%c%d", &v1, &v2, &w);
}
i = LocateVex(*G, v1); // 获取顶点v1在顶点集中的位置
j = LocateVex(*G, v2); // 获取顶点v2在顶点集中的位置
// 在指定的顶点关系上记录权值(注：这里没有验证下标是否越界)
(*G).arcs[i][j].adj = w;
// 如果需要录入弧的其他附加信息
if (IncInfo) {
// 最后录入附加信息
Input(*G, &((*G).arcs[i][j].info));
}
}
// 从文件中读取数据时，最后其实应当判断一下是否读到了足够的信息
return OK;
}
/*
* 构造无向图
*/
static Status CreateUDG(MGraph* G) {
int i, j, k;
ArcCell arcs = { 0, NULL }; // 无向图每条边的初始值
VertexType v1, v2;
if (fp == NULL) {
printf("请输入无向图的顶点数：");
scanf("%d", &((*G).vexnum));
printf("请输入无向图的边数：");
scanf("%d", &((*G).arcnum));
printf("该无向图的边上是否包含其他附加信息(0-不包含│1-包含)：");
scanf("%d", &IncInfo);
// 录入顶点集
printf("请录入 %d 个顶点，不同顶点之间用空格隔开：", (*G).vexnum);
for (i = 0; i < (*G).vexnum; i++) {
// 跳过空白，寻找下一个"可读"符号
skipBlank(stdin);
scanf("%c", &((*G).vexs[i]));
}
}
else {
ReadData(fp, "%d", &((*G).vexnum)); // 录入顶点数
ReadData(fp, "%d", &((*G).arcnum)); // 录入边数
ReadData(fp, "%d", &IncInfo); // 判断边上是否包含附加信息
// 录入顶点集
for (i = 0; i < (*G).vexnum; i++) {
// 跳过空白，寻找下一个"可读"符号
skipBlank(fp);
ReadData(fp, "%c", &((*G).vexs[i]));
}
}
// 初始化无向图的邻接矩阵
for (i = 0; i < (*G).vexnum; i++) {
for (j = 0; j < (*G).vexnum; j++) {
(*G).arcs[i][j] = arcs;
}
}
// 仅在控制台录入信息时输出此提示
if (fp == NULL && (*G).arcnum != 0) {
printf("请为无向图依次录入 %d 条边的信息，顶点之间用空格隔开：\n", (*G).arcnum);
}
// 录入边的信息
for (k = 0; k < (*G).arcnum; k++) {
if (fp == NULL) {
printf("第 %2d 条边：", k + 1);
skipBlank(stdin); // 跳过空白，寻找下一个可读符号
scanf("%c", &v1);
skipBlank(stdin); // 跳过空白，寻找下一个可读符号
scanf("%c", &v2);
}
else {
// 跳过空白，寻找下一个可读符号
skipBlank(fp);
ReadData(fp, "%c%c", &v1, &v2);
}
i = LocateVex(*G, v1); // 获取顶点v1在顶点集中的位置
j = LocateVex(*G, v2); // 获取顶点v2在顶点集中的位置
// 将指定的顶点关系设置为1，指示这两个顶点是直接连接的(注：这里没有验证下标是否越界)
(*G).arcs[i][j].adj = 1;
// 如果需要录入边的其他附加信息
if (IncInfo) {
// 最后录入附加信息
Input(*G, &((*G).arcs[i][j].info));
}
// 填充对称点
(*G).arcs[j][i] = (*G).arcs[i][j];
}
// 从文件中读取数据时，最后其实应当判断一下是否读到了足够的信息
return OK;
}
/*
* 构造无向网
*/
static Status CreateUDN(MGraph* G) {
int i, j, k;
ArcCell arcs = { INFINITE, NULL }; // 无向网每条边的初始值
VertexType v1, v2;
VRType w;
if (fp == NULL) {
printf("请输入无向网的顶点数：");
scanf("%d", &((*G).vexnum));
printf("请输入无向网的边数：");
scanf("%d", &((*G).arcnum));
printf("该无向网的边上是否包含其他附加信息(0-不包含│1-包含)：");
scanf("%d", &IncInfo);
// 录入顶点集
printf("请录入 %d 个顶点，不同顶点之间用空格隔开：", (*G).vexnum);
for (i = 0; i < (*G).vexnum; i++) {
// 跳过空白，寻找下一个"可读"符号
skipBlank(stdin);
scanf("%c", &((*G).vexs[i]));
}
}
else {
ReadData(fp, "%d", &((*G).vexnum)); // 录入顶点数
ReadData(fp, "%d", &((*G).arcnum)); // 录入边数
ReadData(fp, "%d", &IncInfo); // 判断边上是否包含附加信息
// 录入顶点集
for (i = 0; i < (*G).vexnum; i++) {
// 跳过空白，寻找下一个"可读"符号
skipBlank(fp);
ReadData(fp, "%c", &((*G).vexs[i]));
}
}
// 初始化无向网的邻接矩阵
for (i = 0; i < (*G).vexnum; i++) {
for (j = 0; j < (*G).vexnum; j++) {
(*G).arcs[i][j] = arcs;
}
}
// 仅在控制台录入信息时输出此提示
if (fp == NULL && (*G).arcnum != 0) {
printf("请为无向网依次录入 %d 条边(带权值)的信息，顶点及权值之间用空格隔开：\n", (*G).arcnum);
}
// 录入边的信息
for (k = 0; k < (*G).arcnum; k++) {
if (fp == NULL) {
printf("第 %2d 条边及其权值：", k + 1);
skipBlank(stdin); // 跳过空白，寻找下一个可读符号
scanf("%c", &v1);
skipBlank(stdin); // 跳过空白，寻找下一个可读符号
scanf("%c", &v2);
scanf("%d", &w);
}
else {
// 跳过空白，寻找下一个可读符号
skipBlank(fp);
ReadData(fp, "%c%c%d", &v1, &v2, &w);
}
i = LocateVex(*G, v1); // 获取顶点v1在顶点集中的位置
j = LocateVex(*G, v2); // 获取顶点v2在顶点集中的位置
// 在指定的顶点关系上记录权值(注：这里没有验证下标是否越界)
(*G).arcs[i][j].adj = w;
// 如果需要录入边的其他附加信息
if (IncInfo) {
// 最后录入附加信息
Input(*G, &((*G).arcs[i][j].info));
}
// 填充对称点
(*G).arcs[j][i] = (*G).arcs[i][j];
}
// 从文件中读取数据时，最后其实应当判断一下是否读到了足够的信息
return OK;
}
/*
* 录入边/弧的相关附加信息
*/
static void Input(MGraph G, InfoType** info) {
//录入边/弧的信息，本测试涉及到的边/弧默认无其他附加信息
}
/*
* 销毁
*/
Status DestroyGraph(MGraph* G) {
(*G).vexnum = 0;
(*G).arcnum = 0;
IncInfo = 0;
return OK;
}
/*
* 查找
*/
int LocateVex(MGraph G, VertexType u) {
int i;
for (i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == u) {
return i;
}
}
return -1;
}
/*
* 取值
* 返回索引v处的顶点值
*/
VertexType GetVex(MGraph G, int v) {
if (v < 0 || v >= G.vexnum) {
return '\0'; // 指定的顶点不存在
}
return G.vexs[v];
}
/*
* 赋值
* 将顶点v赋值为value
*/
Status PutVex(MGraph* G, VertexType v, VertexType value) {
int k;
// 首先需要判断该顶点是否存在
k = LocateVex((*G), v);
if (k == -1) {
return ERROR; // 指定的顶点不存在
}
(*G).vexs[k] = value;
return OK;
}
/*
* 首个邻接点
* 返回顶点v的首个邻接点
*/
int FirstAdjVex(MGraph G, VertexType v) {
int kv, j;
VRType adj;
kv = LocateVex(G, v);
if (kv == -1) {
return -1; // 指定的顶点不存在
}
// 确定一个非连通标记
if (G.kind == DG || G.kind == UDG) {
adj = 0; // 图
}
else if (G.kind == DN || G.kind == UDN) {
adj = INFINITE; // 网
}
else {
return -1;
}
// 从头开始查找
for (j = 0; j < G.vexnum; j++) {
// 找到与v直接连接的顶点
if (G.arcs[kv][j].adj != adj) {
return j;
}
}
return -1;
}
/*
* 下一个邻接点
* 返回顶点v的(相对于w的)下一个邻接点
*/
int NextAdjVex(MGraph G, VertexType v, VertexType w) {
int kv, kw, j;
VRType adj;
kv = LocateVex(G, v);
if (kv == -1) {
return -1; // 指定的顶点不存在
}
kw = LocateVex(G, w);
if (kw == -1) {
return -1; // 指定的顶点不存在
}
// 确定一个非连通标记
if (G.kind == DG || G.kind == UDG) {
adj = 0; // 图
}
else if (G.kind == DN || G.kind == UDN) {
adj = INFINITE; // 网
}
else {
return -1;
}
// 从顶点w后开始查找
for (j = kw + 1; j < G.vexnum; j++) {
// 找到与v直接连接的顶点
if (G.arcs[kv][j].adj != adj) {
return j;
}
}
return -1;
}
/*
* 插入顶点
* 将指定的顶点v追加到顶点集中，未建立该顶点与其他顶点的关系
*/
Status InsertVex(MGraph* G, VertexType v) {
int i, k;
VRType adj;
// 顶点数过多
if ((*G).vexnum == MAX_VERTEX_NUM) {
return ERROR;
}
// 首先需要判断该顶点是否存在
k = LocateVex(*G, v);
if (k >= 0) {
return ERROR; // 指定的顶点存在时，无需重复添加
}
// 确定一个非连通标记
if ((*G).kind == DG || (*G).kind == UDG) {
adj = 0; // 图
}
else if ((*G).kind == DN || (*G).kind == UDN) {
adj = INFINITE; // 网
}
else {
return ERROR;
}
(*G).vexs[(*G).vexnum] = v;
(*G).vexnum++;
for (i = 0; i < (*G).vexnum; i++) {
(*G).arcs[i][(*G).vexnum - 1].adj = adj;
(*G).arcs[(*G).vexnum - 1][i].adj = adj;
}
return OK;
}
/*
* 删除顶点
* 从顶点集中删除指定的顶点v，注意需要更新相关的顶点关系
*/
Status DeleteVex(MGraph* G, VertexType v) {
int i, j, k;
VRType adj;
k = LocateVex(*G, v);
if (k == -1) {
return ERROR; // 指定的顶点不存在
}
// 确定一个非连通标记
if ((*G).kind == DG || (*G).kind == UDG) {
adj = 0; // 图
}
else if ((*G).kind == DN || (*G).kind == UDN) {
adj = INFINITE; // 网
}
else {
return ERROR;
}
// 更新边/弧的数量
for (i = 0; i < (*G).vexnum; i++) {
// 如果存在从顶点v出发的边，则边的数量减一
if ((*G).arcs[k][i].adj != adj) {
(*G).arcnum--;
}
// 如果这是有向的图/网，依然需要更新边/弧的数量
if ((*G).kind == DG || (*G).kind == DN) {
// 如果存在到达顶点v的边，则边的数量减一
if ((*G).arcs[i][k].adj != adj) {
(*G).arcnum--;
}
}
}
// 将邻接矩阵中的顶点关系左移
for (j = k + 1; j < (*G).vexnum; j++) {
for (i = 0; i < (*G).vexnum; i++) {
(*G).arcs[i][j - 1] = (*G).arcs[i][j]; // 右边的列挪到左边的列
}
}
// 将邻接矩阵中的顶点关系上移
for (i = k + 1; i < (*G).vexnum; i++) {
// 注，由于上面进行左移的关系，所以这里的j是小于(*G).vexnum - 1
for (j = 0; j < (*G).vexnum - 1; j++) {
(*G).arcs[i - 1][j] = (*G).arcs[i][j]; // 下一行挪到上一行
}
}
// 将该顶点从顶点集中移除
for (i = k + 1; i < (*G).vexnum; i++) {
(*G).vexs[i - 1] = (*G).vexs[i];
}
// 顶点数减一
(*G).vexnum--;
return OK;
}
/*
* 插入边/弧<v, w>
* 如果当前图/网是无向的，则插入一条弧需要增加两个顶点关系，但弧的数量只增一。
*/
Status InsertArc(MGraph* G, VertexType v, VertexType w, ...) {
int kv, kw;
VRType adj; // 顶点关系
Boolean overlay = FALSE; // 是否为覆盖添加
InfoType* info = NULL; // 边/弧的附加信息
va_list ap;
kv = LocateVex(*G, v);
if (kv == -1) {
return ERROR; // 指定的顶点不存在
}
kw = LocateVex(*G, w);
if (kw == -1) {
return ERROR; // 指定的顶点不存在
}
// 拒绝环
if (kv == kw) {
return ERROR;
}
/* 确定一个顶点关系 */
// 对于图来说，连通关系用1表示
if ((*G).kind == DG || (*G).kind == UDG) {
adj = 1;
// 如果边/弧上存在附加信息
if (IncInfo) {
va_start(ap, w); // 在w后查询首个可变参数
info = va_arg(ap, InfoType*); // 获取附加信息
va_end(ap);
}
overlay = (*G).arcs[kv][kw].adj != 0;
// 对于网来说，此处需要从可变参数中获取权值信息
}
else if ((*G).kind == DN || (*G).kind == UDN) {
va_start(ap, w); // 在w后查询首个可变参数
adj = va_arg(ap, VRType); // 获取权值信息
// 如果边/弧上存在附加信息
if (IncInfo) {
info = va_arg(ap, InfoType*); // 获取附加信息
}
va_end(ap);
overlay = (*G).arcs[kv][kw].adj != INFINITE;
}
else {
return ERROR;
}
(*G).arcs[kv][kw].adj = adj; // 记录顶点关系
// 如果边/弧上存在附加信息，则记录附加关系
if (IncInfo) {
(*G).arcs[kv][kw].info = info;
}
// 如果是无向图/网，需要考虑对称性
if ((*G).kind == UDG || (*G).kind == UDN) {
(*G).arcs[kw][kv] = (*G).arcs[kv][kw];
}
// 在非覆盖的情形下，才考虑更新边/弧的数量
if (!overlay) {
(*G).arcnum++; // 不论有向无向，边/弧数只增一
}
return OK;
}
/*
* 删除边/弧
* 此删除只是更新边/弧的连通关系
*/
Status DeleteArc(MGraph* G, VertexType v, VertexType w) {
int kv, kw;
VRType adj;
Boolean found = FALSE; // 是否存在待删除的边/弧
kv = LocateVex(*G, v);
if (kv == -1) {
return ERROR; // 指定的顶点不存在
}
kw = LocateVex(*G, w);
if (kw == -1) {
return ERROR; // 指定的顶点不存在
}
// 确定一个非连通标记
if ((*G).kind == DG || (*G).kind == UDG) {
adj = 0; // 图
found = (*G).arcs[kv][kw].adj != 0;
}
else if ((*G).kind == DN || (*G).kind == UDN) {
adj = INFINITE; // 网
found = (*G).arcs[kv][kw].adj != INFINITE;
}
else {
return ERROR;
}
// 标记这两个顶点已断开连接
(*G).arcs[kv][kw].adj = adj;
// 如果是无向图/网，需要考虑对称性
if ((*G).kind == UDG || (*G).kind == UDN) {
(*G).arcs[kw][kv] = (*G).arcs[kv][kw];
}
// 在找到了指定的弧时，才考虑更新边/弧的数量
if (found) {
(*G).arcnum--; // 不论有向无向，边/弧数只减一
}
return OK;
}
/*
* 深度优先遍历(此处借助递归实现)
*/
void DFSTraverse(MGraph G, Status(Visit)(VertexType)) {
int v;
// 使用全局变量VisitFunc，使得DFS不必设置函数指针参数
VisitFunc = Visit;
// 访问标志数组初始化
for (v = 0; v < G.vexnum; v++) {
visited[v] = FALSE;
}
// 此处需要遍历的原因是并不能保证所有顶点都连接在了一起
for (v = 0; v < G.vexnum; v++) {
if (!visited[v]) {
DFS(G, v); // 对尚未访问的顶点调用DFS
}
}
}
/*
* 深度优先遍历核心函数
*/
static void DFS(MGraph G, int v) {
int w;
// 从第v个顶点出发递归地深度优先遍历图G
visited[v] = TRUE;
// 访问第v个顶点
VisitFunc(G.vexs[v]);
for (w = FirstAdjVex(G, G.vexs[v]);
w >= 0;
w = NextAdjVex(G, G.vexs[v], G.vexs[w])) {
if (!visited[w]) {
DFS(G, w); // 对尚未访问的顶点调用DFS
}
}
}
#pragma region 队列基本操作
/*
* 初始化链队
*/
Status InitQueue(LinkQueue* Q) {
if (Q == NULL) {
return ERROR;
}
(*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode));
if (!(*Q).front) {
exit(OVERFLOW);
}
(*Q).front->next = NULL;
return OK;
}
/*
* 判空
*
* 判断链队中是否包含有效数据。
*
* 返回值：
* TRUE : 链队为空
* FALSE: 链队不为空
*/
Status QueueEmpty(LinkQueue Q) {
if (Q.front == Q.rear) {
return TRUE;
}
else {
return FALSE;
}
}
/*
* 入队
*
* 将元素e添加到队列尾部。
*/
Status EnQueue(LinkQueue* Q, QElemType e) {
QueuePtr p;
if (Q == NULL || (*Q).front == NULL) {
return ERROR;
}
p = (QueuePtr)malloc(sizeof(QNode));
if (!p) {
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
(*Q).rear->next = p;
(*Q).rear = p;
return OK;
}
/*
* 出队
*
* 移除队列头部的元素，将其存储到e中。
*/
Status DeQueue(LinkQueue* Q, QElemType* e) {
QueuePtr p;
if (Q == NULL || (*Q).front == NULL || (*Q).front == (*Q).rear) {
return ERROR;
}
p = (*Q).front->next;
*e = p->data;
(*Q).front->next = p->next;
if ((*Q).rear == p) {
(*Q).rear = (*Q).front;
}
free(p);
return OK;
}
#pragma endregion
/*
* 广度优先遍历(此处借助队列实现)
*/
void BFSTraverse(MGraph G, Status(Visit)(VertexType)) {
int v, w;
LinkQueue Q;
QElemType u;
// 初始化为未访问
for (v = 0; v < G.vexnum; v++) {
visited[v] = FALSE;
}
// 置空辅助队列
InitQueue(&Q);
for (v = 0; v < G.vexnum; v++) {
// 如果该顶点已访问过，则直接忽略
if (visited[v]) {
continue;
}
// 标记该顶点已访问
visited[v] = TRUE;
// 访问顶点
Visit(G.vexs[v]);
EnQueue(&Q, v);
while (!QueueEmpty(Q)) {
DeQueue(&Q, &u);
// 先集中访问顶点v的邻接顶点，随后再访问邻接顶点的邻接顶点
for (w = FirstAdjVex(G, G.vexs[u]);
w >= 0;
w = NextAdjVex(G, G.vexs[u], G.vexs[w])) {
if (!visited[w]) {
visited[w] = TRUE;
Visit(G.vexs[w]);
EnQueue(&Q, w);
}
}
}
}
}
/*
* 以图形化形式输出当前结构
* 注：在图/网中，使用"-"来表示两顶点不直接连通
*/
void PrintGraph(MGraph G) {
int i, j;
if (G.vexnum == 0) {
printf("空图，无需打印！\n");
return;
}
printf("当前图/网包含 %2d 个顶点， %2d 条边/弧...\n", G.vexnum, G.arcnum);
printf(" ");
for (i = 0; i < G.vexnum; i++) {
printf(" %c", G.vexs[i]);
}
printf("\n");
for (i = 0; i < G.vexnum; i++) {
printf("%c ", G.vexs[i]);
for (j = 0; j < G.vexnum; j++) {
if (((G.kind == DG || G.kind == UDG) && G.arcs[i][j].adj == 0) || ((G.kind == DN || G.kind == UDN) && G.arcs[i][j].adj == INFINITE)) {
printf(" -");
}
else {
printf("%3d", G.arcs[i][j].adj);
}
}
printf("\n");
}
}
// 测试函数，打印元素
Status PrintElem(VertexType c) {
printf("%c ", c);
return OK;
}
int main(int argc, char* argv[]) {
MGraph G;
printf("\t\t CreateGraph \n");
{
int input;
printf("创建图/网...\n");
printf("请选择输入图方式(0-控制台输入 │ 1-文件中读取)：");
scanf("%d", &input);
// 输入不合规不合规
if (input < 0 || input > 1) {
return ERROR;
}
if (input == 0) CreateGraph(&G, NULL);
else
{
char* path[4];
path[0] = "Test_DG.txt";
path[1] = "Test_DN.txt";
path[2] = "Test_UDG.txt";
path[3] = "Test_UDN.txt";
CreateGraph(&G, path);
}
}
printf("\t\t PrintGraph \n");
{
printf("输出图/网的邻接矩阵... \n");
PrintGraph(G);
}
printf("\t\t LocateVex \n");
{
VertexType u = 'X';
printf("顶点 '%c' 的位置为 %d\n", u, LocateVex(G, u));
}
printf("\t\t GetVex \n");
{
int v = 1;
printf("索引 '%d' 处的顶点值为 %c\n", v, GetVex(G, v));
}
printf("\t\t FirstAdjVex \n");
{
VertexType v = 'X';
int k = FirstAdjVex(G, v);
printf("顶点 '%c' 的第一个邻接顶点为 '%c'\n", v, G.vexs[k]);
}
printf("\t\t NextAdjVex \n");
{
VertexType v = 'X';
VertexType w = 'A';
int k = NextAdjVex(G, v, w);
printf("顶点 '%c' 相对于顶点 '%c' 的下一个邻接顶点为 '%c'\n", v, w, G.vexs[k]);
}
printf("\t\t DeleteVex \n");
{
VertexType v = 'X';
printf("删除顶点 '%c' ...\n", v);
DeleteVex(&G, v);
PrintGraph(G);
}
printf("\t\t InsertVex \n");
{
VertexType v = 'Y';
printf("插入顶点 '%c' ...\n", v);
InsertVex(&G, v);
PrintGraph(G);
}
printf("\t\t InsertArc \n");
{
// 注：<E, B>是重复的边
VertexType v[10] = { 'B', 'C', 'E', 'Y', 'Y', 'Y', 'D', 'D', 'E', 'E' };
VertexType w[10] = { 'Y', 'Y', 'Y', 'A', 'B', 'D', 'C', 'A', 'B', 'D' };
VRType adj[10] = { 8, 5, 1, 11, 2, 6, 3, 7, 2, 9 };
int k;
// 图
if (G.kind == DG || G.kind == UDG) {
for (k = 0; k < 10; k++) {
printf("插入无权值的边：<%c, %c>...\n", v[k], w[k]);
InsertArc(&G, v[k], w[k]);
}
// 网
}
else if (G.kind == DN || G.kind == UDN) {
for (k = 0; k < 10; k++) {
printf("插入带权值的边：<%c, %c, %d>...\n", v[k], w[k], adj[k]);
InsertArc(&G, v[k], w[k], adj[k]);
}
}
else {
return ERROR;
}
PrintGraph(G);
}
printf("\t\t PutVex \n");
{
VertexType v = 'Y';
VertexType value = 'F';
printf("对顶点 '%c' 赋值 '%c' ...\n", v, value);
PutVex(&G, v, value);
PrintGraph(G);
}
printf("\t\t DeleteArc \n");
{
VertexType v[3] = { 'D', 'E', 'F' };
VertexType w[3] = { 'A', 'B', 'B' };
int k;
for (k = 0; k < 3; k++) {
printf("删除边：<%c, %c>...\n", v[k], w[k]);
DeleteArc(&G, v[k], w[k]);
}
PrintGraph(G);
}
printf("\t\t DFSTraverse等 \n");
{
printf("深度优先遍历图/网...\n");
DFSTraverse(G, PrintElem);
printf("\n");
}
printf("\t\t BFSTraverse \n");
{
printf("广度优先遍历图/网...\n");
BFSTraverse(G, PrintElem);
printf("\n");
}
printf("\t\t DestroyGraph \n");
{
printf("销毁图/网G...\n");
DestroyGraph(&G);
PrintGraph(G);
}
}注：测试文件因该与MGraph.c程序在同一路径下，如果其他路径下，需要修改main主函数里path变量的文件路径
如果要进行其他图测试，照下面格式修改为对应图即可！
Test_DG.txt
图类型→0（有向图）
顶点数→6
弧数→14
弧是否带有其他信息→0
顶点集→【A，X，B，C，D，E】
弧的集合→【A，B】【A，C】【A，D】【B，C】【B，D】【B，E】【C，B】【C，E】【C，X】【E，A】【E，D】【E，X】【X，A】【X，D】Test_DN.txt
图类型→1（有向网）
顶点数→6
弧数→14
弧是否带有其他信息→0
顶点集→【A，X，B，C，D，E】
弧的集合→【A，B，3】【A，C，8】【A，D，11】【B，C，7】【B，D，4】【B，E，1】【C，B，5】【C，E，17】【C，X，3】【E，A，6】【E，D，4】【E，X，2】【X，A，8】【X，D，10】Test_UDG.txt
图类型→2（无向图）
顶点数→6
边数→13
边是否带有其他信息→0
顶点集→【A，X，B，C，D，E】
边的集合→【A，B】【A，C】【A，D】【B，C】【B，D】【B，E】【C，E】【C，X】【E，A】【E，D】【E，X】【X，A】【X，D】Test_UDN.txt
图类型→3（无向网）
顶点数→6
边数→13
边是否带有其他信息→0
顶点集→【A，X，B，C，D，E】
边的集合→【A，B，3】【A，C，8】【A，D，11】【B，C，7】【B，D，4】【B，E，1】【C，E，17】【C，X，3】【E，A，6】【E，D，4】【E，X，2】【X，A，8】【X，D，10】