数据结构与算法学习笔记 [复制链接]

表示“多对多关系”

包含：1）一组顶点

2）一组边

理解：比如地铁线路图就是一个典型的图结构

2、分类：

主要有无向图和有向图

无向图可以理解为临街两个顶点是无向的，即可以从A到B也可从B到A;

有向图则相反。

主要以矩阵表示，对于一个无向图，是一个沿轴对称矩阵

可以通过上图观察，对于一个完全图（就是任意一个点都能其他点），则上述邻接矩阵不浪费，否则就会出现空间浪费的情况

此时，便可以引申以数组存储图的方法：

邻接矩阵优点：

1）直观。简单、便于理解

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

）方便找出顶点邻接点

4）方便计算“度”

度的概念：

出度：从该点发出的边数

入度：指向该点的边数

显然对于无向图是对应行（列）非0元素个数

对有向图：行非0元素个数是出度。列非0元素是入度。

邻接矩阵缺点：

1）浪费空间

2）浪费时间

记：修炼内功，重温经典

数据结构中的线性表、链表、栈以及非常重要的树，已经重温完毕