图的创建、深度优先遍历、广度优先遍历

图的创建：

图由节点和边组成，可以使用邻接矩阵或邻接表来表示。

1.邻接矩阵：用一个二维数组来表示节点之间的关系，其中矩阵的行和列分别表示节点，矩阵中的元素表示节点之间是否有连边。

2.邻接表：用一个数组和若干个链表来表示，数组中的元素表示节点，每个节点对应一个链表，链表中存储与该节点相连的其他节点。

深度优先遍历：

深度优先遍历是一种遍历图的方式，从一个节点开始，尽可能深地访问该节点的所有子节点，直到所有的子节点都被访问完毕，然后回溯到上一个节点，继续访问其未被访问过的子节点，直到整个图被遍历完毕。

1.从起点开始遍历，将起点标记为已访问。

2.对于起点的每个未被访问过的邻居节点，递归地进行深度优先遍历。

3.回溯到上一个节点，继续访问其未被访问过的邻居节点，直到所有节点都被访问过。

广度优先遍历：

广度优先遍历是一种遍历图的方式，从一个节点开始，依次访问其所有邻居节点，然后再访问邻居节点的邻居节点，以此类推，直到整个图被遍历完毕。

1.从起点开始遍历，将起点标记为已访问，并将其加入队列。

2.从队列中取出一个节点，访问其所有未被访问过的邻居节点，并将这些邻居节点加入队列。

3.重复步骤2，直到队列为空，即所有节点都被访问过。

相关问题

深度优先遍历 广度优先遍历

深度优先遍历（Depth-First Search，DFS）和广度优先遍历（Breadth-First Search，BFS）是两种常用的图遍历算法。

深度优先遍历是一种通过递归或者栈的方式来遍历图的算法。它从图的某个顶点开始，沿着一条路径一直遍历到最后一个顶点，然后回溯到前一个顶点，再继续遍历其它未遍历的路径。重复这个过程，直到遍历完所有的顶点。

广度优先遍历是一种通过队列的方式来遍历图的算法。它从图的某个顶点开始，首先访问该顶点，然后将其所有未访问过的邻接顶点加入到队列中。之后从队列中取出一个顶点，并访问它的邻接顶点，再将这些邻接顶点加入队列。重复这个过程，直到队列为空。

总结起来，深度优先遍历是先纵向遍历到底再回溯，而广度优先遍历是先横向遍历一层再逐层向下。这两种遍历算法在不同的问题中有不同的应用场景和特点。

深度优先遍历 广度优先遍历的代码示例

下面是深度优先遍历和广度优先遍历的代码示例（以无向图为例）：

深度优先遍历的代码示例：

def dfs(graph, start, visited):
    visited.add(start)
    print(start, end=' ')

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 以邻接表表示图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = set()
dfs(graph, 'A', visited)

广度优先遍历的代码示例：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# 以邻接表表示图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

以上代码示例中，深度优先遍历和广度优先遍历都使用了图的邻接表表示。在深度优先遍历中，使用递归方式实现，通过记录已访问的节点来避免重复访问。在广度优先遍历中，使用队列来存储待访问的节点，并通过记录已访问的节点来避免重复访问。