使用C/C++构建无向图的邻接表表示(DFS和BFS)
发布时间
阅读量:
阅读量
邻接表
构建一个采用邻接表表示法的无向图结构
算法步骤如下:
- 按照输入的顺序,依次将各个顶点信息存入顶点表中,并确保每个表头节点的指针域初始化为NULL。
- 构建邻接表(假设顶点信息具有唯一性)
1 针对输入的一条边所涉及的两个顶点u和v,查找它们在顶点表中的对应位置i和j
2 分别为u和v创建新的边节点pu与pv
3 将这两个节点的adjvex域分别设置为j与i
4 将其插入到对应顶点u与v的边链表头部(采用头插法)
5 重复上述2.1至2.4步骤,直到所有边的信息处理完成
输入规范说明
输入内容由三个部分构成
第一部分包含两个整数n和m,分别用于表示图中顶点的数量以及边的数量
第二部分是由空格分隔开的n个字符,用于表示图中n个顶点的具体信息
第三部分则由m行数据组成,每一行数据均由空格分隔开的两个字符构成,用于表示图中某一条边所连接的两个顶点
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MVNum 10
typedef struct ArcNode {
int adjvex; // 该边的起始点位置(下标)
struct Arc
全部评论 (0)
还没有任何评论哟~
