怎么求图的邻接矩阵和邻接表
邻接矩阵和邻接表是表示图的两种常用方式。邻接矩阵是一个二维数组，用于表示各个节点之间的连通性，而邻接表则是通过链表来表示节点之间的关系。
求图的邻接矩阵和邻接表，需要通过遍历图来获取节点之间的关系。以下是具体的步骤和实现方法：
一、求无向图的邻接矩阵和邻接表
1.邻接矩阵
对于无向图，邻接矩阵是一个对称矩阵。假设该无向图共有n个节点，那么邻接矩阵的大小为n x n。
邻接矩阵中第i行第j列的值表示节点i和节点j之间是否有边相连。如果有，则该位置的值为1；否则为0。
下面是求无向图邻接矩阵的示例代码：
```python
n = 6
graph = [[0, 1, 0, 1, 0, 0],
[1, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 1],
[1, 1, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0]]
print(graph)
```
运行结果：
```
[[0, 1, 0, 1, 0, 0],
[1, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 1],
[1, 1, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0]]
```
其中，第i行和第i列都是表示第i个节点，如果graph[i][j]为1表示节点i和节点j之间有边相连。这个邻接矩阵的Numpy表示形式可以方便地进行矩阵运算
2.邻接表
邻接表是一种用链表表示节点之间关系的数据结构。每个节点相邻的节点个数可能不同，因此每个节点可以用链表来存储其邻居节点。
下面是求无向图邻接表的示例代码：
```python
from collections import defaultdict
# 无向图的例子
graph = defaultdict(list)
graph[0].append(1)
graph[0].append(3)
graph[1].append(0)
graph[1].append(2)
graph[1].append(3)
graph[1].append(4)
graph[2].append(1)
graph[2].append(4)
graph[2].append(5)
graph[3].append(0)
graph[3].append(1)
graph[3].append(4)
graph[4].append(1)
graph[4].append(2)
graph[4].append(3)
graph[4].append(5)
graph[5].append(2)
graph[5].append(4)
print(graph)
```
运行结果：
```
defaultdict(
{0: [1, 3],
1: [0, 2, 3, 4],
2: [1, 4, 5],
3: [0, 1, 4],
4: [1, 2, 3, 5],
5: [2, 4]})
```
代码中使用了Python内置的defaultdict类，这个类的作用相当于是一个字典的工厂函数，我们可以给它一个list作为默认值。当我们调用该类的时候，如果字典中不存在该key，则使用list作为该key的默认值。
二、求有向图的邻接矩阵和邻接表
有向图是指图中的边只是单向的。求有向图的邻接矩阵和邻接表可以通过类似的方式实现。
1.邻接矩阵
有向图的邻接矩阵与无向图的不同点在于，有向图的邻接矩阵不再是对称矩阵，第i行第j列的值表示的是节点i到节点j是否有一条从i到j的有向边。
下面是求有向图邻接矩阵的示例代码：
```python
n = 4
graph = [[0, 1, 0, 0],
[0, 0, 1, 1],
[0, 1, 0, 0],
[1, 0, 1, 0]]
print(graph)
```
运行结果：
```
[[0, 1, 0, 0],
[0, 0, 1, 1],
[0, 1, 0, 0],
[1, 0, 1, 0]]
```
其中，graph[i][j]为1表示节点i到节点j有一条有向边。
2.邻接表
求有向图的邻接表同样需要保存节点之间的方向信息。下面是求有向图邻接表的示例代码：
```python
from collections import defaultdict
# 有向图的例子
graph = defaultdict(list)
graph[0].append(1)
graph[1].append(2)
graph[1].append(3)
graph[2].append(1)
graph[3].append(0)
graph[3].append(2)
print(graph)
```
运行结果：
```
defaultdict(
{0: [1],
1: [2, 3],
2: [1],
3: [0, 2]})
```
三、算法复杂度分析
邻接矩阵和邻接表各有优缺点。邻接矩阵比邻接表更节省存储空间，而邻接表更适合存储稀疏图。但在求解图中节点之间的连通关系时，邻接矩阵的时间复杂度为O(n^2)，而邻接表的时间复杂度为O(n+m)，其中n是节点数，m是边数。
对于求邻接矩阵和邻接表的问题，时间复杂度也与算法的实现方式有关。因此，我们需要在实际应用中根据图的规模和密度来选择更加适合的求解方法。
综上所述，求图的邻接矩阵和邻接表可以通过遍历图的方式实现。对于无向图和有向图，我们需要分别计算邻接矩阵和邻接表。在实际应用中，我们需要根据问题的具体情况来选择更加适合的求解方法。
