精华内容
下载资源
问答
  • 邻接矩阵和邻接表

    2020-07-05 19:30:41
    图的存储结构主要分两种,一种是邻接矩阵,...上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都

    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。

    1.邻接矩阵

    邻接矩阵的存储方式是用两个数组来表示图。一个一维数组储存图中顶点信息,一个二维数组储存图中的边或弧的信息。

    无向图

    这里写图片描述

    这里右图是把顶点作为矩阵内行和列的标头罗列出来。如果在两个顶点之间存在一条边,那么就把 1 放在这个位置上。如果边不存在,那么就赋值为 0。

    从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。

    从矩阵中很容易分析到图中信息:

    1)判断顶点之间是否有边很容易;

    2)要知道顶点的度,其实就是这个顶点在第i行(或第i列)的元素之和;

    3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点。

    有向图

    上图图右是一个有向图。有向图是看入度和出度的(顶点的入边数和出边数),例如V2,就有2个出边。列代表着顶点的入边,列的元素相加代表顶点的入度,而行则代表该顶点所有的出边,元素相加则为顶点的出度。假如V2->V1的这个关系要写到邻接矩阵,首先先找到V1的列,然后在对应V2行的位置写上一个1,就可以了。

    网络

    网络是一个带权图。邻接矩阵如下图:

    有两种表示方法,没有边的两个顶点,可以用0表示,也可以用最大值表示。

    2.邻接表

    邻接矩阵是不错的一种图存储结构,但是,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费。因此,找到一种数组与链表相结合的存储方法称为邻接表。

    邻接表的处理方法是这样的:
           1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。
           2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表(只管顶点的出边不管入边)。

    这里写图片描述

    从图中可以看出,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。

     

     

     

     

    展开全文
  • 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。 这个矩阵中,很容易知道图中...

    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。
    1.邻接矩阵
    图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。
    设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
    在这里插入图片描述
    看一个实例,下图左就是一个无向图。
    在这里插入图片描述

    从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。

    从这个矩阵中,很容易知道图中的信息。
    (1)要判断任意两顶点是否有边无边就很容易了;
    (2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;
    (3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;
    而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2,即第i行的各数之和。
    若图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
    在这里插入图片描述

    1.2 邻接表
    邻接矩阵是不错的一种图存储结构,但是,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费。因此,找到一种数组与链表相结合的存储方法称为邻接表。
    邻接表的处理方法是这样的:
    (1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。
    (2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。
    例如,下图就是一个无向图的邻接表的结构。
    这里写图片描述

    从图中可以看出,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。
    对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。如下图所示。
    这里写图片描述

    3.两者区别
    对于一个具有n个顶点e条边的无向图
    它的邻接表表示有n个顶点表结点2e个边表结点
    对于一个具有n个顶点e条边的有向图
    它的邻接表表示有n个顶点表结点e个边表结点
    如果图中边的数目远远小于n^2称作稀疏图,这是用邻接表表示比用邻接矩阵表示节省空间;
    如果图中边的数目接近于n^2,对于无向图接近于n*(n-1)称作稠密图,考虑到邻接表中要附加链域,采用邻接矩阵表示法为宜。

    展开全文
  • 图的邻接矩阵和邻接表的比较

    万次阅读 多人点赞 2018-08-16 15:39:11
    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。1.邻接矩阵 图的邻接矩阵存储方式是用两...上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即矩阵的左上角到...

    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。
    1.邻接矩阵
    图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。
    设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
    这里写图片描述
    看一个实例,下图左就是一个无向图。
    这里写图片描述
    从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。
    从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。
    从这个矩阵中,很容易知道图中的信息。
    (1)要判断任意两顶点是否有边无边就很容易了;
    (2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;
    (3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;
    而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2,即第i行的各数之和。
    若图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:这里写图片描述

    1.2 邻接表
    邻接矩阵是不错的一种图存储结构,但是,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费。因此,找到一种数组与链表相结合的存储方法称为邻接表。
    邻接表的处理方法是这样的:
    (1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。
    (2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。
    例如,下图就是一个无向图的邻接表的结构。
    这里写图片描述
    从图中可以看出,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。
    对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。如下图所示。
    这里写图片描述
    3.两者区别
    对于一个具有n个顶点e条边的无向图
    它的邻接表表示有n个顶点表结点2e个边表结点
    对于一个具有n个顶点e条边的有向图
    它的邻接表表示有n个顶点表结点e个边表结点
    如果图中边的数目远远小于n2称作稀疏图,这是用邻接表表示比用邻接矩阵表示节省空间;
    如果图中边的数目接近于n2,对于无向图接近于n*(n-1)称作稠密图,考虑到邻接表中要附加链域,采用邻接矩阵表示法为宜。

    展开全文
  • 图的邻接表和邻接矩阵

    千次阅读 2017-03-10 13:47:37
    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。 1.邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,... 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵

    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。
    1.邻接矩阵
    图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。
    设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
    这里写图片描述
    看一个实例,下图左就是一个无向图。
    这里写图片描述
    从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。
    从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。
    从这个矩阵中,很容易知道图中的信息。
    (1)要判断任意两顶点是否有边无边就很容易了;
    (2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;
    (3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;
    而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2,即第i行的各数之和。
    若图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:这里写图片描述

    1.2 邻接表
    邻接矩阵是不错的一种图存储结构,但是,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费。因此,找到一种数组与链表相结合的存储方法称为邻接表。
    邻接表的处理方法是这样的:
    (1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。
    (2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。
    例如,下图就是一个无向图的邻接表的结构。
    这里写图片描述
    从图中可以看出,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。
    对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。如下图所示。
    这里写图片描述
    3.两者区别
    对于一个具有n个顶点e条边的无向图
    它的邻接表表示有n个顶点表结点2e个边表结点
    对于一个具有n个顶点e条边的有向图
    它的邻接表表示有n个顶点表结点e个边表结点
    如果图中边的数目远远小于n2称作稀疏图,这是用邻接表表示比用邻接矩阵表示节省空间;
    如果图中边的数目接近于n2,对于无向图接近于n*(n-1)称作稠密图,考虑到邻接表中要附加链域,采用邻接矩阵表示法为宜。

    展开全文
  • 一、图的存储结构1.1 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中... 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即矩阵的左...
  • 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组... 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij= aji。即矩阵的左上角到右下角...
  • 其实证明也不难,我们从矩阵乘法可以看出一点端倪:c[i][j]=c[i][j]+a[i][k]*b[k][j].这个k就是位于i和j之间的点,枚举k,求和就是方案数。这个性质我忘了叫做什么了,只是在学习离散的时候听老师讲了...
  • 地址点击打开链接这个题目,需要有一点性质了解,邻接矩阵我认为可以把它叫做一步可达矩阵,也就是说我们建立一个邻接矩阵可以直接用M[a][b]看出走一步就可以完成a到b的路线有多少条路线。然后如果将这个矩阵自乘...
  • 上图中,我们可以看出,如果你认识6个人,是很有可能认识其他所有人的。但是,对于全球的30亿的互联网人来说,你真的可以全部认识吗?大多数同学此刻一定是定神一想,这还用问?你是傻子吗?这一定不可能呀。但是...
  • 邻接

    2020-04-05 10:18:13
    我们都知道在存储稠密图时候,邻接表比邻接矩阵效率高,因为邻接矩阵中在存储稀疏图时候,很多没用连接的点既占了...// 专业书上叫做存储当前边的下一条边,但是我觉得理解为上一条边好像更好,过会图中可以看出...
  • ACM菜鸟入门培训4

    2019-11-12 09:06:12
    第三讲 邻接矩阵和邻接表 图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。 1.邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。...上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n...
  • dfs与dfs遍历图节点

    2020-06-14 13:33:30
    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。 1.1 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵...上面可以看出,无向图的边数组是一个
  • Graph(store and create)

    2015-05-12 22:01:47
    图的存储结构 1、 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一...上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即矩阵
  • 一、图的存储结构 1.1 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接... 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵...
  • 数据结构图的定义

    千次阅读 2013-11-23 09:57:00
    一、图的存储结构 1.1 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点...上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即矩阵的
  •       一....【1.1 邻接矩阵】 ...图的邻接矩阵存储方式是用两个数组来表示图。...一个一维数组存储顶点信息,一个二维数组...上面可以看出,无向图的边数组是一个对称矩阵。 所谓对称矩阵就是n阶矩阵的元满足a...
  • 图的存储结构及遍历

    2015-06-09 11:19:00
    一、图的存储结构 1.1 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组... 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足ai...
  • 一、图的存储结构 1.1 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。... 上面可以看出,无向图...
  • 图的存储结构

    2017-08-05 19:42:58
    1.1 邻接矩阵  图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组... 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即...
  • 一、图的存储结构 1.1 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组... 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足ai...
  • 上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij= aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。 这个矩阵中,很容易知道图中...

空空如也

空空如也

1 2 3 4
收藏数 76
精华内容 30
热门标签
关键字:

从邻接矩阵可以看出