数据结构-图-领接表存储

一、了解图的领接表存储

1、定义与结构

1. 定义：邻接表是图的一种链式存储结构，它通过链表将每个顶点与其相邻的顶点连接起来。

2. 结构：

   • 顶点表：通常使用一个数组来存储图的顶点信息，数组的每个元素对应一个顶点，元素的内容可以是顶点的标识符或值，以及一个指向该顶点邻接链表的指针。
   • 邻接链表：对于图中的每个顶点，创建一个链表，链表中存储了与该顶点相邻的其他顶点。链表中的每个节点通常包含两个字段：邻接点域（指示与当前顶点相邻的顶点在图中的位置）和链域（指示下一条邻接边的节点）。

2、性质与特点

1. 节省空间：对于稀疏图，邻接表能够节省大量的内存空间，因为它只存储实际存在的边，而不需要像邻接矩阵那样为所有可能的边分配空间。
2. 灵活性强：邻接表易于增加和删除顶点及其邻接边，因为链表结构允许动态调整。
3. 查找效率高：在查找与某个顶点相邻的所有顶点时，只需要遍历该顶点的邻接链表，而不需要遍历整个矩阵，从而提高了查找效率。

3、构建与存储

1. 构建方法：

   • 确定图的顶点数量和边的关系。
   • 创建一个顶点表数组，数组的每个元素对应一个顶点，并初始化其邻接链表为空。
   • 根据图的边关系，将每条边对应的两个顶点添加到彼此的邻接链表中。

2. 存储：

   • 顶点表数组通常存储在内存中，以便快速访问。
   • 邻接链表使用动态内存分配来存储，以适应不同顶点的邻接边数量。

4、应用与限制

1. 应用：

   • 社交网络中的用户关系可以用无向图表示，每个用户是一个顶点，好友关系是一条边。使用邻接表存储后，可以方便地查找某个用户的好友列表或共同好友等信息。
   • 在图的遍历算法（如广度优先搜索BFS和深度优先搜索DFS）中，邻接表提供了一种高效的访问相邻顶点的方式。
   • 邻接表也适用于求解最短路径、网络流问题等图论算法。

2. 限制：

   • 在查找特定的边时，可能需要遍历整个邻接表，相对较慢，特别是对于稠密图。
   • 对于有向图，如果需要同时获取顶点的入度和出度，则需要分别维护邻接表和逆邻接表，这会增加存储空间的开销。

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) {// 初始化图的边数为0G->arcnum = 0;// 初始化图的顶点数为0G->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 指向 bif (p->adjvex == b) {return true;}}// 如果遍历完所有邻接顶点都没有找到指向 b 的边，则返回 falsereturn 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; // 设置新节点的目标顶点索引为 bt->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}// 初始化图GInitALGraph(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; // 定义一个指向边的指针，初始化为NULLint 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) {// 初始化图的边数为0G->arcnum = 0;// 初始化图的顶点数为0G->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 指向 bif (p->adjvex == b) {return true;}}// 如果遍历完所有邻接顶点都没有找到指向 b 的边，则返回 falsereturn 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; // 设置新节点的目标顶点索引为 bt->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}// 初始化图GInitALGraph(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; // 定义一个指向边的指针，初始化为NULLint 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;
}