邻接表 订阅
邻接表,存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。 [1] 展开全文
邻接表,存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。 [1]
信息
外文名
adjacency list
作    用
存储图
分    类
顺序分配和链式分配
中文名
邻接表
性    质
存储结构
邻接表简介
图的邻接表存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示,表结点存放的是邻接顶点在数组中的索引。对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。 [1]  邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器(n个顶点建立n个容器),第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。在有向图中,描述每个点向别的节点连的边(点a->点b这种情况)。在无向图中,描述每个点所有的边(点a-点b这种情况)与邻接表相对应的存图方式叫做边集表,这种方法用一个容器存储所有的边。工业上有很多非常好的图库的实现,例如C++的boost graph库.如果可以,尽量用这些库,这样可以大大提高你的效率。
收起全文
精华内容
下载资源
问答
  • 本文实例为大家分享了C++有向图的邻接表表示,供大家参考,具体内容如下 一、思路: 有向图的插入有向边、删除边、删除顶点和无向图的有区别。其他的和无向图的类似。 1.插入有向边 只需要插入边就行,不需要插入...
  • 本文实例为大家分享了C++实现邻接表顶点的删除代码,供大家参考,具体内容如下 这里的边是无向边 删除顶点v时,要找到顶点v的邻接顶点w,把w中指向v的边删除掉,再删除边(v,w)。循环这个过程,直到把和顶点v有关的...
  • 领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
  • 主要介绍了java实现图的邻接表存储结构的两种方式及实例应用详解,邻接表构建图是必须需要一个Graph对象,也就是图对象!该对象包含属性有:顶点数、边数以及图的顶点集合,需要的朋友可以参考下
  • 主要为大家详细介绍了C++实现有向图邻接表的构建,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历
  • 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
  • 图的邻接矩阵和邻接表实现, 深度搜索, 广度搜索, Dijstra最短路径
  • 图的邻接表 邻接矩阵表示的迪杰斯特拉算法 普里姆算法 克鲁斯卡尔算法 用c++实现 codeblocks编译通过
  • 主要介绍了邻接表无向图的Java语言实现完整源码,具有一定借鉴价值,需要的朋友可以参考下。
  • 存储结构:邻接表; 实现功能:广度遍历; 为发布的博客的代码实现
  • 本文实例为大家分享了C++数据结构之实现邻接表的具体代码,供大家参考,具体内容如下 一、图的邻接表实现 1.实现了以顶点顺序表、边链表为存储结构的邻接表; 2.实现了图的创建(有向/无向/图/网)、边的增删操作、...
  • 在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?
  • C语言采用邻接表结构实现克鲁斯卡尔算法。 也可以在相应github上下载,https://github.com/Sunnk/Data-Structure,其中Kruskal文件夹中即为克鲁斯卡尔算法,可用vs打开
  • 1.生成一个100个点,3000条边的有向随机图,任选一点作为源点,计算S到其他节点的距离。(注:图用邻接链表存储) 2.将实验一中的有向图变为DAG图。(从中去掉一些边,不允许用递归) 计算上述DAG图中的最长路径。
  • 数据结构 c++ 图的最短路径问题 (邻接表) 数据结构 c++ 图的最短路径问题 (邻接表)
  • 邻接表

    万次阅读 多人点赞 2019-08-27 17:06:30
    邻接表 我们发现,当图中的边数相对于顶点较少时,邻接矩阵是对存储空间的极大浪费。我们可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。回忆树结构的孩子表示法,将结点存入数组,并对结点的孩子进行...

    邻接表

    我们发现,当图中的边数相对于顶点较少时,邻接矩阵是对存储空间的极大浪费。我们可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。回忆树结构的孩子表示法,将结点存入数组,并对结点的孩子进行链式存储,不管有多少孩子,也不会存在空间浪费问题。

    应用这种思路,我们把这种数组与链表相结合的存储方法称为邻接表(Adjacency List)。

    邻接表的处理办法是这样。

    1)  图中顶点用一个一维数组存储,当然也可以用单链表来存储,不过用数组可以较容易的读取顶点信息,更加方便。另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。

    2)  图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点vi的边表,有向图则称为以vi为弧尾的出边表。

    下图是一个无向图的邻接表结构:

    从图中我们知道,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息。

    firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。

    边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指

    向边表中下一个结点的指针,比如v1顶点与v0、v2互为邻接点,则在v1的边表中,adjvex分别为v0的0和v2的2.

    如果想知道某个顶点的度,就去查找这个顶点的边表中结点的个数。

    若要判断顶点vi和vj是否存在边,只需要测试顶点vi的边表adjvex中是否存在结点vj的下标就行了。

    若求顶点的所有邻接点,其实就是对此顶点的边表进行遍历,得到的adjvex域对应的顶点就是邻接点。

    有向图的邻接表中顶点vi的边表是指以vi为弧尾的弧来存储的,这样很容易就可以得到每个顶点的出度。

    有时为了便于确定顶点的入度或以顶点为弧头的弧,可以建立一个有向图的逆邻接表,即对每个顶点vi都建立

    一个链接为vi为弧头的表。如下图所示:

    此时我们很容易就可以算出某个顶点的入度或出度是多少,判断两顶点是否存在弧也很容易实现。

    对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可,如下图所示:

    //结点的定义
    typedef char VertexType;
    typedef int EdgeType;
    #define MaxVex 100
    typedef struct EdgeNode //边表结点
    {
        int adjvex; //邻接点域,存储邻接顶点对应的下标
        EdgeType weight; //用于存储权值,对于非网图可以不需要
        struct EdgeNode *next; //链域,指向下一个邻接点
    }EdgeNode;
    typedef struct VertexNode  //顶点表结点
    {
        VertexType data;  //顶点域,存储顶点信息
        EdgeNode *firstedge; //边表头指针
    }VertexNode,AdjList[MaxVex];
     
    typedef struct
    {
        AdjList adjList;
        int numVertexes,numEdges; //图中当前顶点数和边数
    }GraphAdjList;
    //建立无向图的邻接表结构
    void CreateALGraph(GraphAdjList *G)
    {
        int i,j,k;
        EdgeNode *e;
        printf("输入顶点数和边数:\n");
        scanf("%d,%d",&G->numVertexes,&G->numEdges);
        for(i=0;i<G->numVertexes;i++)
        {
            scanf(&G->adjList[i].data); //输入顶点信息
            G->adjList[i].firstedge = NULL; //将边表置为空表
        }
        for(k=0;k<G->numEdges;k++)
        {
            printf("输入边(vi,vj)上的顶点序号:\n");
            scanf("%d,%d",&i,&j);
            e = (EdgeNode *)malloc(sizeof(EdgeNode)); //向内存申请空间,生成边表结点
            e->adjvex = j; //邻接序号为j
            e->next = G->adjList[i].firstedge;
            G->adjList[i].firstedge = e; //将当前顶点的指针指向e
     
            e = (EdgeNode *)malloc(sizeof(EdgeNode));
            e->adjvex = i; //邻接序号为i
            e->next = G->adjList[j].firstedge;
            G->adjList[j].firstedge = e; 
        }
    }

     
     

    展开全文
  • 2018及数据结构实验课报告目 录 1 基于顺序存储结构的线性表实现 3 1.1 问题描述 3 1.2 系统设计 6 1.2.1 数据物理结构 6 1.3 系统实现 13 ...4基于邻接表的图实现 68 ...附录D 基于邻接表的图实现程序清单 150
  • 邻接表存储的图

    2019-08-25 14:20:25
    1、 定义邻接表存储的图类。 2、 实验验证如下算法的正确性、各种功能及指标: 1)创建一个邻接表存储的图; 2)返回图中指定边的权值; 3)返回图中某顶点的第一个邻接顶点; 4)返回图中某顶点关于另一个顶点的下...
  • 邻接表存储的图的DFS,BFS遍历。文档描述: http://blog.csdn.net/qq_16912257/article/details/45848935
  • 一次上机练习——有向图的邻接矩阵转化为邻接表并存储顶点大于50的值 小渣渣写的和大家一起学习进步
  • 本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法。分享给大家供大家参考。具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6...
  • 一个完整的有向图课程设计,一共含有20个方法。分享给大家一起学习。
  • NULL 博文链接:https://touch-2011.iteye.com/blog/1070798
  • 图的C++的邻接表和邻接矩阵完整实现,功能齐全,运行界面效果好
  • 天津理工大学实验报告 学院系名称 计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009 级 1 班 实验项目 实验四 图的深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 实验时间 2011 年 5 月...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,040
精华内容 31,216
关键字:

邻接表