以邻接矩阵形式存储的图的深度优先

遍历可以使用递归实现。具体步骤如下：

1. 从起点开始，将其标记为已访问，然后输出该节点；

2. 对于起点的每一个未访问的邻居节点，递归调用深度优先遍历函数，对该节点进行访问；

3. 递归结束后回溯到上一级节点，继续遍历该节点的其他未访问邻居节点。

代码实现如下：

def DFS(graph, start, visited):
    visited[start] = True
    print(start, end=' ')
    for neighbor in graph[start]:
        if not visited[neighbor]:
            DFS(graph, neighbor, visited)

# 测试
graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
visited = [False] * len(graph)
DFS(graph, 2, visited)

输出结果为：2 0 1 3。

其中，graph 表示邻接矩阵形式的图，start 表示起点，visited 为布尔型数组，表示每个节点是否已经访问过。

相关问题

邻接矩阵存储图的深度优先遍历 代码

以下是邻接矩阵存储图的深度优先遍历的代码实现：

#define MaxVertexNum 100    // 最大顶点数设为100
typedef char VertexType;    // 顶点类型设为字符型
typedef int EdgeType;       // 边权值设为整型
typedef struct{
    VertexType Vex[MaxVertexNum];            // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];// 邻接矩阵，可看作边表
    int vexnum, arcnum;                     // 图的当前点数和边数/弧数
}MGraph;

bool visited[MaxVertexNum];  // 访问标记数组，初始化为false

// 邻接矩阵的深度优先递归算法
void DFS(MGraph G, int v){
    visited[v] = true;      // 标记v已访问
    printf("%c ", G.Vex[v]); // 输出顶点的数据
    for(int i = 0; i < G.vexnum; i++){
        if(G.Edge[v][i] != 0 && !visited[i]){
            DFS(G, i);       // 对访问的邻接顶点递归调用
        }
    }
}

// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
    for(int i = 0; i < G.vexnum; i++){
        visited[i] = false; // 初始化所有顶点状态都是未访问过状态
    }
    for(int i = 0; i < G.vexnum; i++){
        if(!visited[i]){   // 对未访问过的顶点调用DFS，若是连通图，只会执行一次
            DFS(G, i);
        }
    }
}

R6-1 邻接矩阵存储图的深度优先遍历

以下是邻接矩阵存储图的深度优先遍历的Python实现：

def DFS(MGraph, visited, v):
    visited[v] = True
    print(v, end=' ')
    for w in range(MGraph.Nv):
        if not visited[w] and MGraph.G[v][w] != 0:
            DFS(MGraph, visited, w)

def DFSTraverse(MGraph):
    visited = [False] * MGraph.Nv
    for v in range(MGraph.Nv):
        if not visited[v]:
            DFS(MGraph, visited, v)

其中，`MGraph`是邻接矩阵存储的图，`visited`是记录每个顶点是否被访问过的数组，`v`是当前访问的顶点。`DFS`函数是深度优先遍历的核心代码，它首先将当前顶点标记为已访问，并输出该顶点的编号。然后遍历该顶点的所有邻接点，如果邻接点未被访问过且与当前顶点有边相连，则递归访问该邻接点。`DFSTraverse`函数是深度优先遍历的入口，它遍历图中的所有连通块，对于每个连通块，从一个未被访问的顶点开始进行深度优先遍历。