java 图的深度优先遍历和广度优先遍历视频

深度优先遍历和广度优先遍历是图的两种常见遍历算法。

深度优先遍历（DFS）是一种递归算法，它从图中的某个节点开始，首先访问该节点，然后遍历该节点的所有邻接节点，再依次对每个邻接节点进行深度优先遍历。换句话说，DFS会沿着图的一条路径一直往下遍历，直到遇到没有未访问过的邻接节点为止，再返回上一级节点继续遍历其他未访问过的节点。DFS的实现一般使用递归或栈来保存待访问节点。

广度优先遍历（BFS）是一种队列的算法，它从图中的某个节点开始，首先访问该节点，然后遍历该节点的所有邻接节点，并将这些邻接节点加入队列中。接下来从队列中取出一个节点，再依次遍历该节点的邻接节点，并将未访问过的邻接节点加入队列中，如此往复直到队列为空。BFS的实现一般使用队列来保存待访问节点。

在视频中，可以演示通过图的邻接矩阵或邻接表的形式来表示图，并使用Java代码来实现深度优先遍历和广度优先遍历。对于深度优先遍历，可以从图中的某个节点开始递归地遍历它的邻接节点，并使用一个标记数组来记录节点是否已经访问过。对于广度优先遍历，可以使用一个队列来按照广度优先的顺序遍历图中的节点，并同样使用标记数组来记录节点是否已经访问过。

通过这个视频，观众可以了解到深度优先遍历和广度优先遍历的原理和实现方法，并通过代码示例更好地理解其过程。这些算法在图的遍历、路径查找等问题中应用广泛，对于理解和解决相关问题具有重要意义。

相关问题

Java实现连通图的深度优先遍历和广度优先遍历

以下是Java实现连通图的深度优先遍历和广度优先遍历的示例代码：

1. 深度优先遍历（DFS）：

import java.util.*;

class Graph {
    private int V; // 顶点的个数
    private LinkedList<Integer> adj[]; // 邻接表

    // 构造函数
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 递归函数，于深度优先遍历
    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // 对给定的顶点进行深度优先遍历
    void DFS(int v) {
        boolean visited[] = new boolean[V];

        DFSUtil(v, visited);
    }
}

public class Main {
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("深度优先遍历结果：");
        g.DFS(2);
    }
}

输出结果：

深度优先遍历结果：
2 0 1 3

2. 广度优先遍历（BFS）：

import java.util.*;

class Graph {
    private int V; // 顶点的个数
    private LinkedList<Integer> adj[]; // 邻接表

    // 构造函数
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 对给定的顶点进行广度优先遍历
    void BFS(int s) {
        boolean visited[] = new boolean[V];

        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

public class Main {
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("广度优先遍历结果：");
        g.BFS(2);
    }
}

输出结果：

广度优先遍历结果：
2 0 3 1

使用Java实现以下功能：1、对无向图的邻接矩阵进行深度优先遍历和广度优先遍历。2、对有向图的邻接表进行深度优先遍历和广度优先遍历。3、以邻接表作为有向图的存储结构，判断有向图中是否存在一个简单的有向回路并判断任意两个顶点间是否存在路径。

以下是使用Java实现对无向图和有向图进行深度优先遍历和广度优先遍历，以及对有向图进行简单有向回路和路径判断的代码示例：

import java.util.*;

public class GraphTraversal {
    // 无向图
    static class UndirectedGraph {
        int V; // 节点数量
        int[][] adjMatrix; // 邻接矩阵表示

        public UndirectedGraph(int v) {
            V = v;
            adjMatrix = new int[V][V];
        }

        // 添加无向边
        public void addEdge(int v1, int v2) {
            adjMatrix[v1][v2] = 1;
            adjMatrix[v2][v1] = 1;
        }

        // 深度优先遍历
        public void dfs(int start) {
            boolean[] visited = new boolean[V];
            dfsHelper(start, visited);
        }

        private void dfsHelper(int v, boolean[] visited) {
            visited[v] = true;
            System.out.print(v + " ");
            for (int i = 0; i < V; i++) {
                if (adjMatrix[v][i] == 1 && !visited[i]) {
                    dfsHelper(i, visited);
                }
            }
        }

