一、概念
说到图，大多数人立刻会想到一幅画，一张地图……但是我们今天所说的图是一种数据结构。
图是由顶点（vertice）集和边（edge）集组成的，图又分为有向图、无向图、带权图，下图所示的是一个有向图
有向图：顾名思义就是具有方向的图，如上所示，顶点1指向顶点2，但是顶点2无法指向顶点1。
无向图：就是不区分方向的图，顶点1可以指向顶点2,同时顶点2也可以指向顶点1。
带权图：表示边带有权重的图，如下图所示
另外图中还包含路径这个概念，如上图v1到v7的路径有
- v1->v2->v4->v7
- v1->v2->v4->v5->v7
- v1->v2->v5->v7
- v1->v4->v7
- v1->v4->v5->v7
以上这几种，如果要计算最短路径则需要将权重考虑在内，很显然v1->v7的最短路径是第四种方案，值为5。
二、图的表示方式
在简单介绍完图的基本概念以后，我们再讨论图的表示方式。
第一种表示方式：邻接矩阵。
邻接矩阵是表示图中顶点和顶点之间关系的矩阵，我们将如下的图（非带权图）转换成邻接矩阵。
我们定义：若顶点v1可以指向v2，则矩阵中的值标记为1，否则为0，如下图便是得到的邻接矩阵
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/122470.html