Advertisement

使用C/C++构建无向图的邻接表表示(DFS和BFS)

阅读量:

邻接表

构建一个采用邻接表表示法的无向图结构

算法步骤如下:

  1. 按照输入的顺序,依次将各个顶点信息存入顶点表中,并确保每个表头节点的指针域初始化为NULL。
  2. 构建邻接表(假设顶点信息具有唯一性)
    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)

还没有任何评论哟~