创建图的邻接矩阵和邻接表

邻接矩阵和邻接表都是用于表示图的数据结构。

邻接矩阵是一个二维矩阵，其中每个元素表示两个顶点之间是否存在一条边。如果顶点i和顶点j之间存在一条边，则邻接矩阵中(i,j)和(j,i)的位置为1；否则为0。对于无向图来说，邻接矩阵是对称的。

邻接表则是通过链表的方式来表示每个顶点和与之相邻的顶点。对于每个顶点i，邻接表中存储了所有与之相邻的顶点的链表。如果顶点j与顶点i之间存在一条边，则在i的链表中存储j；如果存在多条边，则在链表中存储多个j。

下面是一个无向图的邻接矩阵和邻接表的示例：

邻接矩阵：
    0 1 1 0
    1 0 1 1
    1 1 0 1
    0 1 1 0

邻接表：
    0 -> 1 -> 2
    1 -> 0 -> 2 -> 3
    2 -> 0 -> 1 -> 3
    3 -> 1 -> 2

其中邻接矩阵中的(i,j)位置为1表示顶点i和顶点j之间有一条边；邻接表中的箭头表示从一个顶点出发可以到达的所有相邻顶点。

相关问题

创建图的邻接矩阵输出图的邻接矩阵3. 根据邻接矩阵创建邻接表输出邻接表销毁邻接表

邻接矩阵是一种用于表示图形的数据结构，其中每个节点都用一个行和一个列来表示。如果两个节点之间有一条边，则相应的矩阵元素为1，否则为0。邻接矩阵可以通过以下步骤创建：

1. 定义一个二维数组，数组的大小为节点数×节点数。
2. 根据节点之间的连接情况，在相应的数组元素中标记1或0。

例如，以下是一个包含4个节点和4条边的无向图的邻接矩阵：

    0 1 1 0
    1 0 1 0
    1 1 0 1
    0 0 1 0

根据邻接矩阵创建邻接表的过程如下：

1. 对于每个节点，创建一个链表。
2. 遍历邻接矩阵中的每个元素，如果该元素为1，则在相应的链表中添加一个节点，该节点表示与当前节点相连的另一个节点。

例如，以上邻接矩阵所对应的邻接表如下：

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

销毁邻接表的过程很简单，只需要依次遍历每个链表，并释放其节点即可。

自定义图的邻接矩阵和邻接表两种存储结构。以下两项任选其一： (1)创建图的邻接矩阵，设计算法自动生成邻接表，或： (2)创建图的邻接表，设计算法自动生成邻接矩阵。 要求能够打印图的邻接矩阵和邻接表，进行验证。

我可以为您提供创建图的邻接矩阵并自动生成邻接表的算法。

首先，我们需要定义一个Graph类来表示图，其中包含邻接矩阵和邻接表两种存储结构。以下是一个基本的Graph类实现：

class Graph:
    def __init__(self, num_vertices):
        # 邻接矩阵
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
        # 邻接表
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, src, dest):
        # 在邻接矩阵中添加边
        self.adj_matrix[src][dest] = 1
        self.adj_matrix[dest][src] = 1
        # 在邻接表中添加边
        self.adj_list[src].append(dest)
        self.adj_list[dest].append(src)

    def print_adj_matrix(self):
        # 打印邻接矩阵
        for row in self.adj_matrix:
            print(row)

    def print_adj_list(self):
        # 打印邻接表
        for i, adjacents in enumerate(self.adj_list):
            print(f"{i}: {adjacents}")

在上面的代码中，我们定义了一个Graph类，它有一个构造函数，用于初始化邻接矩阵和邻接表。我们还定义了一个add_edge()方法，用于向图中添加边。在这个方法中，我们首先在邻接矩阵中添加边，然后在邻接表中添加边。最后，我们还定义了两个方法print_adj_matrix()和print_adj_list()，用于打印邻接矩阵和邻接表。

现在，我们可以在Graph类中添加一个新的方法，用于从邻接矩阵生成邻接表。以下是这个方法的实现：

def generate_adj_list(self):
        self.adj_list = [[] for _ in range(len(self.adj_matrix))]
        for i in range(len(self.adj_matrix)):
            for j in range(len(self.adj_matrix[i])):
                if self.adj_matrix[i][j] == 1:
                    self.adj_list[i].append(j)

在上面的代码中，我们遍历邻接矩阵中的每一个元素。如果邻接矩阵中的值是1，说明有一条边，我们就在邻接表中添加这条边。最后，我们将生成的邻接表覆盖Graph类中原有的邻接表。

现在，我们可以创建一个Graph对象，向其中添加一些边，然后打印邻接矩阵和邻接表，最后生成邻接表并再次打印邻接表来验证我们的算法。

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

print("Adjacency Matrix:")
g.print_adj_matrix()

print("Adjacency List:")
g.print_adj_list()

g.generate_adj_list()
print("Generated Adjacency List:")
g.print_adj_list()

运行上面的代码，我们可以看到以下输出：

Adjacency Matrix:
[0, 1, 0, 0, 1]
[1, 0, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 1, 0, 1, 0]
Adjacency List:
0: [1, 4]
1: [0, 2, 3, 4]
2: [1, 3]
3: [1, 2, 4]
4: [0, 1, 3]
Generated Adjacency List:
0: [1, 4]
1: [0, 2, 3, 4]
2: [1, 3]
3: [1, 2, 4]
4: [0, 1, 3]

我们可以看到邻接矩阵和邻接表都被正确地打印出来了，并且生成的邻接表也与原始的邻接表相同，因此我们的算法是正确的。