数据结构与算法之深度优先遍历_图的深度优先遍历代码

深度优先遍历（Depth First Search，DFS）是一种常用的图遍历算法，主要应用在查找和遍历树或图的路径问题上。

深度优先遍历的原理是从一个节点开始，尽可能深地搜索这个节点的子节点，直到到达不能再深入的节点，然后回溯到上一个节点，继续搜索它的下一个子节点，直到所有节点都被访问为止。

具体实现时，可以使用递归或者栈来遍历节点。以递归实现为例，可以定义一个递归函数，输入参数为当前节点和访问状态的数组，函数的实现如下：

1. 先标记当前节点已经被访问过
2. 遍历当前节点的所有未被访问过的邻居节点，对每个未访问过的邻居节点，调用递归函数访问它
3. 返回到上一个节点，继续访问它的其他邻居节点

由于深度优先遍历是通过递归或者栈实现的，因此在访问图或树时，可能会遇到循环引用的情况，需要在实现时做好判重处理，防止出现死循环等问题。

深度优先遍历的时间复杂度为O(n+m)，其中n为节点数，m为边数，因为需要遍历所有节点和边。

一、C 实现 深度优先遍历 及代码详解

深度优先遍历（Depth First Search, DFS）是图论中的经典算法，用于遍历或搜索树或图的所有节点。

以下是 C 语言实现深度优先遍历算法的代码详解。

代码实现：

#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 20//定义最大顶点数

typedef struct ArcNode//定义弧度节点
{
    int adjvex;//邻接点下标
    struct ArcNode *nextarc;//指向下一个弧度节点的指针
}ArcNode;

