图

https://www.bilibili.com/video/BV1hg411V7Bm?p=62

1）图的分类

完全图

在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图。

无向图完全图

在有向图中，若每对顶点之间都有两条有向边相连接，则称该图为完全图。

有向图完全图

问题：n个顶点的无向图和有向图的完全图的边的个数为多少？

无向图

n个顶点：

顶点编号	边统计	参与的边
1	顶点1和顶点2 顶点1和顶点3 顶点1和顶点4 …… 顶点1和顶点n	n-1
2	顶点2和顶点3 顶点2和顶点4 …… 顶点2和顶点3 顶点2和顶点n	n-2
n-1	顶点n-1和顶点n	1
n	0

n-1，n-2，……，1，0

等差数列求和：(n-1+0)×n÷2=(n-1)×n÷2

有向图：

参考无线图，因为有向图两个顶点之间的线是两条，所以就是(n-1)×n

连通图

连通图：指任意两个顶点之间都有一个路径相连。

连通图与完全图不同的是：完全图中，任意两个顶点一定有至少一条边直接相连；而连通图中两个顶点之间的路径可以是间接相连的。

在有向图中，如果可以直接满足任意两个顶点之间都有一个路径相连的条件的叫做强连通图；如果不计较方向可以直接满足任意两个顶点之间都有一个路径相连的条件的叫做弱连通图。

2）图的转换：无向图转邻接矩阵

用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素R_ij定义为：

比如

矩阵R₁中R₁₂=1就表示顶点1到顶点2的边；

矩阵R₁中R₂₁=1就表示顶点2到顶点1的边（和R₁₂描述的是同一条边）；

矩阵R₁中R₂₅=0就表示顶点2到顶点5的没有路径，没有边；

无向图转换的邻接矩阵为对称矩阵。

满足R_ij=R_ji的矩阵叫做对称矩阵。

出度：看行，一个顶点连到其他顶点

入度：看列，其他顶点连到当前顶点

https://www.bilibili.com/video/BV1hg411V7Bm?p=63

2）图的转换：有向图转邻接矩阵

与有向图的转换方式相同。

有向图中，一个顶点指向另一个顶点的边又叫做弧；

R_ij=0或∞表示顶点i到顶点j没有弧的存在；

R_ij=1表示顶点i到顶点j有弧的存在；

有向图中度分入度和出度：其他顶点指向自己的弧的和自己指向其他顶点的弧；

比如顶点V₁，看第1行，有6、1、50，我们就说顶点V₁的出度为3；看第1列，没有有效值，我们就说顶点V₁的入度为0。

再比如顶点V₅，看第5行，有38、24，我们就说顶点V₅的出度为2；看第5列，有6、12、1，我们就说顶点V₅的入度为3。

从行看出度，从列看入度。

2）图的转换：有向图转邻接链表

首先把每个顶点的邻接顶点用链表表示出来，然后用一个以为数组来顺序存储上面没个链表的头指针。

比如

V₁就是有到V₂的弧值为6，到V₄的弧值为1，到V₆的弧值为50；

……

V₇就是有到V₈的弧值为20；

考点1：无向图的转换

对于连通无向图G，一下叙述中，错误的是（）。

A、G中任意两个顶点之间存在路径

B、G中任意两个顶点之间都有边

C、从G中任意顶点出发可遍历图中所有顶点

D、G的邻接矩阵是对称的

题解：选项B。完全图才是任意两个顶点之间都有边。

考点2：有向图转邻接矩阵

某图G的邻接矩阵如下图所示。

以下关于该图的叙述中，错误的是（）。

A、该图存在回路（环）

B、该图为完全有向图 √

C、图中所有顶点的入度都大于0

D、图中所有顶点的出度都大于0

解：

判断选项D：逐行统计顶点的出度分别为：2、1、2、2、1、2，所以D对

判断选项C：逐列统计顶点的入度分别为：2、1、2、2、1、2，所以C对

判断选项B：完全有向图的定义是每对顶点（每两个顶点）之间都有两条有向边相连接，很明显B是错的。

判断选项A：需要画图

明显顶点1、2、3之间构成了回路

考点3：有向图转邻接链表

已知某带权图G的邻接表如下所示，

其中表结点的结构为：以下关于该图的叙述中，正确的是（）。

A、图G是强连通图

B、图G具有14条弧

C、顶点B的出度为3

D、顶点B的入度为3 √

解：

A：“强连通图”要求任意两个顶点之间都有一条路径相连，顶点1A到2B有、到4D有，顶点3C到1A有，但1A和4D之间互相就没有，和5E之间互相也没有，所以A是错的

B：计数：1A到2B、1A到4D、2B到5E、3C到1A、3C到2B、4D到2B、5E到4D，一共7条弧，所以B是错的；

C：B的出度只有2B到5E一条，C错

D：统计B的入度有：1A到2B、3C到2B、4D到2B共计3条，D对