图邻接矩阵和邻接表算法有哪些

图的邻接矩阵和邻接表是两种不同的表示图的方法。

邻接矩阵是用一个二维矩阵来表示图，矩阵中的每个元素是一个布尔值，表示两个顶点之间是否有边相连。这种表示方法适用于稠密图，即图中边的数量接近于最大值的图。邻接矩阵的优点是可以快速检查两个顶点之间是否有边相连，但是如果图中点的数量很多，邻接矩阵就会浪费很多空间。

邻接表是用链表来表示图，每个顶点对应一个链表，链表中的每个元素表示该顶点和其他顶点之间有边相连。这种表示方法适用于稀疏图，即图中边的数量比较少的图。邻接表的优点是空间效率高，但是如果要检查两个顶点之间是否有边相连，就需要遍历链表，所以访问速度会比邻接矩阵慢。

相关问题

设计将无向图的邻接矩阵转为对应邻接表的算法

1. 首先创建一个大小为n的空链表数组，n为无向图的顶点数。
2. 遍历邻接矩阵，对于每个顶点i，遍历其相邻的顶点j。
3. 如果邻接矩阵中i和j的值为1，则将j加入i的链表中，同时将i加入j的链表中。
4. 遍历完邻接矩阵后，得到的链表数组即为对应的邻接表。

设计一个算法将无向图的邻接矩阵转为对应邻接表的算法

算法步骤如下：

1. 创建一个空的邻接表，其中包含与无向图中顶点数相同的链表。

2. 遍历无向图的邻接矩阵，对于每个非零元素，将其对应的行和列所代表的顶点加入到邻接表中。

3. 对于每个顶点，将其邻接矩阵中对应的行或列中非零元素所代表的顶点加入到该顶点对应的链表中。

4. 返回生成的邻接表。

例如，对于以下无向图的邻接矩阵：

 1 1 
1  1 1
1 1  1
 1 1 

生成的邻接表如下：

 -> 1 -> 2
1 ->  -> 2 -> 3
2 ->  -> 1 -> 3
3 -> 1 -> 2

其中，每个数字代表一个顶点，箭头表示该顶点所连接的其他顶点。