龙空技术网

深度优先搜索/广度优先搜索与java的实现

Admin123 117

前言:

现时大家对“深度优先算法广度优先算法”都比较讲究,小伙伴们都想要学习一些“深度优先算法广度优先算法”的相关资讯。那么小编同时在网上收集了一些有关“深度优先算法广度优先算法””的相关文章,希望小伙伴们能喜欢,我们快快来学习一下吧!

度:某个顶点的度就是依附于该顶点的边的个数

子图:一幅图中所有边(包含依附边的顶点)的子集

路径:是由边顺序连接的一系列定点组成

环:至少含有一条边且终点和起点相同的路径

连通图:如果图中任一个到另一个节点都存在一条路径,该图就叫连通图。

图的存储方式

1.邻接矩阵:

空间复杂度较高。

2.邻接表

图结构的java实现代码

import java.util.LinkedList;import java.util.Queue;/** * 无向图 * 数组索引代表顶点的值 */public class Graph {    private int V; //顶点数量    private int E; //边数量    private Queue<Integer>[] adj; //邻接表    public Graph(int vertical) {        this.V = vertical;        this.adj = new Queue[vertical];        for (int i = 0; i < vertical; i++) {            adj[i] = new LinkedList<>();        }    }    public int getV() {        return V;    }    public int getE() {        return E;    }    /**     * 向图中某一顶点加一条边     * 无向图是没有方向的,需要让w出现在v的邻接表中,还需要让v出现在w的邻接表中     *     * @param w     * @param v     */    public void addEdge(int v, int w) {        adj[v].add(w);        adj[w].add(v);        this.E++;    }    /**     * 获取和某一顶点关联的所有顶点     *     * @param v     * @return Queue     */    public Queue<Integer> adj(int v) {        return adj[v];    }}

深度优先搜索:指的是如果遇到一个子节点既有兄弟节点又有子节点,那么先找子节点,再找兄弟节点

实现代码如下:

/** * 深度优先搜索 */public class DepthFirstSearch {    private int sCount; //记录多少个节点与s节点相通    private boolean[] marked; //代表顶点是否被搜索过    //找出g中与顶点s所有相邻的节点    public DepthFirstSearch(Graph g, int s) {        marked = new boolean[g.getV()];        //初始化跟顶点s相通的数量        this.sCount = 0;        dfs(g, s);    }    //找出g中与顶点v所有相通的节点    private void dfs(Graph graph, int v) {        //将v节点标识为已搜索        marked[v] = true;        for (Integer w : graph.adj(v)) {            if (!marked[w]) {                dfs(graph, w);            }        }        sCount++;    }    private boolean marked(int w) { //判断w顶点与s顶点是否相通        return marked[w];    }    private int count() {//获取所有与s顶点相通的总数        return sCount;    }}

广度优先搜索:指的是如果遇到一个子节点既有兄弟节点又有子节点,那么先找兄弟节点,再找子节点,类似于层次遍历

代码如下:

import java.util.LinkedList;import java.util.Queue;/** * 广度优先搜索 */public class BreadthFirstSearch {    private int sCount; //记录多少个节点与s节点相通    private final boolean[] marked; //代表顶点是否被搜索过    private final Queue<Integer> waitSearch; //存储带搜索顶点    //找出g中与顶点s所有相邻的节点    public BreadthFirstSearch(Graph g, int s) {        marked = new boolean[g.getV()];        //初始化跟顶点s相通的数量        this.sCount = 0;        waitSearch = new LinkedList<>();        bfs(g, s);    }    //找出g中与顶点v所有相通的节点    private void bfs(Graph graph, int v) {        waitSearch.add(v);        while (!waitSearch.isEmpty()) {            Integer wait = waitSearch.poll();            for (Integer w : graph.adj(wait)) {                if (!marked(w)) {                    marked[w] = true;                    sCount++;                    waitSearch.add(w);                }            }        }    }    public boolean marked(int w) { //判断w顶点与s顶点是否相通        return marked[w];    }    public int count() {//获取所有与s顶点相通的总数        return sCount;    }}

标签: #深度优先算法广度优先算法