几种常用的图的存储方式

1.  方式一:邻接矩阵

            核心内容:利用二维数组实现图的存储

            结构分析:该图有3个顶点,分别为1、2、3,因此至少需要一个n行n列的二维数组,行坐标和列坐标都代表结点的编号,从1开始编号,分析以上有向图可以发现,有1->2,1->3,2->3三边,  以行坐标代表起点,纵坐标代表终点,两点之间如果有边标记为1,否则标记为0,如下表格所示

《几种常用的图的存储方式》

        注意:如果该图是无向图,那么 就有1->2,2->1,1->3,3->1,2->3,3->2六条边,因为对于无向图而言是双向可达的

《几种常用的图的存储方式》

 

2.  方式二:邻接表

        核心内容:利用数组+链表实现图的存储 

          结构分析:该图有4个顶点,分别为1、2、3、4,从1出发的边有1->2,1->3,1->4,从2出发的边有2->3,没有从3出发的边,从4出发的边有4->3,并且边与边之间有权重

《几种常用的图的存储方式》

        注意:有向图,链表只连接指出去的;无向图,凡是连接的都加入链表,例如1->2  2->1都需要加入链表,因为无向图是双向可达的 

 

 

3.  方式三:链式前向星

        核心内容:本质上是邻接表的数组表示(数组模拟链表)

        结构分析:该图有5个顶点,分别为1、2、3、4、5 从1出发的边有1->2,1->5,从2出发的边有2->3,从3出发的边有3->4,从4出发的边有4->5,没有从5出发的边,并且边与边之间有权重

《几种常用的图的存储方式》

    原文作者:小C哈哈哈
    原文地址: https://blog.csdn.net/xiaoxi_hahaha/article/details/116593083
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