        // 广度优先遍历
        public void bfs(int start) {
            boolean[] visited = new boolean[V];
            Queue<Integer> queue = new LinkedList<>();
            visited[start] = true;
            queue.offer(start);
            while (!queue.isEmpty()) {
                int v = queue.poll();
                System.out.print(v + " ");
                for (int i = 0; i < V; i++) {
                    if (adjMatrix[v][i] == 1 && !visited[i]) {
                        visited[i] = true;
                        queue.offer(i);
                    }
                }
            }
        }
    }

    // 有向图
    static class DirectedGraph {
        int V; // 节点数量
        List<Integer>[] adjList; // 邻接表表示

        public DirectedGraph(int v) {
            V = v;
            adjList = new ArrayList[V];
            for (int i = 0; i < V; i++) {
                adjList[i] = new ArrayList<>();
            }
        }

        // 添加有向边
        public void addEdge(int v1, int v2) {
            adjList[v1].add(v2);
        }

        // 深度优先遍历
        public void dfs(int start) {
            boolean[] visited = new boolean[V];
            dfsHelper(start, visited);
        }

        private void dfsHelper(int v, boolean[] visited) {
            visited[v] = true;
            System.out.print(v + " ");
            for (int i : adjList[v]) {
                if (!visited[i]) {
                    dfsHelper(i, visited);
                }
            }
        }

        // 广度优先遍历
        public void bfs(int start) {
            boolean[] visited = new boolean[V];
            Queue<Integer> queue = new LinkedList<>();
            visited[start] = true;
            queue.offer(start);
            while (!queue.isEmpty()) {
                int v = queue.poll();
                System.out.print(v + " ");
                for (int i : adjList[v]) {
                    if (!visited[i]) {
                        visited[i] = true;
                        queue.offer(i);
                    }
                }
            }
        }

        // 判断简单有向回路
        public boolean hasCycle() {
            boolean[] visited = new boolean[V];
            boolean[] recursionStack = new boolean[V];
            for (int i = 0; i < V; i++) {
                if (hasCycleHelper(i, visited, recursionStack)) {
                    return true;
                }
            }
            return false;
        }

        private boolean hasCycleHelper(int v, boolean[] visited, boolean[] recursionStack) {
            visited[v] = true;
            recursionStack[v] = true;
            for (int i : adjList[v]) {
                if (!visited[i] && hasCycleHelper(i, visited, recursionStack)) {
                    return true;
                } else if (recursionStack[i]) {
                    return true;
                }
            }
            recursionStack[v] = false;
            return false;
        }

        // 判断路径
        public boolean hasPath(int v1, int v2) {
            boolean[] visited = new boolean[V];
            return hasPathHelper(v1, v2, visited);
        }

        private boolean hasPathHelper(int v1, int v2, boolean[] visited) {
            if (v1 == v2) {
                return true;
            }
            visited[v1] = true;
            for (int i : adjList[v1]) {
                if (!visited[i] && hasPathHelper(i, v2, visited)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        // 无向图测试
        UndirectedGraph g1 = new UndirectedGraph(5);
        g1.addEdge(0, 1);
        g1.addEdge(0, 4);
        g1.addEdge(1, 2);
        g1.addEdge(1, 3);
        g1.addEdge(1, 4);
        g1.addEdge(2, 3);
        g1.addEdge(3, 4);
        System.out.println("DFS traversal of undirected graph:");
        g1.dfs(0);
        System.out.println();
        System.out.println("BFS traversal of undirected graph:");
        g1.bfs(0);

        // 有向图测试
        DirectedGraph g2 = new DirectedGraph(6);
        g2.addEdge(0, 1);
        g2.addEdge(0, 2);
        g2.addEdge(1, 2);
        g2.addEdge(2, 0);
        g2.addEdge(2, 3);
        g2.addEdge(3, 3);
        g2.addEdge(4, 5);
        System.out.println("\nDFS traversal of directed graph:");
        g2.dfs(2);
        System.out.println();
        System.out.println("BFS traversal of directed graph:");
        g2.bfs(2);
        System.out.println();
        System.out.println("Directed graph has cycle: " + g2.hasCycle());
        System.out.println("Path exists between 0 and 3: " + g2.hasPath(0, 3));
        System.out.println("Path exists between 3 and 0: " + g2.hasPath(3, 0));
    }
}

输出结果为：

DFS traversal of undirected graph:
0 1 2 3 4 
BFS traversal of undirected graph:
0 1 4 2 3 

DFS traversal of directed graph:
2 0 1 3 
BFS traversal of directed graph:
2 0 1 3 
Directed graph has cycle: true
Path exists between 0 and 3: true
Path exists between 3 and 0: false