一、了解图的领接表存储
1、定义与结构
定义：邻接表是图的一种链式存储结构，它通过链表将每个顶点与其相邻的顶点连接起来。
结构：
- 顶点表：通常使用一个数组来存储图的顶点信息，数组的每个元素对应一个顶点，元素的内容可以是顶点的标识符或值，以及一个指向该顶点邻接链表的指针。
- 邻接链表：对于图中的每个顶点，创建一个链表，链表中存储了与该顶点相邻的其他顶点。链表中的每个节点通常包含两个字段：邻接点域（指示与当前顶点相邻的顶点在图中的位置）和链域（指示下一条邻接边的节点）。
2、性质与特点
- 节省空间：对于稀疏图，邻接表能够节省大量的内存空间，因为它只存储实际存在的边，而不需要像邻接矩阵那样为所有可能的边分配空间。
- 灵活性强：邻接表易于增加和删除顶点及其邻接边，因为链表结构允许动态调整。
- 查找效率高：在查找与某个顶点相邻的所有顶点时，只需要遍历该顶点的邻接链表，而不需要遍历整个矩阵，从而提高了查找效率。
3、构建与存储
构建方法：
- 确定图的顶点数量和边的关系。
- 创建一个顶点表数组，数组的每个元素对应一个顶点，并初始化其邻接链表为空。
- 根据图的边关系，将每条边对应的两个顶点添加到彼此的邻接链表中。
存储：
- 顶点表数组通常存储在内存中，以便快速访问。
- 邻接链表使用动态内存分配来存储，以适应不同顶点的邻接边数量。
4、应用与限制
应用：
- 社交网络中的用户关系可以用无向图表示，每个用户是一个顶点，好友关系是一条边。使用邻接表存储后，可以方便地查找某个用户的好友列表或共同好友等信息。
- 在图的遍历算法（如广度优先搜索BFS和深度优先搜索DFS）中，邻接表提供了一种高效的访问相邻顶点的方式。
- 邻接表也适用于求解最短路径、网络流问题等图论算法。
限制：
- 在查找特定的边时，可能需要遍历整个邻接表，相对较慢，特别是对于稠密图。
- 对于有向图，如果需要同时获取顶点的入度和出度，则需要分别维护邻接表和逆邻接表，这会增加存储空间的开销。
5、示例
假设有一个有向图G，其顶点集合为V={V1, V2, V3, V4}，边集合为E={(V1, V2), (V1, V4), (V2, V1), (V2, V3), (V3, V0), (V4, V3)}（注意：这里V0可能是一个错误或假设的顶点，通常顶点编号应从1开始且连续，但为保持示例的一致性，我们在此保留V0）。
该图的邻接表表示如下：
- V1的邻接链表包含：V2, V4
- V2的邻接链表包含：V1, V3
- V3的邻接链表包含：V0（注意：V0可能表示一个不存在的顶点或错误，根据实际情况调整）
- V4的邻接链表包含：V3
二、领接表结构（C语言）
1. 弧的结构体
#define MaxVertexNum 100
// 定义顶点对应的数据类型，这里使用字符类型来表示顶点
typedef char VertexType;
// 定义边对应的数据类型，这里使用整数类型来表示边的权重（如果有的话）
typedef int EdgeType;
// 定义邻接表中的弧（边）节点结构
typedef struct ArcNode {
int adjvex; // adjvex 表示该弧所指向的顶点的位置（索引）
struct ArcNode* nextarc; // nextarc 指向下一条与该顶点相连的弧的指针，形成链表
// EdgeType data; // 边的数据（如权重），如果需要使用边的权重，取消注释
} ArcNode; // 弧节点结构定义结束
2. 顶点结构体
// 定义邻接表中的顶点节点结构
typedef struct VNode {
VertexType name[20]; // name 存储顶点的名称或标识符，这里假设最长为19个字符加上一个结束符
ArcNode* firstarc; // firstarc 指向该顶点的第一条相连的弧的指针，即该顶点的邻接链表的头指针
} VNode, AdjList[MaxVertexNum]; // VNode 和 AdjList 是同义类型，AdjList 是一个顶点数组类型，其大小由 MaxVertexNum 决定
3. 定义图，用领接表表示
// 定义图的结构，使用邻接表表示
typedef struct {
int vexnum, arcnum; // vexnum 表示图的顶点数，arcnum 表示图的边数
AdjList vertices; // vertices 是邻接表，存储了图的所有顶点及其邻接链表
} ALGraph;
4. 初始化图
// 初始化图的邻接表表示的函数
void InitALGraph(ALGraph* G) {
// 初始化图的边数为0
G->arcnum = 0;
// 初始化图的顶点数为0
G->vexnum = 0;
// 遍历顶点数组，初始化每个顶点的邻接链表为空（即每个顶点的 firstarc 指针指向 NULL）
for (int i = 0; i < MaxVertexNum; i++) {
G->vertices[i].firstarc = NULL;
}
}三、领接表存储使用案例
实现的功能包括多个部分，涉及文件操作、从终端读取图的信息（由用户输入）、将图信息写入文件、从文件读取图信息、有向图转换为无向图以及查看图的信息。
1. 判断图中是否有a指向b
// 判断在有向图 G 中，顶点 a 是否有一条直接指向顶点 b 的边
bool VertexConnect(ALGraph G, int a, int b) {
// 从顶点 a 的邻接链表的头指针开始遍历
ArcNode* p = G.vertices[a].firstarc;
// 遍历顶点 a 的所有邻接顶点
for (; p != NULL; p = p->nextarc) {
// 如果当前邻接顶点的位置（索引）等于 b，则返回 true，表示 a 指向 b
if (p->adjvex == b) {
return true;
}
}
// 如果遍历完所有邻接顶点都没有找到指向 b 的边，则返回 false
return false;
}2. 将图中a连向b
// 将图中顶点 a 与顶点 b 相连
void ConnectAB(ALGraph* G, int a, int b) {
ArcNode* p, * t; // 声明两个指针，p 用于遍历，t 用于存储新创建的邻接点
// 初始化指针 p，指向顶点 a 的首条邻接边
p = G->vertices[a].firstarc;
// 为新邻接点分配内存
// 创建新的邻接点
t = (ArcNode*)malloc(sizeof(ArcNode)); // 分配内存给新节点
// 检查内存分配是否成功
if (t == NULL) {
printf("空间不足\n"); // 打印错误信息
exit(1); // 内存分配失败，退出程序
}
// 设置新邻接点的信息
t->adjvex = b; // 设置新节点的目标顶点索引为 b
t->nextarc = NULL; // 新节点为链表末尾，nextarc 指向 NULL
// 若顶点 a 无邻接边，则新边为首条边
if (p == NULL) {
G->vertices[a].firstarc = t; // 将新节点设置为顶点 a 的首条邻接边
return; // 添加完成，直接返回
}
// 若顶点 a 有邻接边，则将新边添加到邻接链表末尾
// 将 p 调整到最后一条边
while (p->nextarc != NULL) { // 遍历至链表末尾
p = p->nextarc; // 移动指针至下一条边
}
// 将新边添加到顶点 a 的邻接链表末尾
p->nextarc = t; // 将链表的最后一个节点的 nextarc 指向新节点
}3 通过用户输入创建图
// 通过用户输入创建图
void StructGraph(ALGraph* G) {
// 初始化数据
G->arcnum = 0;
G->vexnum = 0;
// 假设 MaxVertexNum 已经在其他地方定义
printf("请输入图的总顶点数(<=%d) : ", MaxVertexNum);
scanf("%d", &G->vexnum);
if (G->vexnum > MaxVertexNum || G->vexnum <= 0) {
printf("图的顶点数输入错误!\n");
exit(1);
}
// 初始化顶点数组
for (int i = 0; i < G->vexnum; i++) {
G->vertices[i].firstarc = NULL;
printf("\n请输入第 %d 顶点的名字: ", i);
scanf("%s", G->vertices[i].name); // 确保 name 数组足够大以存储输入
int key; // 将 key 的声明移到循环内部
ArcNode* p = G->vertices[i].firstarc;
while (1) {
clearScreen();
printf("请输入顶点： %s(%d) 将连接的点 \n(退出：-1； 输入限制： 0 <= num < %d) : ",
G->vertices[i].name, i, G->vexnum - 1);
scanf("%d", &key);
if (key == -1) break;
if (key < 0 || key >= G->vexnum) { // 修改条件，确保 key 在有效范围内
printf("输入顶点信息错误\n\n");
continue;
}
// 检查两点是否已经相连或者是否是与自身相连
if (VertexConnect(*G, i, key) || key == i) {
printf("此边已连接!!\n\n");
continue; // continue 会跳过后面的代码直接回到 while 循环的开始
}
// 创建新的邻接点
ArcNode* t = (ArcNode*)malloc(sizeof(ArcNode));
if (t == NULL) {
printf("空间不足\n");
exit(1);
}
t->adjvex = key;
t->nextarc = NULL;
// 将新的邻接点添加到链表中
if (p == NULL) {
G->vertices[i].firstarc = t;
p = t;
}
else {
p->nextarc = t;
p = t;
}
G->arcnum++;
printf("该边添加成功\n\n");
}
}
}
4. 将图像信息写入文件
// 将邻接表表示的图写入文本文件
void WriteALGraph(ALGraph* G) {
// 打开文件用于写入，如果文件打开失败则打印错误信息并退出程序
FILE* fp = fopen("Graph.txt", "w");
if (fp == NULL) {
printf("Graph.txt 文件打开失败！\n");
exit(1); // 退出程序，返回错误码1
}
// 将图的顶点数和边数写入文件
fprintf(fp, "%d %d\n", G->vexnum, G->arcnum);
// 遍历每个顶点
for (int i = 0; i < G->vexnum; i++) {
// 写入 "begin" 标记，表示一个顶点的邻接表开始
fprintf(fp, "begin ");
// 写入顶点的名称，假设名称不会超过20个字符，并使用空格填充至20个字符宽度
fprintf(fp, "%20s ", G->vertices[i].name);
// 获取当前顶点的第一个邻接点
ArcNode* p = G->vertices[i].firstarc;
// 遍历当前顶点的所有邻接点
while (p != NULL) {
// 写入 "to" 标记和邻接点的索引
fprintf(fp, "to %d ", p->adjvex);
// 如果弧有数据，可以取消以下行的注释，并写入弧的数据
// fprintf(fp, "arcdata %d", p->data);
// 移动到下一个邻接点
p = p->nextarc;
}
// 写入 "end" 标记，表示一个顶点的邻接表结束
fprintf(fp, "end\n");
}
// 关闭文件
fclose(fp);
// 打印成功信息
printf("写入成功\n");
}5. 从文件读取图的信息
void ReadGrcph(ALGraph* G) {
// 打开文件用于读取，如果文件打开失败则打印错误信息并退出程序
FILE* fp = fopen("Graph.txt", "r");
if (fp == NULL) {
printf("Graph.txt 文件打开失败！\n");
exit(1); // 退出程序，返回错误码1
}
// 初始化图G
InitALGraph(G);
int cntarcnum = 0; // 用于记录实际读取的边数
// 读入顶点数和边数（注意：这里读取的边数可能会被后续的实际边数覆盖）
fscanf(fp, "%d %d", &G->vexnum, &G->arcnum);
// 遍历每个顶点，读取其邻接信息
for (int i = 0; i < G->vexnum && !feof(fp); i++) {
char temps[20];
fscanf(fp, "%s", temps);
// 检查是否为"begin"标记，如果不是则报错并退出
if (strcmp(temps, "begin") != 0) {
printf("文件信息错误！！！\n");
fclose(fp);
exit(1);
}
// 读取顶点名称
fscanf(fp, "%s", G->vertices[i].name);
ArcNode* p = G->vertices[i].firstarc; // 指向当前顶点的首条邻接边
// 读取当前顶点的所有邻接信息，直到遇到"end"标记
while (1) {
fscanf(fp, "%s", temps);
if (strcmp(temps, "end") == 0) {
break; // 遇到"end"标记，结束当前顶点的邻接信息读取
}
else if (strcmp(temps, "to") != 0) {
// 如果不是"to"标记，则报错并退出
printf("文件信息错误！！！\n");
fclose(fp);
exit(1);
}
int key = 0; // 用于存储邻接顶点的索引
fscanf(fp, "%d", &key); // 读取邻接顶点的索引
// 检查索引的有效性，避免越界和自环
if (key < 0 || key >= G->vexnum) {
printf("文件信息错误！！！\n");
fclose(fp);
exit(1);
}
// 检查两点是否已经相连或者是否是与自身相连，如果是则跳过
if (VertexConnect(*G, i, key) || key == i) {
continue; // 跳过当前循环迭代，继续检查下一个邻接信息
}
// 创建新的邻接点并添加到链表中
ArcNode* t = (ArcNode*)malloc(sizeof(ArcNode));
if (t == NULL) {
fclose(fp);
printf("空间不足\n");
exit(1);
}
t->adjvex = key; // 设置邻接点的目标顶点索引
t->nextarc = NULL; // 新节点为链表末尾，nextarc 指向 NULL
// 将新节点添加到当前顶点的邻接链表末尾
if (p == NULL) {
G->vertices[i].firstarc = t; // 如果当前顶点无邻接边，则新边为首条边
p = t; // 更新指针p，使其指向新添加的节点
}
else {
p->nextarc = t; // 将新节点添加到链表末尾
p = t; // 更新指针p，使其指向新添加的节点
}
cntarcnum++; // 更新实际读取的边数
// 注释掉的代码是之前添加邻接点的另一种方式，与当前方式重复（调试中好像不能正常运行），因此被注释掉
/*
if (G->vertices[i].firstarc == NULL) {
G->vertices[i].firstarc = t;
}
else {
while (p->nextarc != NULL) {
p = p->nextarc;
}
p->nextarc = t;
}
*/
}
}
// 更新图的边数为实际读取的边数
G->arcnum = cntarcnum;
// 关闭文件
fclose(fp);
}
6. 查看图的信息
// 定义一个函数，用于监视（遍历并显示）图的邻接表表示
void WatchGraph(ALGraph G) {
ArcNode* p = NULL; // 定义一个指向边的指针，初始化为NULL
int key = 0; // 定义一个变量，用于存储当前正在查看的顶点编号，初始化为0
// 使用无限循环来不断显示顶点信息，直到用户选择退出
while (1) {
clearScreen(); // 清除屏幕，以便显示新的信息
// 获取当前顶点的第一条相邻边
p = G.vertices[key].firstarc;
// 显示图的基本信息和当前顶点的信息
printf("顶点数：%d 边数：%d \n", G.vexnum, G.arcnum);
printf("当前顶点：%d\n", key);
printf("与之相连的边(编号)：\n");
// 遍历当前顶点的所有相邻边，并打印相邻顶点的编号
for (; p != NULL; p = p->nextarc) {
printf("%d ", p->adjvex);
}
// 提示用户输入要跳转的顶点编号，或输入-1退出
printf("\n\n跳转顶点 退出：-1（0 <= k <= %d）：", G.vexnum - 1);
int k;
scanf("%d", &k); // 读取用户输入的顶点编号
// 再次清除屏幕，以防之前的输入或错误信息干扰接下来的显示
clearScreen();
// 根据用户输入进行处理
if (k == -1) {
// 如果用户输入-1，则退出循环
break;
}
else if (k < 0 || k >= G.vexnum) {
// 如果用户输入的编号无效，则显示错误信息，并继续显示当前顶点
printf("\n\n输入错误，当前顶点将不变\n\n");
continue; // 跳过循环的剩余部分，继续下一次迭代
}
else {
// 如果用户输入了有效的顶点编号，则更新当前顶点编号
key = k;
}
}
}
7. 有向图转换为无向图
// 将图转换为无向图
void ConvertUndirectedGraph(ALGraph G, ALGraph* UG) {
*UG = G;
// int arccnt = 0;
for (int i = 0; i < UG->vexnum; i++) {
ArcNode* p = UG->vertices[i].firstarc;
for (p; p != NULL; p = p->nextarc) {
// 查看两点是否相连
if (!VertexConnect(*UG, p->adjvex, i)) {
// 若没有相连，则连接上
ConnectAB(UG, p->adjvex, i);
UG->arcnum++;
// printf("%d to %d\n", p->adjvex, i);
}
}
}
// 从新计算边的数量
/*
for (int i = 0; i < UG->vexnum; i++) {
ArcNode* p = UG->vertices[i].firstarc;
for (p; p != NULL; p = p->nextarc) {
arccnt++;
}
}
*/
// 调整无向图中边的计数。
UG->arcnum = UG->arcnum / 2;
}
8.文件内容（参考）// 无向图
4 4
begin adfsgvb to 1 to 3 end
begin dca2 to 2 to 0 end
begin fdgfch to 3 to 1 end
begin afcf to 0 to 2 end
四、总代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#pragma warning(disable:4996);
// 清屏
void clearScreen() {
system("cls");
}
#define MaxVertexNum 100
// 定义顶点对应的数据类型，这里使用字符类型来表示顶点
typedef char VertexType;
// 定义边对应的数据类型，这里使用整数类型来表示边的权重（如果有的话）
typedef int EdgeType;
// 定义邻接表中的弧（边）节点结构
typedef struct ArcNode {
int adjvex; // adjvex 表示该弧所指向的顶点的位置（索引）
struct ArcNode* nextarc; // nextarc 指向下一条与该顶点相连的弧的指针，形成链表
// EdgeType data; // 边的数据（如权重）如果需要使用边的权重，取消注释
} ArcNode; // 弧节点结构定义结束
// 定义邻接表中的顶点节点结构
typedef struct VNode {
VertexType name[20]; // name 存储顶点的名称或标识符，这里假设最长为19个字符加上一个结束符
ArcNode* firstarc; // firstarc 指向该顶点的第一条相连的弧的指针，即该顶点的邻接链表的头指针
} VNode, AdjList[MaxVertexNum]; // VNode 和 AdjList 是同义类型，AdjList 是一个顶点数组类型，其大小由 MaxVertexNum 决定
// 定义图的结构，使用邻接表表示
typedef struct {
int vexnum, arcnum; // vexnum 表示图的顶点数，arcnum 表示图的边数
AdjList vertices; // vertices 是邻接表，存储了图的所有顶点及其邻接链表
} ALGraph;
// 初始化图的邻接表表示的函数
void InitALGraph(ALGraph* G) {
// 初始化图的边数为0
G->arcnum = 0;
// 初始化图的顶点数为0
G->vexnum = 0;
// 遍历顶点数组，初始化每个顶点的邻接链表为空（即每个顶点的 firstarc 指针指向 NULL）
for (int i = 0; i < MaxVertexNum; i++) {
G->vertices[i].firstarc = NULL;
}
}
// 判断在有向图 G 中，顶点 a 是否有一条直接指向顶点 b 的边
bool VertexConnect(ALGraph G, int a, int b) {
// 从顶点 a 的邻接链表的头指针开始遍历
ArcNode* p = G.vertices[a].firstarc;
// 遍历顶点 a 的所有邻接顶点
for (; p != NULL; p = p->nextarc) {
// 如果当前邻接顶点的位置（索引）等于 b，则返回 true，表示 a 指向 b
if (p->adjvex == b) {
return true;
}
}
// 如果遍历完所有邻接顶点都没有找到指向 b 的边，则返回 false
return false;
}
// 将图中顶点 a 与顶点 b 相连
void ConnectAB(ALGraph* G, int a, int b) {
ArcNode* p, * t; // 声明两个指针，p 用于遍历，t 用于存储新创建的邻接点
// 初始化指针 p，指向顶点 a 的首条邻接边
p = G->vertices[a].firstarc;
// 为新邻接点分配内存
// 创建新的邻接点
t = (ArcNode*)malloc(sizeof(ArcNode)); // 分配内存给新节点
// 检查内存分配是否成功
if (t == NULL) {
printf("空间不足\n"); // 打印错误信息
exit(1); // 内存分配失败，退出程序
}
// 设置新邻接点的信息
t->adjvex = b; // 设置新节点的目标顶点索引为 b
t->nextarc = NULL; // 新节点为链表末尾，nextarc 指向 NULL
// 若顶点 a 无邻接边，则新边为首条边
if (p == NULL) {
G->vertices[a].firstarc = t; // 将新节点设置为顶点 a 的首条邻接边
return; // 添加完成，直接返回
}
// 若顶点 a 有邻接边，则将新边添加到邻接链表末尾
// 将 p 调整到最后一条边
while (p->nextarc != NULL) { // 遍历至链表末尾
p = p->nextarc; // 移动指针至下一条边
}
// 将新边添加到顶点 a 的邻接链表末尾
p->nextarc = t; // 将链表的最后一个节点的 nextarc 指向新节点
}
// 通过用户输入创建图
void StructGraph(ALGraph* G) {
// 初始化数据
G->arcnum = 0;
G->vexnum = 0;
// 假设 MaxVertexNum 已经在其他地方定义
printf("请输入图的总顶点数(<=%d) : ", MaxVertexNum);
scanf("%d", &G->vexnum);
if (G->vexnum > MaxVertexNum || G->vexnum <= 0) {
printf("图的顶点数输入错误!\n");
exit(1);
}
// 初始化顶点数组
for (int i = 0; i < G->vexnum; i++) {
G->vertices[i].firstarc = NULL;
printf("\n请输入第 %d 顶点的名字: ", i);
scanf("%s", G->vertices[i].name); // 确保 name 数组足够大以存储输入
int key; // 将 key 的声明移到循环内部
ArcNode* p = G->vertices[i].firstarc;
while (1) {
clearScreen();
printf("请输入顶点： %s(%d) 将连接的点 \n(退出：-1； 输入限制： 0 <= num < %d) : ",
G->vertices[i].name, i, G->vexnum - 1);
scanf("%d", &key);
if (key == -1) break;
if (key < 0 || key >= G->vexnum) { // 修改条件，确保 key 在有效范围内
printf("输入顶点信息错误\n\n");
continue;
}
// 检查两点是否已经相连或者是否是与自身相连
if (VertexConnect(*G, i, key) || key == i) {
printf("此边已连接!!\n\n");
continue; // continue 会跳过后面的代码直接回到 while 循环的开始
}
// 创建新的邻接点
ArcNode* t = (ArcNode*)malloc(sizeof(ArcNode));
if (t == NULL) {
printf("空间不足\n");
exit(1);
}
t->adjvex = key;
t->nextarc = NULL;
// 将新的邻接点添加到链表中
if (p == NULL) {
G->vertices[i].firstarc = t;
p = t;
}
else {
p->nextarc = t;
p = t;
}
G->arcnum++;
printf("该边添加成功\n\n");
}
}
}
// 将邻接表表示的图写入文本文件
void WriteALGraph(ALGraph* G) {
// 打开文件用于写入，如果文件打开失败则打印错误信息并退出程序
FILE* fp = fopen("Graph.txt", "w");
if (fp == NULL) {
printf("Graph.txt 文件打开失败！\n");
exit(1); // 退出程序，返回错误码1
}
// 将图的顶点数和边数写入文件
fprintf(fp, "%d %d\n", G->vexnum, G->arcnum);
// 遍历每个顶点
for (int i = 0; i < G->vexnum; i++) {
// 写入 "begin" 标记，表示一个顶点的邻接表开始
fprintf(fp, "begin ");
// 写入顶点的名称，假设名称不会超过20个字符，并使用空格填充至20个字符宽度
fprintf(fp, "%20s ", G->vertices[i].name);
// 获取当前顶点的第一个邻接点
ArcNode* p = G->vertices[i].firstarc;
// 遍历当前顶点的所有邻接点
while (p != NULL) {
// 写入 "to" 标记和邻接点的索引
fprintf(fp, "to %d ", p->adjvex);
// 如果弧有数据，可以取消以下行的注释，并写入弧的数据
// fprintf(fp, "arcdata %d", p->data);
// 移动到下一个邻接点
p = p->nextarc;
}
// 写入 "end" 标记，表示一个顶点的邻接表结束
fprintf(fp, "end\n");
}
// 关闭文件
fclose(fp);
// 打印成功信息
printf("写入成功\n");
}
void ReadGrcph(ALGraph* G) {
// 打开文件用于读取，如果文件打开失败则打印错误信息并退出程序
FILE* fp = fopen("Graph.txt", "r");
if (fp == NULL) {
printf("Graph.txt 文件打开失败！\n");
exit(1); // 退出程序，返回错误码1
}
// 初始化图G
InitALGraph(G);
int cntarcnum = 0; // 用于记录实际读取的边数
// 读入顶点数和边数（注意：这里读取的边数可能会被后续的实际边数覆盖）
fscanf(fp, "%d %d", &G->vexnum, &G->arcnum);
// 遍历每个顶点，读取其邻接信息
for (int i = 0; i < G->vexnum && !feof(fp); i++) {
char temps[20];
fscanf(fp, "%s", temps);
// 检查是否为"begin"标记，如果不是则报错并退出
if (strcmp(temps, "begin") != 0) {
printf("文件信息错误！！！\n");
fclose(fp);
exit(1);
}
// 读取顶点名称
fscanf(fp, "%s", G->vertices[i].name);
ArcNode* p = G->vertices[i].firstarc; // 指向当前顶点的首条邻接边
// 读取当前顶点的所有邻接信息，直到遇到"end"标记
while (1) {
fscanf(fp, "%s", temps);
if (strcmp(temps, "end") == 0) {
break; // 遇到"end"标记，结束当前顶点的邻接信息读取
}
else if (strcmp(temps, "to") != 0) {
// 如果不是"to"标记，则报错并退出
printf("文件信息错误！！！\n");
fclose(fp);
exit(1);
}
int key = 0; // 用于存储邻接顶点的索引
fscanf(fp, "%d", &key); // 读取邻接顶点的索引
// 检查索引的有效性，避免越界和自环
if (key < 0 || key >= G->vexnum) {
printf("文件信息错误！！！\n");
fclose(fp);
exit(1);
}
// 检查两点是否已经相连或者是否是与自身相连，如果是则跳过
if (VertexConnect(*G, i, key) || key == i) {
continue; // 跳过当前循环迭代，继续检查下一个邻接信息
}
// 创建新的邻接点并添加到链表中
ArcNode* t = (ArcNode*)malloc(sizeof(ArcNode));
if (t == NULL) {
fclose(fp);
printf("空间不足\n");
exit(1);
}
t->adjvex = key; // 设置邻接点的目标顶点索引
t->nextarc = NULL; // 新节点为链表末尾，nextarc 指向 NULL
// 将新节点添加到当前顶点的邻接链表末尾
if (p == NULL) {
G->vertices[i].firstarc = t; // 如果当前顶点无邻接边，则新边为首条边
p = t; // 更新指针p，使其指向新添加的节点
}
else {
p->nextarc = t; // 将新节点添加到链表末尾
p = t; // 更新指针p，使其指向新添加的节点
}
cntarcnum++; // 更新实际读取的边数
// 注释掉的代码是之前添加邻接点的另一种方式，与当前方式重复（调试中好像不能正常运行），因此被注释掉
/*
if (G->vertices[i].firstarc == NULL) {
G->vertices[i].firstarc = t;
}
else {
while (p->nextarc != NULL) {
p = p->nextarc;
}
p->nextarc = t;
}
*/
}
}
// 更新图的边数为实际读取的边数
G->arcnum = cntarcnum;
// 关闭文件
fclose(fp);
}
// 定义一个函数，用于监视（遍历并显示）图的邻接表表示
void WatchGraph(ALGraph G) {
ArcNode* p = NULL; // 定义一个指向边的指针，初始化为NULL
int key = 0; // 定义一个变量，用于存储当前正在查看的顶点编号，初始化为0
// 使用无限循环来不断显示顶点信息，直到用户选择退出
while (1) {
clearScreen(); // 清除屏幕，以便显示新的信息
// 获取当前顶点的第一条相邻边
p = G.vertices[key].firstarc;
// 显示图的基本信息和当前顶点的信息
printf("顶点数：%d 边数：%d \n", G.vexnum, G.arcnum);
printf("当前顶点：%d\n", key);
printf("与之相连的边(编号)：\n");
// 遍历当前顶点的所有相邻边，并打印相邻顶点的编号
for (; p != NULL; p = p->nextarc) {
printf("%d ", p->adjvex);
}
// 提示用户输入要跳转的顶点编号，或输入-1退出
printf("\n\n跳转顶点 退出：-1（0 <= k <= %d）：", G.vexnum - 1);
int k;
scanf("%d", &k); // 读取用户输入的顶点编号
// 再次清除屏幕，以防之前的输入或错误信息干扰接下来的显示
clearScreen();
// 根据用户输入进行处理
if (k == -1) {
// 如果用户输入-1，则退出循环
break;
}
else if (k < 0 || k >= G.vexnum) {
// 如果用户输入的编号无效，则显示错误信息，并继续显示当前顶点
printf("\n\n输入错误，当前顶点将不变\n\n");
continue; // 跳过循环的剩余部分，继续下一次迭代
}
else {
// 如果用户输入了有效的顶点编号，则更新当前顶点编号
key = k;
}
}
}
// 将图转换为无向图
void ConvertUndirectedGraph(ALGraph G, ALGraph* UG) {
*UG = G;
// int arccnt = 0;
for (int i = 0; i < UG->vexnum; i++) {
ArcNode* p = UG->vertices[i].firstarc;
for (p; p != NULL; p = p->nextarc) {
// 查看两点是否相连
if (!VertexConnect(*UG, p->adjvex, i)) {
// 若没有相连，则连接上
ConnectAB(UG, p->adjvex, i);
UG->arcnum++;
// printf("%d to %d\n", p->adjvex, i);
}
}
}
// 从新计算边的数量
/*
for (int i = 0; i < UG->vexnum; i++) {
ArcNode* p = UG->vertices[i].firstarc;
for (p; p != NULL; p = p->nextarc) {
arccnt++;
}
}
*/
// 调整无向图中边的计数。
UG->arcnum = UG->arcnum / 2;
}
int main() {
ALGraph G;
InitALGraph(&G);
//StructGraph(&G);
//WriteALGraph(&G);
ReadGrcph(&G);
ConvertUndirectedGraph(G, &G);
//WatchGraph(G);
WriteALGraph(&G);
//WatchGraph(G);
return 0;
}