最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 【数据结构-图(一)】什么是图

    一、什么是“”(Graph)

    • 表示“多对多”的关系
    • 包含
      •  一组顶点:通常用 V (Vertex) 表示顶点集合
      • 一组边:通常用 E (Edge) 表示边的集合
        • 无向边:(v, w)
        • 有向边:<v, w>
        • 不考虑重边和自回路

    二、抽象数据类型定义

    • 类型名称:图(Graph
    • 数据对象集:G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成。
    • 操作集:

     

    三、邻接矩阵 

    1. 邻接矩阵G[N][N]——N个顶点从0到N-1编号,若存在边,则 G[i][j] = 1,否则为0。

    1. 对于无向图的存储,怎样可以省一半空间?

    2. 邻接矩阵
      用一个长度为N(N+1)/2的1维数组A存储{G00,G10,G11,……,Gn-1,0,…,Gn-1 n-1},则Gij在A中对应的下标是:( i*(i+1)/2 + j )对于网络,只要把G[i][j]的值定义为边<vi,vj>的权重即可。

    1. 如,若查看是否有v6到v3的边,则查看G[6*7/2 + 3] = G[24]即可。

    四、邻接矩阵性质

        优点:邻接矩阵 —— 有什么好处?

    • 直观、简单、好理解

    • 方便检查任意一对顶点间是否存在边

    • 方便找任一顶点的所有“邻接点”(有边直接相连的顶点)

    • 方便计算任一顶点的“度”(从该点发出的边数为“出度”,指向该点的边数为“入度”)

      • 无向图:对应行(或列)非0元素的个数

      • 有向图:对应行非0元素的个数是“出度”;对应列非0元素的个数是“入度”

        缺点:邻接矩阵 —— 有什么不好?

    • 浪费空间 —— 存稀疏图(点很多而边很少)有大量无效元素。对稠密图,特别是完全图,还是很合算的)

    • 浪费时间 —— 统计稀疏图中一共有多少条边

    五、邻接表

        G[N]为指针数组,对应矩阵每行一个链表,只存非0元素 。

    六、邻接表性质

    • 方便找任一顶点的所有“邻接点”
    • 节约稀疏图的空间
      • 需要N个头指针 + 2E个结点(每个结点至少2个域)
    • 方便计算任一顶点的“度”?
      • 对无向图:是的
      • 对有向图:只能计算“出度”;需要构造“逆邻接表”(存指向自己的边)来方便计算“入度”
    • 方便检查任意一对顶点间是否存在边?
      • No
    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 【数据结构-图(一)】什么是图

    发表评论

    • 52会员总数(位)
    • 310资源总数(个)
    • 31本周发布(个)
    • 1 今日发布(个)
    • 331稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情