目录

一、图的基本概念

1、完全图

2、顶点的度 

3、简单路径、简单回路

4、连通图 （强连通图）

 5、生成树

 二、图的存储结构

1、邻接矩阵法（数组表示法） n×n

 2、有权图（网）的邻接矩阵表示法

 3、采用邻接矩阵表示法创建无向网

一、图的基本概念

1、有向图   记为

G = (V,E)

V = {v1,v2,v3,v4}

E = {, , , }

2、无向图  记为 (v,w) 或(w,v) 

G = (V,E)

V = {v1,v2,v3,v4,v5}

E = {(v1,v3), (v1,v4), (v2,v3), (v2,v5), (v3,v4), (v3,v5), (v4,v5)}

1、完全图

1、无向图中任意两点之间都存在边，称为无向完全图。

     无向完全图具有 n(n-1) / 2 条边。

 2、有向图中任意两点之间都存在方向向反的两条弧，称为有向完全图。

       有向完全图具有 n(n-1) 条弧

2、顶点的度 

与该顶点相关联的边的数目，记为TD(v)

无向图：顶点的边数为度，度数和 = 顶点边数 × 2

有向图：顶点的度 = 该顶点的入度+出度

全部顶点入度之和 = 全部顶点出度之和 = 等于边数

顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v)

顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)

3、简单路径、简单回路

顶点不重复出现的路径称为简单路径

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或简单环

4、连通图 （强连通图）

若图中任意两顶点都连通，同此图为连通图。

无向图中的极大连通子图称为连通分量。 

 

           连通图                                非连通图

在有向图中，两顶点两个方向都有路径，两顶点称为强连通。

强连通：既可以从a走到b，也可以从b走到a

若任一顶点都是强连通的，称为强连通图。

有向图中极大强连通子图为有向图的强连通分量。

极大强连通子图：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。

 eg：非强连通图中v0可以走到v1，但v1走不到v0

         强连通图                         非强连通图

 5、生成树

极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。
生成树：包含无向图G 所有顶点的极小连通子图。

生成森林：对非连通图，由各个连通分量的生成树的集合。       

若图中有n个顶点，则生成树有n-1条边

 二、图的存储结构

1、邻接矩阵法（数组表示法） n×n

一维数组存储图中顶点信息

二维数组（称为邻接矩阵）存储图中的边的信息

无向图：求某个顶点的度，即计算此顶点在邻接矩阵中第i行（或第i列）的元素之和

               无向图的邻接矩阵是对称的

有向图：求某个顶点的出度 = 此顶点所在行的元素之和

              求某个顶点的入度 = 此顶点所在列的元素之和

              某顶点的度 = 第i行元素之和 + 第i列元素之和

 2、有权图（网）的邻接矩阵表示法

 3、采用邻接矩阵表示法创建无向网