龙空技术网

JAVA-树|图-深度优先搜索

Bit旅人 43

前言:

而今看官们对“无向图建立”大约比较关注,兄弟们都需要了解一些“无向图建立”的相关知识。那么小编在网络上汇集了一些有关“无向图建立””的相关资讯,希望同学们能喜欢,你们一起来学习一下吧!

深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

深度优先搜索的特点是算法的递归性,因此其时间复杂度通常为O(V),其中V是图中顶点的数量。空间复杂度为O(H),其中H是栈的最大深度,也就是需要存储探索路径的节点数。

深度优先搜索在计算机科学中应用广泛,例如在解决图的连通性问题、寻找图的环、图的遍历、图的剖分、图的等价类、图的顶点可区分性等等问题上都有应用。

下面是一个简单的深度优先搜索的Java代码示例:

import java.util.LinkedList;public class DepthFirstSearch {    // 使用邻接列表表示图    private LinkedList<Integer> adj[];    boolean visited[]; // 标记数组,用于追踪节点是否被访问过    // 构造函数    DepthFirstSearch(int vertices) {        adj = (LinkedList<Integer>[]) new LinkedList[vertices];        visited = new boolean[vertices]; // 初始化 visited 数组        for (int i = 0; i < vertices; i++) {            adj[i] = new LinkedList<>();        }    }    // 添加边    void addEdge(int v1, int v2) {        adj[v1].add(v2);        adj[v2].add(v1); // 如果是无向图,需要加上这行    }    // 深度优先搜索函数    void dfs(int v) {        // 标记当前节点已被访问        System.out.print(v + " ");        // 遍历邻接列表,访问未被访问的节点        for (int i = 0; i < adj[v].size(); i++) {            int n = adj[v].get(i);            if (!visited[n]) {                visited[n] = true; // 标记为已访问                dfs(n); // 递归调用            }        }    }    public static void main(String args[]) {        DepthFirstSearch g = new DepthFirstSearch(4);        g.addEdge(0, 1);        g.addEdge(0, 2);        g.addEdge(1, 3);        g.addEdge(2, 3);        System.out.println("Depth First Search:");        g.dfs(0); // 从节点0开始搜索                // 输出结果        // Depth First Search:        // 0 1 0 2 3    }}

以上代码实现了一个简单的无向图,并从节点0开始进行深度优先搜索。当搜索到某个节点时,该节点会被标记为已访问,并且其未访问过的邻接节点会被递归地访问。在主函数main中,创建了一个有四个节点的图,并且连接了四个节点。然后从节点0开始执行深度优先搜索,输出遍历的结果。

标签: #无向图建立 #java搜索图片