织梦建设两个网站 视频,php开发企业网站教程,网站页面布局名称,服装设计80%的人会转行一、了解图的领接表存储
1、定义与结构 定义#xff1a;邻接表是图的一种链式存储结构#xff0c;它通过链表将每个顶点与其相邻的顶点连接起来。 结构#xff1a; 顶点表#xff1a;通常使用一个数组来存储图的顶点信息#xff0c;数组的每个元素对应一个顶点#xff…一、了解图的领接表存储
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, V4V2的邻接链表包含V1, V3V3的邻接链表包含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 指针指向 NULLfor (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跳转顶点 退出-10 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 指针指向 NULLfor (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跳转顶点 退出-10 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;
}
