《算法笔记》图专题

一、图的定义与相关术语

图可以分为：

• 有向图：所有边都有方向，确定了顶点到顶点的指向；
• 无向图：所有边都是双向的，即无向边所连接的两个顶点可以相互到达。

顶点的度：和该顶点相连的边的条数；对有向图来说，顶点的出边条数为该顶点的出度，入边条数为入度。
权值：指顶点和边的量化属性，分别为点权、边权。

二、图的存储

图由顶点（Vertex）、边（Edge）组成，记号G（V,E）表示图G的顶点集为V，边集为E。

1、邻接矩阵

设图G(V,E)的顶点编号为0,1,2，，N-1，可以令二维数组G[N][N]的两维分别顶点编号，如果G[i][j]==1，说明顶点i和j之间有边，如果为0则无边。另外，如果存在边权，可令G[i][j]存放边权，不存在的边可设边权为0，-1或INF。
例如以下无向图的邻接矩阵为


虽然邻接矩阵写法简单，但是如果顶点数目太多，二维数组占据空间可能超出内存限制。所以邻接矩阵适用于顶点数目不超过1000的题目。<