深度优先遍历邻接矩阵邻接矩阵转化为邻接链表

深度优先遍历是一种图遍历算法，它从某个顶点开始，递归地访问该顶点的所有邻接顶点，直到所有顶点都被访问为止。具体实现可以使用栈来存储访问过的节点，每次取出栈顶元素并将其未访问的邻居节点入栈，直到栈为空。

邻接矩阵是一种表示图的数据结构，它是一个二维数组，数组元素表示两个节点之间是否有边相连。邻接链表是另一种表示图的数据结构，它由若干个链表组成，每个链表表示一个节点以及与它相连的所有边。将邻接矩阵转化为邻接链表可以通过遍历邻接矩阵，将每个节点以及与它相连的边添加到对应的链表中。

具体步骤如下：
1. 创建一个包含n个链表的数组，n为图的节点数。
2. 遍历邻接矩阵的每个元素，如果元素值为1，则将其对应的节点和与之相连的节点添加到对应的链表中。
3. 重复步骤2直到遍历完整个邻接矩阵。

相关问题

数据结构图系统定义一个图的数据类型，完成以下操作(1)用邻接矩阵的方式创建一个图 (2)用邻接表的方式创建一个图 (3)对采用邻接矩阵表示的图进行深度优先遍历: (4)对采用邻接矩阵表示的图进行广度优先遍历 (5)对采用邻接表表示的图进行深度优先遍历 (6)对采用邻接表表示的图进行广度优先遍历

好的，我来回答你的问题：

1. 用邻接矩阵的方式创建一个图

邻接矩阵是一个二维数组，其中数组中的每个元素表示两个节点之间是否有边。对于一个有 n 个节点的图，邻接矩阵的大小为 n x n。如果两个节点之间有边，则邻接矩阵中对应的元素为 1，否则为 0。

代码实现：

class GraphMatrix:
    def __init__(self, n):
        self.n = n
        self.matrix = [[0]*n for i in range(n)]
    
    def add_edge(self, u, v):
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1

2. 用邻接表的方式创建一个图

邻接表是一个由链表组成的数组，其中每个链表表示图中某个节点的邻居节点。对于一个有 n 个节点的图，邻接表的大小为 n。链表中的每个元素表示该节点的一个邻居节点。

代码实现：

class GraphList:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for i in range(n)]
    
    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

3. 对采用邻接矩阵表示的图进行深度优先遍历

深度优先遍历是一种遍历图的方式，它从某个起点开始，沿着一条路径尽可能远地访问图中的节点，直到到达一个死胡同，然后回溯到之前的节点，继续访问其他节点。深度优先遍历可以使用递归实现。

代码实现：

def dfs_matrix(graph, start, visited):
    visited[start] = True
    print(start, end=' ')
    for i in range(graph.n):
        if graph.matrix[start][i] == 1 and not visited[i]:
            dfs_matrix(graph, i, visited)

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

visited = [False]*g.n
dfs_matrix(g, 0, visited)

4. 对采用邻接矩阵表示的图进行广度优先遍历

广度优先遍历是一种遍历图的方式，它从某个起点开始，先访问所有与该节点相邻的节点，然后按照宽度优先的顺序访问它们的邻居节点。广度优先遍历可以使用队列实现。

代码实现：

from collections import deque

def bfs_matrix(graph, start, visited):
    queue = deque()
    queue.append(start)
    visited[start] = True
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for i in range(graph.n):
            if graph.matrix[node][i] == 1 and not visited[i]:
                visited[i] = True
                queue.append(i)

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

visited = [False]*g.n
bfs_matrix(g, 0, visited)

5. 对采用邻接表表示的图进行深度优先遍历

代码实现：

def dfs_list(graph, start, visited):
    visited[start] = True
    print(start, end=' ')
    for i in graph.adj[start]:
        if not visited[i]:
            dfs_list(graph, i, visited)

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

visited = [False]*g.n
dfs_list(g, 0, visited)

6. 对采用邻接表表示的图进行广度优先遍历

代码实现：

def bfs_list(graph, start, visited):
    queue = deque()
    queue.append(start)
    visited[start] = True
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for i in graph.adj[node]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

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

visited = [False]*g.n
bfs_list(g, 0, visited)

邻接矩阵非递归深度遍历和邻接链表非递归层次遍历

以下是邻接矩阵非递归深度遍历和邻接链表非递归层次遍历的Python实现：

邻接矩阵非递归深度遍历：

def DFS_iterative(graph, start):
    visited = set()  # 用集合存储已访问的节点
    stack = [start]  # 用栈存储待访问的节点
    while stack:
        vertex = stack.pop()  # 取出栈顶节点
        if vertex not in visited:
            visited.add(vertex)  # 将节点标记为已访问
            print(vertex, end=' ')
            # 将该节点的未访问过的邻居节点入栈
            stack.extend([v for v in range(len(graph[vertex])) if graph[vertex][v] and v not in visited])

# 示例
graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [1, 0, 0, 1],
         [0, 1, 1, 0]]
DFS_iterative(graph, 0)  # 从节点0开始深度遍历

输出结果为：0 2 3 1

邻接链表非递归层次遍历：

from collections import deque
def BFS_iterative(graph, start):
    visited = set()  # 用集合存储已访问的节点
    queue = deque([start])  # 用队列存储待访问的节点
    while queue:
        vertex = queue.popleft()  # 取出队首节点
        if vertex not in visited:
            visited.add(vertex)  # 将节点标记为已访问
            print(vertex, end=' ')
            # 将该节点的未访问过的邻居节点入队
            queue.extend([v for v in graph[vertex] if v not in visited])

# 示例
graph = {0: [1, 2],
         1: [0, 3],
         2: [0, 3],
         3: [1, 2]}
BFS_iterative(graph, 0)  # 从节点0开始层次遍历

输出结果为：0 1 2 3