typedef struct VNode//定义顶点节点
{
    int data;//顶点数据
    ArcNode *firstarc;//指向第一条弧度节点
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct Graph//定义图结构体
{
    AdjList vertices;//邻接表
    int vexnum,arcnum;//顶点数及弧度数
}Graph;

int visited[MAX_VERTEX_NUM];//标记各顶点是否被访问过

//创建一个图
void createGraph(Graph *G)
{
    int i,j,k;
    ArcNode *p;
    printf("输入顶点数和弧度数:\n");
    scanf("%d%d",&G->vexnum,&G->arcnum);
    printf("输入顶点信息:\n");
    for(i=0;i<G->vexnum;i++)
    {
        scanf("%d",&G->vertices[i].data);
        G->vertices[i].firstarc = NULL;//初始化每个顶点的指向第一条弧度节点的指针
    }
    printf("输入弧度信息:\n");
    for(k=0;k<G->arcnum;k++)
    {
        printf("输入弧度的起点和终点:\n");
        scanf("%d%d",&i,&j);
        //新建一个弧度节点，指向顶点j
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex=j;
        p->nextarc=G->vertices[i].firstarc;
        G->vertices[i].firstarc=p;
        //新建一个弧度节点，指向顶点i
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex=i;
        p->nextarc=G->vertices[j].firstarc;
        G->vertices[j].firstarc=p;
    }
}

//深度优先遍历
void DFS(Graph G,int v)
{
    ArcNode *p;
    visited[v]=1;//标记当前顶点为已访问状态
    printf("%d ",G.vertices[v].data);//输出当前访问的顶点
    p=G.vertices[v].firstarc;
    while(p!=NULL)//对当前节点的所有邻接点进行遍历
    {
        if(!visited[p->adjvex])//如果该邻接点未被访问，则对该节点进行深度优先遍历
        {
            DFS(G,p->adjvex);
        }
        p=p->nextarc;//指向下一个邻接点
    }
}

int main()
{
    Graph G;
    int i;
    createGraph(&G);
    printf("深度优先遍历的结果为:\n");
    for(i=0;i<G.vexnum;i++)
    {
        visited[i]=0;//初始化每个顶点的未访问状态
    }
    DFS(G,0);//从第0个节点开始深度优先遍历
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

代码详解：

在实现深度优先遍历的代码中，我们使用了一个邻接表来存储图。在邻接表中，每个顶点的指向第一条弧度节点的指针指向该顶点的第一条邻接边。另外，我们使用了一个visited数组来标记每个顶点是否被访问过，其中visited[i]为1表示第i个顶点已被访问过，为0则表示未被访问。

在createGraph函数中，我们输入了图的顶点数及弧度数，并且分别输入了每个顶点的信息。在输入每条弧度的起点和终点时，我们新建了两条弧度，一条从顶点i指向j，另一条从顶点j指向i，这两条弧度的存在是为了处理无向图。

在DFS函数中，我们先将当前节点标记为已访问状态，并输出当前访问的顶点。然后，我们遍历该节点的所有邻接点，并判断是否已经被访问过，如果没有，则以该节点为起点进行深度优先遍历。

在main函数中，我们调用了createGraph函数创建了一个图，并对visited数组进行了初始化。然后，我们从顶点0开始对整个图进行深度优先遍历。

二、C++ 实现 深度优先遍历 及代码详解

深度优先遍历（Depth First Search，DFS）是一种遍历图或树的算法。其核心思想是从某个结点开始，首先访问它本身，然后递归地访问其相邻结点中未曾访问过的结点，直到所有相邻结点都被访问过为止。具体实现过程可以使用递归或者栈来实现。

下面是C++实现深度优先遍历（DFS）的代码：

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 100;

// 存储图的邻接表
vector<int> adj[MAX];

// 标记图中是否已经被访问
bool visited[MAX];

// 深度优先遍历算法实现
void dfs(int u) {
    visited[u] = true;
    cout << u << " ";

    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    // 构建无向图
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(1);
    adj[2].push_back(4);
    adj[2].push_back(5);
    adj[3].push_back(1);
    adj[3].push_back(5);
    adj[4].push_back(2);
    adj[4].push_back(5);
    adj[5].push_back(2);
    adj[5].push_back(3);
    adj[5].push_back(4);

    // 从结点1开始进行深度优先遍历
    dfs(1);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

代码思路：首先定义了一个邻接表 adj 来存储图，每个元素是一个 vector<int> 类型的向量，用于存储和该结点相邻的结点。同时还定义了一个 bool 类型的数组 visited，用于标记该结点是否已经被访问过。

在 dfs 函数中，首先将当前结点 u 标记为已经被访问过，并输出该结点的值。然后遍历与该结点相邻的所有结点，如果其相邻结点 v 没有被访问过，则递归调用 dfs 函数继续访问。最后，当所有相邻结点都被访问完毕后，退出递归。最后，在 main 函数中，以结点1作为起始结点，调用 dfs 函数进行深度优先遍历。

这段代码可以输出以下结果：

1 2 4 5 3
1

表示从起始结点1开始，先访问结点1，再访问与结点1相邻的结点2和结点3，然后递归访问与结点2相邻的结点4和结点5，最后再访问与结点3相邻的结点5，遍历结束。

三、Java 实现 深度优先遍历 及代码详解

深度优先遍历（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，访问尽可能深的节点，直到找到目标或到达叶节点。然后，算法回溯到前一个节点，并继续遍历未访问的节点。

以下是 Java 代码实现深度优先遍历的基本框架：

// 定义节点类
class Node {
    int val;
    List<Node> neighbors;

    public Node(int val) {
        this.val = val;
        neighbors = new ArrayList<Node>();
    }
}

// 深度优先遍历
public void dfs(Node node, boolean[] visited) {
    visited[node.val] = true;
    System.out.print(node.val + " ");

    for (Node neighbor : node.neighbors) {
        if (!visited[neighbor.val]) {
            dfs(neighbor, visited);
        }
    }
}

// 调用深度优先遍历
public void callDFS(Node node) {
    boolean[] visited = new boolean[n]; // n 为节点总数
    dfs(node, visited);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

首先，定义一个节点类 Node，它包含节点的值 val 和链表形式的相邻节点列表 neighbors。然后，定义一个 dfs 函数来实现深度优先遍历。该函数需要两个参数：一个表示当前节点的 node 对象，另一个表示是否访问过当前节点的布尔值数组 visited。

在 dfs 函数中，首先将当前节点标记为已访问，并输出节点值。然后，遍历当前节点的相邻节点，如果相邻节点没有被访问，则递归调用 dfs 函数访问该相邻节点。

最后，定义一个 callDFS 函数来调用 dfs 函数并传入节点对象。在 callDFS 函数中，创建一个 visited 布尔数组来记录节点是否访问过，然后调用 dfs 函数并传入根节点对象和 visited 数组。

使用 callDFS 函数来遍历整个图或树结构。

这是一个示例代码，用来遍历一个有序图结构：

public class DFSGraphTraversal {
    int n; // 节点总数
    List<Node> graph; // 有序图结构

    public DFSGraphTraversal(int n) {
        this.n = n;
        graph = new ArrayList<Node>();
        for (int i = 0; i < n; i++) {
            graph.add(new Node(i));
        }
    }

    // 添加有向边
    public void addEdge(int from, int to) {
        Node fromNode = graph.get(from);
        Node toNode = graph.get(to);
        fromNode.neighbors.add(toNode);
    }

    // 深度优先遍历
    public void dfs(Node node, boolean[] visited) {
        visited[node.val] = true;
        System.out.print(node.val + " ");

        for (Node neighbor : node.neighbors) {
            if (!visited[neighbor.val]) {
                dfs(neighbor, visited);
            }
        }
    }

    // 调用深度优先遍历
    public void callDFS(Node node) {
        boolean[] visited = new boolean[n];
        dfs(node, visited);
    }

    // 测试
    public static void main(String[] args) {
        DFSGraphTraversal traversal = new DFSGraphTraversal(6);
        traversal.addEdge(0, 1);
        traversal.addEdge(0, 2);
        traversal.addEdge(1, 3);
        traversal.addEdge(2, 3);
        traversal.addEdge(2, 4);
        traversal.addEdge(3, 5);
        traversal.addEdge(4, 5);

        traversal.callDFS(traversal.graph.get(0)); // 从第 0 个节点开始遍历
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

在该示例代码中，首先创建一个 DFSGraphTraversal 对象，并在该对象中添加有向边。然后，调用 callDFS 函数来遍历整个图结构。

输出结果为：0 1 3 5 2 4，表示深度优先遍历的顺序。