精华内容
下载资源
问答
  • 图的深度优先搜索
    千次阅读 多人点赞
    2022-03-11 11:53:46

    图的遍历,

    即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略: (1)深度优先遍历

    (2)广度优先遍历

    图的深度优先搜索(Depth First Search)

    指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,然后找兄弟结点。

    1. 深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
    2. 我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。
    3. 显然,深度优先搜索是一个递归的过程

    深度优先遍历算法步骤

    1. 访问初始结点v,并标记结点v为已访问。
    2. 查找结点v的第一个邻接结点w。
    3. 若w存在,则继续执行4,
    4. 如果w不存在,则回到第1步,将从v的下一个结点继续。
    5. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
    6. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

     很明显,在由于边是没有方向的,所以,如果4和5顶点相连,那么4会出现在5的相邻链表中,5也会出现在4的相邻链表中,那么为了不对顶点进行重复搜索,应该要有相应的标记来表示当前顶点有没有搜索过,可以使用一个布尔类型的数组 boolean[V] marked,索引代表顶点,值代表当前顶点是否已经搜索,如果已经搜索,标记为true,如果没有搜索,标记为false;

    API设计

    API设计
    类名DepthFirstSearch
    构造方法DepthFirstSearch(Graph G,int s):构造深度优先搜索对象,使用深度优先搜索找出G图中s顶点的所有相通顶点
    成员方法1.private void dfs(Graph G, int v):使用深度优先搜索找出G图中v顶点的所有相通顶点 2.public boolean marked(int w):判断w顶点与s顶点是否相通 3.public int count():获取与顶点s相通的所有顶点的总数
    成员变量1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索 2.private int count:记录有多少个顶点与s顶点相通

    代码实现

    1、实现图:

    package 基本图;
    
    import 队列.Queue;
    
    public class Graph {
        //顶点数目
        private final int v;
        //遍的数目
        private int E;
        //邻接表
        private Queue<Integer>[] adj;
    
        public Graph(int v) {
            //初始化顶点数量
            this.v = v;
            //初始化边的数量
            this.E = 0;
            //初始化邻接表
            this.adj = new Queue[v];
    
            for (int i = 0; i < adj.length; i++) {
                adj[i] = new Queue<>();
            }//为邻接表赋值
        }
    
        //获取顶点的数目
        public int v(){
            return v;
        }
    
        //获取边的数目
        public int E(){
            return E;
        }
    
        //向图中添加一条边
        public void addEdge(int v,int w){
            //在无向图中,边是没有方向的,所以该边既可以说是从v到w,也可以是w到v
            adj[v].enqueue(w) ;
            adj[w].enqueue(v) ;
            //边的数量+1
            E++;
        }
    
        //获取和顶点v相邻的所有顶点
        public Queue<Integer> adj(int v){
            return adj[v];
        }//返回邻接表里的值
    }
    

    2、深度优先搜索处理办法

    package 深度优先搜索;
    
    import 基本图.Graph;
    
    public class DepthFirstSearch {
        //索引代表顶点,值表示当前顶底是否已经被搜索过
        private boolean[] marked;
        //记录有多少个顶点与s顶点相通
        private int count;
    
        //构造深度优先搜索对象,使用深度优先搜索找出G图中顶点的所有相邻顶点(找兄弟节点)
        //s为起点5
        public DepthFirstSearch(Graph G, int s){
            //初始化marked数组
            this.marked = new boolean[G.v()];
            //初始化跟顶点s相通的顶点的数量
            this.count = 0;
            dfs(G,s);
        }
    
        //使用深度优先搜索找出G图中v顶点的所有相通的顶点(找子节点)
        private void dfs(Graph G,int v){
            //把v标识为已搜索
            marked[v] = true;
    
            for (Integer w : G.adj(v)) {
                //判断当前w顶点有没有被搜索过,如果没有被搜索过 ,则递归调用dfs方法进行深度搜索
                if(!marked[w]){
                    dfs(G,w);
                }
            }
            //相通顶点的数量+1,找到兄弟节点
            count++;
        }
    
        //判断w顶点与s顶点是否相通
        public boolean marked(int w){
            return marked[w];
        }
    
        //获取与顶点s相通的所有顶点的总数
        public int count(){
            return count;
        }
    }
    

    核心代码

      //使用深度优先搜索找出G图中v顶点的所有相通的顶点(找子节点)
        private void dfs(Graph G,int v){
            //把v标识为已搜索
            marked[v] = true;
    
            for (Integer w : G.adj(v)) {
                //判断当前w顶点有没有被搜索过,如果没有被搜索过 ,则递归调用dfs方法进行深度搜索
                if(!marked[w]){
                    dfs(G,w);
                }
            }
            //相通顶点的数量+1,找到兄弟节点
            count++;
        }

    测试代码(Demo)

    package 深度优先搜索;
    
    import 基本图.Graph;
    
    public class DepthFirstSearchTest {
        public static void main(String[] args) {
            //准备Graph对象
            Graph G = new Graph(13);
            G.addEdge(0,5);
            G.addEdge(0,1);
            G.addEdge(0,2);
            G.addEdge(0,6);
            G.addEdge(5,3);
            G.addEdge(5,4);
            G.addEdge(3,4);
            G.addEdge(4,6);
    
            G.addEdge(7,8);
    
            G.addEdge(9,11);
            G.addEdge(9,10);
            G.addEdge(9,12);
            G.addEdge(11,12);
    
            //准备深度优先搜索对象
            DepthFirstSearch search = new DepthFirstSearch(G,0);
    
            //准备深度优先搜索对象
            int count = search.count();
            System.out.println("与起点0相通的顶点的数量为:" + count);
    
            //测试与某个顶点相通的顶点数量
            boolean marked1 = search.marked(5);
            System.out.println("顶点5和0是否相通:" + marked1);
    
            //测试某个顶点与起点是否相通
            boolean marked2 = search.marked(7);
            System.out.println("顶点7和0是否相通:" + marked2);
        }
    }
    

    导入的包

    package 队列;
    
    import java.util.Iterator;
    
    public class Queue<T> implements Iterable<T>{
        //记录首结点
        private Node head;
        //记录最后一个结点
        private Node last;
        //记录队列中元素的个数
        private int N;
    
    
        private class Node{
            public T item;
            public Node next;
    
            public Node(T item, Node next) {
                this.item = item;
                this.next = next;
            }
        }
        public Queue() {
            this.head = new Node(null,null);
            this.last=null;
            this.N=0;
        }
    
        //判断队列是否为空
        public boolean isEmpty(){
            return N==0;
        }
    
        //返回队列中元素的个数
        public int size(){
            return N;
        }
    
        //向队列中插入元素t
        public void enqueue(T t){
    
            if (last==null){
                //当前尾结点last为null
                last= new Node(t,null);
                head.next=last;
            }else {
                //当前尾结点last不为null
                Node oldLast = last;
                last = new Node(t, null);
                oldLast.next=last;
            }
    
            //元素个数+1
            N++;
        }
    
        //从队列中拿出一个元素
        public T dequeue(){
            if (isEmpty()){
                return null;
            }
    
            Node oldFirst= head.next;
            head.next=oldFirst.next;
            N--;
    
            //因为出队列其实是在删除元素,因此如果队列中的元素被删除完了,需要重置last=null;
    
            if (isEmpty()){
                last=null;
            }
            return oldFirst.item;
        }
    
    
        @Override
        public Iterator<T> iterator() {
            return new QIterator();
        }
    
        private class QIterator implements Iterator{
            private Node n;
    
            public QIterator(){
                this.n=head;
            }
            @Override
            public boolean hasNext() {
                return n.next!=null;
            }
    
            @Override
            public Object next() {
                n = n.next;
                return n.item;
            }
        }
    
    
    }
    
    

    更多相关内容
  • 主要介绍了Python数据结构与算法之的广度优先与深度优先搜索算法,结合实例形式分析了的广度优先与深度优先搜索算法原理与相关实现技巧,需要的朋友可以参考下
  • 12 设计成绩 姓名 班级 学号 指导教师 深度优先搜索遍历算法分析及其应用 摘 要:文章介绍了图论的基本概念及其的表示方法详细的分析了中以邻接表为 存储结构进行的深度优先搜索遍历的算法并且在 VC++...
  • 介绍了数据结构中图的基本概念,并以渭河流域西部重点水源工程联合...应用图深度优先搜索技术,并采用数据库及可视化编程技术,进行了来水量关系分析与计算,为多水源工程联合调度和防洪决策支持系统自动化提供依据。
  • MATLAB源码集锦-基于深度优先搜索算法图论代码
  • 代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码...
  • 深度优先搜索即是 从起点出发,从规定的方向中选择一个不断往前走,走到头为止,然后尝试另一种方向直到最后的终点。 DFS解决的是连通性问题,即从A是否能到达B。采用DFS进行遍历的话,必须依赖栈,后进先出。 ...

            深度优先搜索即是 从起点出发,从规定的方向中选择一个不断往前走,走到头为止,然后尝试另一种方向直到最后的终点。

    DFS解决的是连通性问题,即从A是否能到达B。 采用DFS进行遍历的话,必须依赖栈,后进先出。 

            

    假设有一个图,里面有ABCDEFGH 8 个顶点,对这个图进行深度优先的遍历

    第一步 选择一个起始顶点,例如从顶点 A 开始。把 A 压入栈,标记它为访问过(用红色标记),并输出到结果中。

     

    第二步 寻找与 A 相连并且还没有被访问过的顶点,顶点 A BDG 相连,而且它们都还没有被访问过,我们按照字母顺序处理,所以将 B 压入栈,标记它为访问过,并输出到结果中。

     

    第三步 现在我们在顶点 B 上,重复上面的操作,由于 B AEF 相连,如果按照字母顺序处理的话,A 应该是要被访问的,但是 A 已经被访问了,所以我们访问顶点 E,将 E 压入栈,标记它为访问过,并输出到结果中。

     

    第四步 E 开始, E B G 相连,但是 B 刚刚被访问过了,所以下一个被访问的将是 G ,把 G 压入栈,标记它为访问过,并输出到结果中。

    第五步 现在我们在顶点 G 的位置,由于与 G 相连的顶点都被访问过,所以我们这里要做的就是将 G 从栈里弹出,表示我们从 G 这里已经无法继续走下去了,看看能不能从前一个路口找到出路。
    如果发现周围的顶点都被访问了,就把当前的顶点弹出。
    第六步 现在栈的顶部记录的是顶点 E ,我们来看看与 E 相连的顶点中有没有还没被访问到的,发现它们都被访问了,所以把 E 也弹出去

    第七步 当前栈的顶点是 B ,看看它周围有没有还没被访问的顶点,有,是顶点 F ,于是把 F 压入栈,标记它为访问过,并输出到结果中。

    第八步  当前顶点是 F ,与 F 相连并且还未被访问到的点是 C D ,按照字母顺序来,下一个被访问的点是 C ,将 C 压入栈,标记为访问过,输出到结果中。

    第九步 当前顶点为 C ,与 C 相连并尚未被访问到的顶点是 H ,将 H 压入栈,标记为访问过,输出到结果中。

    第十步 当前顶点是 H,由于和它相连的点都被访问过了,将它弹出栈。

    第十一步 当前顶点是 C ,与 C 相连的点都被访问过了,将 C 弹出栈。

     

    第十二步 当前顶点是 F ,与 F 相连的并且尚未访问的点是 D ,将 D 压入栈,输出到结果中,并标记为访问过。

    第十三步 当前顶点是 D ,与它相连的点都被访问过了,将它弹出栈。以此类推,顶点 F B A 的邻居都被访问过了,将它们依次弹出栈就好了。最后,当栈里已经没有顶点需要处理了,我们的整个遍历结束。

     

    时间复杂度
            
    采用邻接表方式实现
    访问所有顶点的时间为 O(V) ,而查找所有顶点的邻居一共需要 O(E) 的时间,所以总的时间复杂度是O(V + E)。
    采用邻接矩阵方式实现
    查找每个顶点的邻居需要 O(V) 的时间,所以查找整个矩阵的时候需要 O(V^2) 的时间
    展开全文
  • 所谓的深度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,子节点找完了,再找兄弟结点。 无向中,一条边在邻接表中出现两次,搜索子节点的时候需要判断此边是否之前被...

    一.概述

    所谓的深度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,子节点找完了,再找兄弟结点

    在这里插入图片描述
    无向图中,一条边在邻接表中出现两次,搜索子节点的时候需要判断此边是否之前被搜索过,如0-6 6-0 ,不能从6再往0方向区搜索,会重复。

    从顶点0出发,遍历0的邻接表,找到第一个6 ;
    继续递归dfs从6出发 ,遍历6的邻接表,0搜索过,找到4 ;
    继续递归dfs从4出发,找到5;
    继续递归dfs从5出发,遍历5的邻接表,找到3;
    继续递归dfs从3出发,遍历3的邻接表,找到5搜索过,找到4 也搜索过,子节点搜索完毕,递归在此出口结束,开始退回去找兄弟节点;
    往回返到5的邻接表,找3的兄弟节点,3搜过了,4搜过了,0搜过了,3完毕
    往回返到4的邻接表,找5的兄弟节点,5搜过了,6搜过了,3搜过了,5完毕
    往回返到6的邻接表,找4的兄弟节点,0搜索过,4搜索过,4完毕
    往回返到0的邻接表,找6的兄弟节点,2没搜过!

    二.实现

    在这里插入图片描述

    public class GraphDFS {
        private boolean[] marked;  //marked数组的索引代表了顶点!
        private int count;  //与s顶点相同的顶点的个数
    7
        public GraphDFS(graph g, int s) {
        //初始化marked数组
            this.marked=new boolean[g.V()];   //marked和graph的定点数量一致都是 g.v()
        //初始化跟顶点s相通的顶点数量
            this.count=0;
            dfs(g,s); // 构造方法 调成员函数!!!       搜索与顶点相同的所有顶点
        }
    
        private void dfs(graph g,int v){  //使用深度优先搜索找出与v相通的顶点
        //将v标记为搜过
            marked[v]=true;
        //遍历当前顶点的邻接表(一个LinkedList),如果搜过了就找下一个,如果没有则递归dfs深度搜索
            for (Integer k : g.adj(v)) {
                //判断当前k顶点有没有被搜索过
                 if(!marked[k]){  //如果k没被搜索过则递归,如果已经搜过了则不进入递归,即递归出口
                    dfs(g,k);  //递归dfs
                } 
            }
            //递归完后, 与s顶点相通的数量+1
            count++;
        }
    
        public int count(){  //获取与顶点s相通的所有顶点的总数
            return count;
        }
    
        public boolean marked(int w){  //返回顶点是否被搜索过
            return marked[w];
        }
    
        public static void main(String[] args) {
            //准备一个graph
            graph g = new graph(13);
            g.addEdge(0,5);
            g.addEdge(0,1);
            g.addEdge(0,2);
            g.addEdge(0,6);
            g.addEdge(5,3);
            g.addEdge(5,4);
            g.addEdge(3,4);
            g.addEdge(4,6);
            g.addEdge(0,5);
    
            g.addEdge(7,8);
            g.addEdge(9,11);
            g.addEdge(9,10);
            g.addEdge(9,12);
    
            //准备dfs搜索对象(dfs方法在构造方法中调用!一初始化就搜索完毕了)
            GraphDFS search = new GraphDFS(g, 0);//传入图g,起点为0
            //测试与某个顶点相同的数量
            int c = search.count();
            //测试某个顶点与起点是否相同
            System.out.println("与起点相通的顶点的个数为:"+c);
      boolean m1 = search.marked(5);
            System.out.println("顶点5和0是否相通:"+m1);
    
            boolean m2=search.marked(7);
            System.out.println("顶点7和0是否相通:"+m2);
        }
    }
    

    if判断视为递归的出口 ,当邻接表都被标记过了,则返回上一层。

    展开全文
  • 以邻接表为存储结构,实现连通无向深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 注: 1.代码共182行。 2.代码经过多次编译运行,无错误。
  • 深度优先搜索_matlab

    2022-04-08 23:12:01
    资源名:深度优先搜索_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定经验的开发人员
  • 1.深度优先搜索 深度优先搜索,Depth First Search,简称DFS。 对于一个连通,深度优先遍历的过程: 从中一个顶点 vvv 出发并访问 vvv 。 找到刚访问顶点的第一个未被访问的邻接点并访问,并继续以该邻接点...

    关于邻接矩阵和邻接表

    下面都以此图进行遍历:
    在这里插入图片描述

    1.深度优先搜索

    深度优先搜索,Depth First Search,简称DFS。

    对于一个连通图,深度优先遍历的过程:

    1. 从图中一个顶点 v v v 出发并访问 v v v
    2. 找到刚访问顶点的第一个未被访问的邻接点并访问,并继续以该邻接点作为刚访问过的顶点,重复此步骤直到刚访问过的结点没有未被访问的邻接点为止。
    3. 返回上一个访问过的且还有未被访问邻接点的顶点,继续访问这个顶点的下一个未被访问的邻接点。
    4. 重复2, 3,直到图中所有顶点都被访问。

    它的思想是从一个顶点 v v v 开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个结点,然后从另一条路开始走到底,这种尽量往深处走的概念即是深度优先的概念。类似树的先序遍历。

    邻接矩阵的深度优先遍历

    对上面这个图深度优先遍历的一个顺序为:ABDHECFG。深度优先遍历的顺序不唯一,因为顶点B的第一个邻接点既可以认为是顶点D,也可以认为是顶点E。

    java代码:

    public class DFS_AM {
    	char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
    	int[][] matrix = new int[8][8];
    
    	// 创建邻接矩阵
    	private void creatMartix() {
    		matrix[locate('A')][locate('B')] = matrix[locate('B')][locate('A')] = 1;
    		matrix[locate('B')][locate('D')] = matrix[locate('D')][locate('B')] = 1;
    		matrix[locate('B')][locate('E')] = matrix[locate('E')][locate('B')] = 1;
    		matrix[locate('D')][locate('H')] = matrix[locate('H')][locate('D')] = 1;
    		matrix[locate('E')][locate('H')] = matrix[locate('H')][locate('E')] = 1;
    		matrix[locate('A')][locate('C')] = matrix[locate('C')][locate('A')] = 1;
    		matrix[locate('C')][locate('F')] = matrix[locate('F')][locate('C')] = 1;
    		matrix[locate('C')][locate('G')] = matrix[locate('G')][locate('C')] = 1;
    		matrix[locate('F')][locate('G')] = matrix[locate('G')][locate('F')] = 1;
    	}
    
    	private int locate(char v) {
    		int i = 0;
    		for (; i < vertex.length; i++) {
    			if (v == vertex[i])
    				break;
    		}
    		return i;
    	}
    
    	// 顶点访问标记,visited[i]=false表示顶点vertex[i]未被访问,反之表示已经访问过,初始默认值false
    	boolean[] visited = new boolean[vertex.length];
    
    	private void dfs(char v) {
    		// 访问第一个顶点
    		System.out.print(v + " ");
    		// 标记该顶点被访问过
    		visited[locate(v)] = true;
    		for (int j = 0; j < matrix.length; j++) {
    			// 找到刚访问顶点的一个未被访问过的邻接点
    			if (matrix[locate(v)][j] == 1 && visited[j] == false) {
    				// 以该邻接点作为新的顶点递归访问
    				dfs(vertex[j]);
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		DFS_AM am = new DFS_AM();
    		am.creatMartix();
    		am.dfs('A');
    	}
    }
    

    邻接表的深度优先遍历

    public class DFS_AL {
    	class VertexNode {
    		char verName;
    		EdgeNode next;
    
    		public VertexNode(char verName) {
    			this.verName = verName;
    		}
    	}
    
    	class EdgeNode {
    		int index;
    		EdgeNode next;
    
    		public EdgeNode(int index) {
    			this.index = index;
    		}
    	}
    
    	VertexNode[] vertex = { new VertexNode('A'), 
    							new VertexNode('B'), 
    							new VertexNode('C'), 
    							new VertexNode('D'),
    							new VertexNode('E'), 
    							new VertexNode('F'), 
    							new VertexNode('G'), 
    							new VertexNode('H') };
    
    	private int locate(char v) {
    		int index = 0;
    		for (; index < vertex.length; index++) {
    			if (v == vertex[index].verName)
    				break;
    		}
    		return index;
    	}
    
    	// 创建邻接表
    	private void creatList() {
    		vertex[locate('A')].next = new EdgeNode(locate('B'));
    		vertex[locate('A')].next.next = new EdgeNode(locate('C'));
    
    		vertex[locate('B')].next = new EdgeNode(locate('A'));
    		vertex[locate('B')].next.next = new EdgeNode(locate('D'));
    		vertex[locate('B')].next.next.next = new EdgeNode(locate('E'));
    
    		vertex[locate('C')].next = new EdgeNode(locate('A'));
    		vertex[locate('C')].next.next = new EdgeNode(locate('F'));
    		vertex[locate('C')].next.next.next = new EdgeNode(locate('G'));
    
    		vertex[locate('D')].next = new EdgeNode(locate('B'));
    		vertex[locate('D')].next.next = new EdgeNode(locate('H'));
    
    		vertex[locate('E')].next = new EdgeNode(locate('B'));
    		vertex[locate('E')].next.next = new EdgeNode(locate('H'));
    
    		vertex[locate('F')].next = new EdgeNode(locate('C'));
    		vertex[locate('F')].next.next = new EdgeNode(locate('G'));
    
    		vertex[locate('G')].next = new EdgeNode(locate('C'));
    		vertex[locate('G')].next.next = new EdgeNode(locate('F'));
    
    		vertex[locate('H')].next = new EdgeNode(locate('D'));
    		vertex[locate('H')].next.next = new EdgeNode(locate('E'));
    	}
    
    	boolean[] visited = new boolean[vertex.length];
    
    	private void dfs(char v) {
    		// 访问第一个顶点
    		System.out.print(v + " ");
    		// 标记
    		visited[locate(v)] = true;
    		// 找到访问顶点的一个邻接点
    		EdgeNode node = vertex[locate(v)].next;
    
    		while (node != null) {
    			// 如果这个邻接点没有被访问,作为新顶点递归访问
    			if (visited[node.index] == false) {
    				dfs(vertex[node.index].verName);
    			}
    			// 遍历作为底层顶点的所有邻接点
    			node = node.next;
    		}
    	}
    
    	public static void main(String[] args) {
    		DFS_AL al = new DFS_AL();
    		al.creatList();
    		al.dfs('A');
    	}
    }
    

    深度优先遍历的时间复杂度及空间复杂度分析

    时间复杂度
    遍历图时,对图中的每个顶点最多调用一次dfs方法,某个顶点被标记访问过,就不再从它出发调用。因此遍历图的过程其实是对每个顶点查找其邻接点的过程。对于一个含有 n 个顶点和 e 条边的图:

    • 邻接矩阵因为对每个顶点 v 都要通过遍历一次一维数组 matrix[v][ ]找到它的所有邻接点,对应的时间复杂度 O ( n ) Ο(n) O(n),所以总的时间复杂度 O ( n 2 ) Ο(n^2) O(n2)
    • 邻接表因为本身存储的就是有相连关系的邻接点,所以查找所有顶点的邻接点的时间复杂度为 O ( e ) Ο(e) O(e)。又因为对每个顶点都要进行一次查找,所以总的时间复杂度 O ( n + e ) Ο(n+e) O(n+e)

    空间复杂度
    都包括标记数组的空间和递归过程中开辟的系统空间栈。

    2.广度优先搜索

    广度优先搜索,Breadth First Search,简称BFS。

    对一个连通图进行广度优先遍历的步骤是:

    1. 从图中的一个顶点 v v v 出发并访问。
    2. 访问顶点 v v v 的所有邻接点。
    3. 按照邻接点的访问顺序访问邻接点的所有邻接点。
    4. 重复步骤3,直到图中所有的顶点都被访问。

    可以看出广度优先遍历是从图中的某个顶点出发,以这个顶点为中心由内往外一层一层的完成遍历,类似树的层序遍历。

    因为根据算法先被访问的顶点的邻接点也先被访问,所以遍历过程需要借助队列来保存访问过的顶点。

    邻接矩阵的广度优先遍历

    上图的一个广度优先遍历序列为:ABCDEFGH。广度优先遍历得到的序列也不唯一,因为对一个顶点的所有邻接点进行访问的时候这些邻接点的先后访问顺序可以不同。

    import java.util.LinkedList;
    import java.util.Queue;
    
    public class BFS_AM {
    	char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
    	int[][] matrix = new int[8][8];
    
    	// 创建邻接矩阵
    	private void creatMartix() {
    		matrix[locate('A')][locate('B')] = matrix[locate('B')][locate('A')] = 1;
    		matrix[locate('B')][locate('D')] = matrix[locate('D')][locate('B')] = 1;
    		matrix[locate('B')][locate('E')] = matrix[locate('E')][locate('B')] = 1;
    		matrix[locate('D')][locate('H')] = matrix[locate('H')][locate('D')] = 1;
    		matrix[locate('E')][locate('H')] = matrix[locate('H')][locate('E')] = 1;
    		matrix[locate('A')][locate('C')] = matrix[locate('C')][locate('A')] = 1;
    		matrix[locate('C')][locate('F')] = matrix[locate('F')][locate('C')] = 1;
    		matrix[locate('C')][locate('G')] = matrix[locate('G')][locate('C')] = 1;
    		matrix[locate('F')][locate('G')] = matrix[locate('G')][locate('F')] = 1;
    	}
    
    	private int locate(char v) {
    		int i = 0;
    		for (; i < vertex.length; i++) {
    			if (v == vertex[i])
    				break;
    		}
    		return i;
    	}
    
    	boolean[] visited = new boolean[vertex.length];
    	// 辅助队列,保存访问过的顶点
    	Queue<Character> q = new LinkedList<>();
    
    	private void bfs(char v) {
    		// 访问第一个顶点
    		System.out.print(v + " ");
    		// 访问标记
    		visited[locate(v)] = true;
    		// 访问过的顶点入队
    		q.add(v);
    		while(!q.isEmpty()) {
    			char c =  q.remove();
    			for(int i=0;i<matrix.length;i++) {
    				// 访问出队顶点的所有未被访问过的邻接点
    				if(matrix[locate(c)][i]==1 && visited[i]==false) {
    					System.out.print(vertex[i]+" ");
    					visited[i]=true;
    					q.add(vertex[i]);
    				}
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		BFS_AM am = new BFS_AM();
    		am.creatMartix();
    		am.bfs('A');
    	}
    }
    

    邻接表的广度优先遍历

    import java.util.LinkedList;
    import java.util.Queue;
    
    public class BFS_AL {
    	class VertexNode {
    		char verName;
    		EdgeNode next;
    
    		public VertexNode(char verName) {
    			this.verName = verName;
    		}
    	}
    
    	class EdgeNode {
    		int index;
    		EdgeNode next;
    
    		public EdgeNode(int index) {
    			this.index = index;
    		}
    	}
    
    	VertexNode[] vertex = { new VertexNode('A'), 
    							new VertexNode('B'), 
    							new VertexNode('C'), 
    							new VertexNode('D'),
    							new VertexNode('E'), 
    							new VertexNode('F'), 
    							new VertexNode('G'), 
    							new VertexNode('H') };
    
    	private int locate(char v) {
    		int index = 0;
    		for (; index < vertex.length; index++) {
    			if (v == vertex[index].verName)
    				break;
    		}
    		return index;
    	}
    
    	// 创建邻接表
    	private void creatList() {
    		vertex[locate('A')].next = new EdgeNode(locate('B'));
    		vertex[locate('A')].next.next = new EdgeNode(locate('C'));
    
    		vertex[locate('B')].next = new EdgeNode(locate('A'));
    		vertex[locate('B')].next.next = new EdgeNode(locate('D'));
    		vertex[locate('B')].next.next.next = new EdgeNode(locate('E'));
    
    		vertex[locate('C')].next = new EdgeNode(locate('A'));
    		vertex[locate('C')].next.next = new EdgeNode(locate('F'));
    		vertex[locate('C')].next.next.next = new EdgeNode(locate('G'));
    
    		vertex[locate('D')].next = new EdgeNode(locate('B'));
    		vertex[locate('D')].next.next = new EdgeNode(locate('H'));
    
    		vertex[locate('E')].next = new EdgeNode(locate('B'));
    		vertex[locate('E')].next.next = new EdgeNode(locate('H'));
    
    		vertex[locate('F')].next = new EdgeNode(locate('C'));
    		vertex[locate('F')].next.next = new EdgeNode(locate('G'));
    
    		vertex[locate('G')].next = new EdgeNode(locate('C'));
    		vertex[locate('G')].next.next = new EdgeNode(locate('F'));
    
    		vertex[locate('H')].next = new EdgeNode(locate('D'));
    		vertex[locate('H')].next.next = new EdgeNode(locate('E'));
    	}
    
    	boolean[] visited = new boolean[vertex.length];
    	Queue<Character> q = new LinkedList<>();
    
    	private void bfs(char v) {
    		// 访问第一个顶点
    		System.out.print(v + " ");
    		// 访问标记
    		visited[locate(v)] = true;
    		q.add(v);
    		while (!q.isEmpty()) {
    			char c = q.remove();
    			// 找到访问顶点的第一个邻接点
    			EdgeNode node = vertex[locate(c)].next;
    			while (node != null) {
    				// 邻接点存在访问并修改访问标记,并且将访问过的邻接点入队
    				if (visited[node.index] == false) {
    					System.out.print(vertex[node.index].verName + " ");
    					visited[locate(vertex[node.index].verName)] = true;
    					q.add(vertex[node.index].verName);
    				}
    				// 寻找访问顶点的下一个邻接点
    				node = node.next;
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		BFS_AL al = new BFS_AL();
    		al.creatList();
    		al.bfs('A');
    	}
    }
    

    广度优先遍历的时间复杂度及空间复杂度分析

    时间复杂度
    广度优先遍历每个顶点最多进入一次队列,与深度优先的区别仅是对不同顶点邻接点的访问顺序不同,所以广度优先的时间复杂度与深度优先相等。

    • 对于邻接矩阵,广度优先的时间复杂度 O ( n 2 ) Ο(n^2) O(n2)
    • 对于邻接表,广度优先的时间复杂度 O ( n + e ) Ο(n+e) O(n+e)

    空间复杂度
    与深度优先相比少用了递归时占用的系统空间栈,多了一个辅助队列。

    展开全文
  • 本文实例讲述了的遍历中深度优先搜索的C++实现方法,是一种非常重要的算法,具体实现方法如下: 首先,的遍历是指从中的某一个顶点出发,按照某种搜索方法沿着中的边对图中的所有顶点访问一次且仅访问一次。...
  • 本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题。分享给大家供大家参考,具体如下: 深度优先搜索 伪代码 (Pseudocode)如下: 将起点标记为已走过并压栈; while (栈非空) { 从栈顶弹出一个点p; if (p这个...
  • 数据结构的邻接矩阵,邻接表存储表示,深度优先搜索遍历,广度优先搜索遍历 数据结构的邻接矩阵,邻接表存储表示,深度优先搜索遍历,广度优先搜索遍历.rar
  • 人工智能的作业,用深度优先遍历实现八数码问题,可以设置搜索深度。 人工智能的作业,用深度优先遍历实现八数码问题,可以设置搜索深度。
  • DFS——深度优先搜索

    2022-03-17 21:52:29
    DFS,中文名深度优先搜索,是一种的搜索方式,本质上是一种递归。 dfs相当自由,学dfs可能最高境界就和打太极似的,无招胜有招 DFS的经典应用: 1.全排列 虽然感觉没有贴题目的必要 这应该是大多数...
  • 一、递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1、写出临界条件 2、找出这一次和上一次关系 3、假设当前函数已经能用...
  • C#深度优先搜索算法

    2020-12-31 04:14:31
    本文实例为大家分享了C#深度优先搜索算法的具体代码,供大家参考,具体内容如下 //论文要用到其改进算法,在此先demo测试一下 using System; using System.Collections.Generic; using System.Linq; using System....
  • 一、无向 1.1 的相关术语 相邻顶点: 当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这条边依附于这两个顶点。 度: 某个顶点的度就是依附于该顶点的边的个数。 子图: 是一幅的所有边的子集...
  • DFS(Depth-First-Search)深度优先搜索算法是的遍历算法中非常常见的一类算法。分享给大家供大家参考。具体方法如下: #include #include #include using namespace std; #define MAX_VERTEX_NUM 10 struct ...
  • 1.前言 和树的遍历类似,的遍历也是从中某点出发...根据搜索路径的不同,我们可以将遍历的方法分为两种:广度优先搜索和深度优先搜索。 2.的基本概念 无向:顶点对(u,v)是无序的,即(u,v)和(v,u)是...
  • 图深度优先搜索C++

    2011-12-13 12:45:13
    图深度优先搜索C++,详细,无错误,精练,准确
  • 的遍历(深度优先搜索

    万次阅读 多人点赞 2017-10-19 16:52:01
    它的思想:假设初始状态是中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历,直至中所有和v有路径相通的顶点都被访问到。 若此时尚有其他...
  • 无向深度优先搜索算法/c语言实现 其中采用邻接矩阵存储
  • 针对电网故障事件等级判定需要自动识别电力故障元器件的问题,文中提出了一种基于深度优先搜索算法的电力系统拓扑建模方法。首先根据电气元件端子数建立了各元器件的数据表;然后根据各端子连接情况,构建配电网拓扑...
  • 深度优先搜索 类似树的深度优先遍历,所谓深度优先即递归的对相邻节点进行访问。从来访问的越来越深。... * 深度优先搜索 * @author yjw * @date 2019/5/16/016 */ public class DepthF...
  • ——有向深度优先搜索

    千次阅读 2018-12-18 19:52:49
    采用邻接矩阵表示存储有向 #include&lt;stdio.h&gt; #define MAX_VERTEX_NUM 20 #define INFINITY 32768 #define True 1 #define False 0 #define Error -1 #define OK 1 #include&lt;stdio.h...
  • 深度优先搜索算法和广度优先搜索算法都是基于“”这种数据结构的。 作为的搜索算法,既可用于有向,也可用于无向,以下均用无向讲解。 广度优先搜索 Breadth-First-Search,BFS。 一种“地毯式”层层推进...
  • 1.深度优先搜索的思想:给定G=(V,E)。深度优先搜索的思想为:初始时,所有顶点均为未被访问过,任选一个顶点v作为源点。该方法先访问源点v,并将其标记为已访问过;然后从v点出发,选择v的下一个邻接点(子节点)w...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 111,082
精华内容 44,432
关键字:

图的深度优先搜索

友情链接: DNSProxy.rar