精华内容
下载资源
问答
  • 深度优先遍历和广度优先遍历

    万次阅读 多人点赞 2019-05-29 21:24:38
    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。 这两种遍历方式有什么不同呢?我们来举个栗子: 我们来到一个游乐场,游乐场里有...

    深度优先遍历和广度优先遍历
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    什么是 深度/广度 优先遍历?

    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。

    这两种遍历方式有什么不同呢?我们来举个栗子:

    我们来到一个游乐场,游乐场里有11个景点。我们从景点0开始,要玩遍游乐场的所有景点,可以有什么样的游玩次序呢?

    在这里插入图片描述
    第一种是一头扎到底的玩法。我们选择一条支路,尽可能不断地深入,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入。

    在图中,我们首先选择景点1的这条路,继续深入到景点7、景点8,终于发现走不动了(景点旁边的数字代表探索次序):
    在这里插入图片描述
    于是,我们退回到景点7,然后探索景点10,又走到了死胡同。于是,退回到景点1,探索景点9:
    在这里插入图片描述
    按照这个思路,我们再退回到景点0,后续依次探索景点2、3、5、4、6,终于玩遍了整个游乐场:
    在这里插入图片描述
    像这样先深入探索,走到头再回退寻找其他出路的遍历方式,就叫做深度优先遍历(DFS)。
    在这里插入图片描述
    在这里插入图片描述
    除了像深度优先遍历这样一头扎到底的玩法以外,我们还有另一种玩法:首先把起点相邻的几个景点玩遍,然后去玩距离起点稍远一些(隔一层)的景点,然后再去玩距离起点更远一些(隔两层)的景点…

    在图中,我们首先探索景点0的相邻景点1、2、3、4:
    在这里插入图片描述
    接着,我们探索与景点0相隔一层的景点7、9、5、6:
    在这里插入图片描述
    最后,我们探索与景点0相隔两层的景点8、10:
    在这里插入图片描述
    像这样一层一层由内而外的遍历方式,就叫做广度优先遍历(BFS)。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    深度优先遍历

    首先说说深度优先遍历的实现过程。这里所说的回溯是什么意思呢?回溯顾名思义,就是自后向前,追溯曾经走过的路径。

    我们把刚才游乐场的例子抽象成数据结构的图,假如我们依次访问了顶点0、1、7、8,发现无路可走了,这时候我们要从顶点8退回到顶点7。

    在这里插入图片描述
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190529211147549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyMjE3MDE4MTAz,size_16,color_FFFFFF,t_70

    而后我们探索了顶点10,又无路可走了,这时候我们要从顶点10退回到顶点7,再退回到顶点1。
    在这里插入图片描述
    像这样的自后向前追溯曾经访问过的路径,就叫做回溯。

    要想实现回溯,可以利用栈的先入后出特性,也可以采用递归的方式(因为递归本身就是基于方法调用栈来实现)。

    下面我们来演示一下具体实现过程。

    首先访问顶点0、1、7、8,这四个顶点依次入栈,此时顶点8是栈顶:
    在这里插入图片描述
    从顶点8退回到顶点7,顶点8出栈:
    在这里插入图片描述
    接下来访问顶点10,顶点10入栈:
    在这里插入图片描述
    从顶点10退到顶点7,从顶点7退到顶点1,顶点10和顶点7出栈:
    在这里插入图片描述
    探索顶点9,顶点9入栈:
    在这里插入图片描述
    以此类推,利用这样一个临时栈来实现回溯,最终遍历完所有顶点。

    广度优先遍历

    接下来该说说广度优先遍历的实现过程了。刚才所说的重放是什么意思呢?似乎听起来和回溯差不多?其实,回溯与重放是完全相反的过程。

    仍然以刚才的图为例,按照广度优先遍历的思想,我们首先遍历顶点0,然后遍历了邻近顶点1、2、3、4:

    在这里插入图片描述
    接下来我们要遍历更外围的顶点,可是如何找到这些更外围的顶点呢?我们需要把刚才遍历过的顶点1、2、3、4按顺序重新回顾一遍,从顶点1发现邻近的顶点7、9;从顶点3发现邻近的顶点5、6。
    在这里插入图片描述
    像这样把遍历过的顶点按照之前的遍历顺序重新回顾,就叫做重放。同样的,要实现重放也需要额外的存储空间,可以利用队列的先入先出特性来实现。

    下面我们来演示一下具体实现过程。
    首先遍历起点顶点0,顶点0入队:
    在这里插入图片描述
    接下来顶点0出队,遍历顶点0的邻近顶点1、2、3、4,并且把它们入队:
    在这里插入图片描述
    然后顶点1出队,遍历顶点1的邻近顶点7、9,并且把它们入队:
    在这里插入图片描述
    然后顶点2出队,没有新的顶点可入队:
    在这里插入图片描述
    以此类推,利用这样一个队列来实现重放,最终遍历完所有顶点。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    /**

    图的顶点
    
    / private static class Vertex { int data; Vertex(int data) {    this.data = data; } } /*
    
    图(邻接表形式)
    
    / private static class Graph { private int size; private Vertex[] vertexes; private LinkedList adj[]; Graph(int size){    this.size = size;    //初始化顶点和邻接矩阵    vertexes = new Vertex[size];    adj = new LinkedList[size];    for(int i=0; i*
    
    深度优先遍历
    
    / public static void dfs(Graph graph, int start, boolean[] visited) { System.out.println(graph.vertexes[start].data); visited[start] = true; for(int index : graph.adj[start]){    if(!visited[index]){        dfs(graph, index, visited);    } } } /*
    
    广度优先遍历
    
    */
    
    public static void bfs(Graph graph, int start, boolean[] visited, LinkedList queue) {
    
    queue.offer(start);
    
    while (!queue.isEmpty()){
    
       int front = queue.poll();
    
       if(visited[front]){
    
           continue;
    
       }
    
       System.out.println(graph.vertexes[front].data);
    
       visited[front] = true;
    
       for(int index : graph.adj[front]){
    
           queue.offer(index);;
    
       }
    
    }
    
    }
    
    public static void main(String[] args) {
    
    Graph graph = new Graph(6);
    
    graph.adj[0].add(1);
    
    graph.adj[0].add(2);
    
    graph.adj[0].add(3);
    
    graph.adj[1].add(0);
    
    graph.adj[1].add(3);
    
    graph.adj[1].add(4);
    
    graph.adj[2].add(0);
    
    graph.adj[3].add(0);
    
    graph.adj[3].add(1);
    
    graph.adj[3].add(4);
    
    graph.adj[3].add(5);
    
    graph.adj[4].add(1);
    
    graph.adj[4].add(3);
    
    graph.adj[4].add(5);
    
    graph.adj[5].add(3);
    
    graph.adj[5].add(4);
    
    System.out.println("图的深度优先遍历:");
    
    dfs(graph, 0, new boolean[graph.size]);
    
    System.out.println("图的广度优先遍历:");
    
    bfs(graph, 0, new boolean[graph.size], new LinkedList());
    
    }
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 邻接表法创建 广度优先遍历
  • 邻接矩阵实现,Java实现数据结构,Java实现的深度优先遍历,广度优先遍历

    **

    Java实现数据结构,邻接矩阵实现图,Java实现图的深度、广度优先遍历

    **
    目录:

    1. 前言
    2. 深度预先遍历
    3. 广度优先遍历

    前言:
    首先这里主要讲Java实现图的深度和广度优先遍历,邻接矩阵实现图。
    深度优先和广度优先首先是不难,你之所以会来查找如何实现深度优先和广度优先,我觉得是你的深度广度的逻辑不懂,这里会告诉你深度广度的逻辑是什么。然后用代码于实现。
    示例图片
    图是无序图,A、B、C、D、E对应0、1、2、3、4
    **

    深度优先

    **:
    深度优先顾名思义就是:深是遍历的原则(深就是长驱直入),比如我们从A开始寻找,只要找到A的下一个邻接结点(就是和A相连的结点)就可以,找到的是B,再从B开始找B的下一个邻接结点找到的是C,在从C开始找C的邻接结点,(找过的就不在找),没有找到。这时我们说A的深度优先遍历就结束了,再开始B的深度优先遍历。
    深度优先简单来说,就是,长驱直入,不管有几个邻接结点,找到一个就行,找不到就从下一个结点开始深度优先遍历。
    代码实现:

    在这里插入代码片
    /**
     * 
     * @author 楠
     *
     */
    //图
    class graph{
    	public ArrayList<String> vertex;//存储结点的字符串数组
    	public int[][] edges;//邻接矩阵
    	public int numOfEdge;//边的个数
    	public boolean[] isVisited;//辅助遍历工具,用来判断一个结点是否被访问过
    	//构造器
    	public graph(int n) {//初始化图
    		vertex=new ArrayList<String>(n);
    		edges=new int[n][n];
    		numOfEdge=0;
    	}
    	//深度优先遍历图
    	public void dfs() {//对每一个结点都进行深度优先遍历
    		isVisited=new boolean[vertex.size()];//初始化辅助工具,初始均为未被访问
    		for(int i=0;i<vertex.size();i++) {
    			if(isVisited[i]) {//被访问就跳过
    				continue;
    			}else {
    				dfs(i);
    			}
    		}
    	}
    	private void dfs(int i) {//对结点i进行深度优先遍历
    		System.out.print(getValueOfVertex(i)+"---");
    		isVisited[i]=true;
    		int n=getFirst(i);//查找i的邻接结点
    		if(n!=-1) {//找到了
    			dfs(n);
    		}else {
    			return;
    		}
    	}
    	/**
    	 * 
    	 * @param i 给定结点的下标,
    	 * @return	返回结点i的第一个且没有被访问过的邻接结点,没有返回-1
    	 */
    	private int getFirst(int i) {
    		for(int j=0;j<vertex.size();j++) {
    			if(edges[i][j]>0&&!isVisited[j]) {
    				return j;
    			}
    		}
    		return -1;
    	}
    	
    	/*
    		一下都是图的基本操作
    	*/
    	
    	//添加结点
    	public void add(String str) {
    		vertex.add(str);
    	}
    	//添加边
    	public void addEdges(int a,int b,int value) {
    		edges[a][b]=value;
    		edges[b][a]=value;
    		numOfEdge++;
    	}
    	//返回结点的个数
    	public int getNumOfVertex() {
    		return vertex.size();
    	}
    	//根据结点返回权值
    	public int getValue(int a,int b) {
    		return edges[a][b];
    	}
    	//显示图对应的矩阵
    	public void show() {
    		for(int[] arr:edges) {
    			System.out.println(Arrays.toString(arr));
    		}
    	}
    	//返回边的数目
    	public int getNumEdges() {
    		return numOfEdge;
    	}
    	//返回下标对应的结点
    	public String getValueOfVertex(int a) {
    		return vertex.get(a);
    	}
    }
    
    

    **

    广度优先:

    **
    广度优先也是顾名思义,横向搜索的广度优先的原则,给一个结点i,找到结点i的所有邻接结点。再从找到的结点当中进行广度优先遍历。
    代码实现:

    在这里插
    /**
     * 
     * @author 楠
     *
     */
    //图
    class graph{
    	public ArrayList<String> vertex;//存储结点的字符串数组
    	public int[][] edges;//邻接矩阵
    	public int numOfEdge;//边的个数
    	public boolean[] isVisited;//辅助遍历工具,用来判断一个结点是否被访问过
    	//构造器
    	public graph(int n) {//初始化图
    		vertex=new ArrayList<String>(n);
    		edges=new int[n][n];
    		numOfEdge=0;
    	}
    	//广度优先遍历图
    	public void bfs() {//广度优先遍历只从一个遍历一次就可以了
    		isVisited=new boolean[vertex.size()];
    		bfs(0);
    		System.out.println();
    	}
    	private void bfs(int i) {
    		LinkedList<Integer> queue = new LinkedList<Integer>();//队列存储遍历出来的结点
    		System.out.print(getValueOfVertex(i)+"--");
    		queue.addLast(i);
    		isVisited[i]=true;	
    		while (!queue.isEmpty()) {//队列空的时候就遍历完了
    			int w=queue.removeFirst();
    			int n=getFirst(w);	
    			while (n!=-1) {//找到所有的邻接结点
    				queue.addLast(n);
    				System.out.print(getValueOfVertex(n)+"--");
    				isVisited[n]=true;
    				n=getFirst(w);
    			}
    		}
    		
    	}
    	/**
    	 * 
    	 * @param i 给定结点的下标,
    	 * @return	返回结点i的第一个且没有被访问过的邻接结点,没有返回-1
    	 */
    	private int getFirst(int i) {
    		for(int j=0;j<vertex.size();j++) {
    			if(edges[i][j]>0&&!isVisited[j]) {
    				return j;
    			}
    		}
    		return -1;
    	}
    	
    	/*
    		一下都是图的基本操作
    	*/
    	
    	//添加结点
    	public void add(String str) {
    		vertex.add(str);
    	}
    	//添加边
    	public void addEdges(int a,int b,int value) {
    		edges[a][b]=value;
    		edges[b][a]=value;
    		numOfEdge++;
    	}
    	//返回结点的个数
    	public int getNumOfVertex() {
    		return vertex.size();
    	}
    	//根据结点返回权值
    	public int getValue(int a,int b) {
    		return edges[a][b];
    	}
    	//显示图对应的矩阵
    	public void show() {
    		for(int[] arr:edges) {
    			System.out.println(Arrays.toString(arr));
    		}
    	}
    	//返回边的数目
    	public int getNumEdges() {
    		return numOfEdge;
    	}
    	//返回下标对应的结点
    	public String getValueOfVertex(int a) {
    		return vertex.get(a);
    	}
    }
    
    
    展开全文
  • 广度优先遍历-bfs 顾名思义,bfs总是先访问完同一层的结点,然后才继续访问下一层结点,它最有用的性质是可以遍历一次就生成中心结点到所遍历结点的最短路径,这一点在求无权的最短路径时非常有用。广度优先遍历的...

    广度优先遍历-bfs

    顾名思义,bfs总是先访问完同一层的结点,然后才继续访问下一层结点,它最有用的性质是可以遍历一次就生成中心结点到所遍历结点的最短路径,这一点在求无权图的最短路径时非常有用。广度优先遍历的核心思想非常简单,用python实现起来也就十来行代码。下面就是超精简的实现,用来理解核心思想足够了:

    import Queue
    
    def bfs(adj, start):
        visited = set()
        q = Queue.Queue()
        q.put(start)
        while not q.empty():
            u = q.get()
            print(u)
            for v in adj.get(u, []):
                if v not in visited:
                    visited.add(v)
                    q.put(v)
    
    
    graph = {1: [4, 2], 2: [3, 4], 3: [4], 4: [5]}
    bfs(graph, 1)

     

     

     

    上面的代码:

    1 创建一个队列,遍历的起始点放入队列

    2 从队列中取出一个元素,打印它,并将其未访问过的子结点放到队列中

    3 重复2,直至队列空

    时间复杂度:基本与图的规模成线性关系了,比起图的其它算法动不动就O(n^2)的复杂度它算是相当良心了

    空间复杂度:我们看到程序中使用了一个队列,这个队列会在保存一层的结点,当图规模很大时占用内存还是相当可观的了,所以一般会加上一些条件,比如遍历到第N层就停止

     

    关于图的理解的一个技巧

    上面提到,bfs遍历会由近及远,同一层会先遍历完。这里随便提一个关于图的展示问题,或者说当你拿到一个图,当你要对它进行分析时,这个图在你的脑海里会一个什么形态呢?比较一下下面两种形态,你觉得哪一种更加清晰?

    其实你仔细看,左右两张图其实数据是一样的,只是布局不一样罢了,上面的图使用了一种无规律凌乱的布局,而下面假设出了一个中心点,将与它直接相连的结点放在第一层上,与它距离为2的结点放在第二层了,这样会有什么好处呢?好处就是这样布局后边只会在相邻层或者同一层间的结点间相连,这样就不会出现很长或者交叉的边了,整个图会感觉有序得多,在思考图的一些性质的时候也会清晰得多。

    回过头来,这种布局不说是bfs形成的吗。

     

    深度优先遍历

    深度优先遍历算法dfs通俗的说就是“顺着起点往下走,直到无路可走就退回去找下一条路径,直到走完所有的结点”。这里的“往下走”主是优先遍历结点的子结点。bfs与dfs都可以完成图的遍历。dfs常用到爬虫中,下面是最精简的代码:

    def dfs(adj, start):
        visited = set()
        stack = [[start, 0]]
        while stack:
            (v, next_child_idx) = stack[-1]
            if (v not in adj) or (next_child_idx >= len(adj[v])):
                stack.pop()
                continue
            next_child = adj[v][next_child_idx]
            stack[-1][1] += 1
            if next_child in visited:
                continue
            print(next_child)
            visited.add(next_child)
            stack.append([next_child, 0])
    
    
    graph = {1: [4, 2], 2: [3, 4], 3: [4], 4: [5]}
    dfs(graph, 1)

     

    上面的代码是dfs的非递归实现,其实递归的代码更简单,但是我觉得使用了函数的递归调用隐含了对栈的使用但是却没有明确出来,这样不太利于对dfs核心思想的理解,所以这里反而选择了更复杂的非递归实现。

     

    整个程序借助了一个栈,由于python没有直接的实现栈,这里使用了list来模拟,入栈就是向列表中append一个元素,出栈就是取列表最后一个元素然后pop将最后一个元素删除

    下面来分析实现过程,还是按之前的那句话“顺着起点往下走,直到无路可走就退回去找下一条路径,直到走完所有的结点”,整个程序都蕴含在这句话中:

    首次是“顺着起点往下走”中的起点当然就是函数传进来的参数start,第三行中我们把起点放到了栈中,此时栈就是初始状态,其中就只有一个元素即起点。那么栈中元素表示的语义是:下一次将访问的结点,没错就这么简单,那么为什么我们一个结点和一个索引来表示呢?理由是这样的,由于我们使用邻接表来表示图,那么要表示一个结点表可以用<这个结点的父结点、这个结是父结点的第几个子结点>来决定,至于为什么要这么表示,就还是前面说的:由这们这里使用的图的存储方式-邻接表决定了,因为这样我们取第N个兄弟结点要容易了。因为邻接表中用list来表示一个结点的所有子结点,我们就用一个整数的索引值来保存下次要访问的子结点的list的下标,当这个下标超过子结点list的长度时意味着访问完所有子结点。

     

    接着,“往下走”,看这句:next_child = adj[v][next_child_idx]就是我们在这个while循环中每次访问的都是一个子结点,访问完当前结点后stack.append([next_child, 0])将这个结点放到栈中,意思是下次就访问这个结点的子结点,这样就每次都是往下了。

     

    “直到无路可走”,在程序中的体现就是 if (v not in adj) or (next_child_idx >= len(adj[v])):,栈顶元素表示即将要访问的结点的父结点及其是父结点的第N个子结点(有点绕),这里的意思是如果这个父结点都没有子结点了或者是我们想要访问第N个子结点但是父结点并没有这么多子结点,表示已经访问完了一个父结点的所有子结点了。

     

    接着“就退回去找下一条路径”中的“退回去”,怎么退回去,很简单将栈顶元素弹出,新的栈顶元素就是它的父结点,那么就是退回去了,“去找下一条路径”就是弹出栈顶后下一次while中会沿着父结点继续探索,也就是去找下一条路径了。

     

    最后“直到走完所有的结点“当然就是栈为空了,栈为空表示已经回退到起点,即所有结点已经访问完了,整个算法结束。

     

     

    展开全文
  • 深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现
  • 文章目录一、的概述1.1 什么是1.2 对比线性表和树1.3 的常见概念二、的存储方式2.1 邻接矩阵2.2 邻接表三、...广度优先遍历3.2.1 什么是广度优先遍历3.2.2 广度优先遍历的步骤3.2.3 广度优先遍历代码实现...

    一、图的概述

    1.1 什么是图

    图(graph)是一种数据结构,它是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E)。其中 G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中边的集合。

    在这里插入图片描述

    从图的定义中我们可以注意到它的一个特点:图中数据元素被称为顶点(Vertex。而在线性表中的数据元素叫元素,树形结构中的数据元素叫做节点。

    1.2 图对比线性表和树

    前面学习过线性表和树,现在又学到了图。为什么有这么多的数据结构呢?它们各自有什么不可替代的特点呢?

    在线性表中,数据元素之间是串起来的,仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继,可以理解为一对一。在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中的多个元素相关,但是只能和上一层中一个元素相关,可以理解为一对多

    图示一种较线性表和树更加复杂的数据结构。在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关,可以理解为多对多

    1.3 图的常见概念

    在图中有比较多的概念需要掌握,下面用一个表格来展示图形结构的常见概念。

    常见概念概念解释
    顶点数据元素
    两个顶点之间的连线
    路径从顶点 A 到顶点 B 要经过的边(路径可以有多条)
    邻接点相邻的顶点(如 A 和 B 通过一条边直接相连,则 B 是 A 的邻接点,A 是 B 的邻接点)
    无向图所有的边都没有方向
    有向图所有的边都有方向(如 A->B,表示只能从 A 到 B,无法从 B 到 A)
    带权图所有的边都带有权值
    连通图任意两个顶点都是连通的

    在这里插入图片描述

    二、图的存储方式

    图的存储方式有两种:二维数组表示(邻接矩阵)、链表表示(邻接表)。

    2.1 邻接矩阵

    图的邻接矩阵 (Adjacency Matrix) 存储方式是用两个数组来表示图,其中一个一维数组用来存储顶点信息,一个二维数组(称为邻接矩阵)存储图中的边的信息。

    邻接矩阵的行和列都是代表着图的第几个顶点。

    在这里插入图片描述

    如上所示图左是一个无向图,右边是该无向图的邻接矩阵:顶点 0 和顶点 1 之间存在一条边,因此 arr[0][1]arr[1][0] 都为 1(仅适用于无向图);顶点 0 和顶点 5 之间没有直接相连的边,因此 arr[0][5]arr[5][0] 都是 0。

    【案例演示】

    代码实现如下图结构,要求使用邻接矩阵。

    在这里插入图片描述

    public class No1_Graph {
        public static void main(String[] args) {
            String[] str = {"A", "B", "C", "D", "E"};
            // 创建一个图对象
            Graph graph = new Graph(str.length);
            // 添加顶点
            for (String vertex : str){
                graph.addVertex(vertex);
            }
            // 设置顶点之间的边
            graph.setEdges(0, 1, 1);    // A<->B
            graph.setEdges(1, 2, 1);    // B<->C
            graph.setEdges(1, 3, 1);    // B<->D
            graph.setEdges(1, 4, 1);    // B<->E;
            graph.setEdges(0, 2, 1);    // A<->C;
        }
    }
    
    /**
     * 图
     */
    class Graph{
        private ArrayList<String> vertexList;   // 存储顶点的集合
        private int[][] edges;  // 图对应的邻接矩阵
        private int numOfEdges; // 顶点之间边的个数
    	
        // 图的初始化
        public Graph(int n){
            this.vertexList = new ArrayList<>();
            this.edges = new int[n][n];
            this.numOfEdges = 0;
            this.isVisited = new boolean[n];
        }
        // 添加顶点到图中
        public void addVertex(String vertex){
            vertexList.add(vertex);
        }
        /**
         * 设置两个顶点之间的边
         * @param n 第一个顶点的索引
         * @param m 第二个顶点的索引
         * @param weight    边的权重
         * @return void
         */
        public void setEdges(int n, int m, int weight){
            edges[n][m] = weight;
            edges[m][n] = weight;
            numOfEdges++;
        }
        // 打印邻接矩阵
        public void printGraph(){
            for (int[] edge : edges){
                System.out.println(Arrays.toString(edge));
            }
        }
    }
    

    代码运行结果如下:

    在这里插入图片描述

    2.2 邻接表

    图的邻接表(Adjacency List)存储方式是用数组和链表来表示图,其中一个一维数组用来存储顶点,顶点数组中的每个数据元素还需要存储指向该顶点第一个邻接点的指针,每个顶点的所有邻接点构成一个线性表。

    邻接矩阵需要为每个顶点都分配 n 个边的空间,其实有很多边都是不存在,会造成空间的一定损失。邻接表的实现只关心存在的边,不关心不存在的边,因此没有空间浪费。

    如下图所示就是一个无向图的邻接表结构。

    在这里插入图片描述

    如图右所示,是无向图的邻接表:如标号为 0 的顶点的邻接点为 1、2、3、4;标号为 2 的订单的邻接点为 0、5。

    顶点数组中的数据元素由两部分组成,一部分是数据域存储顶点的信息,另一部分是指针域,指向该顶点的第一个邻接点。链表节点同样由两部分组成,一部分是邻接点域,用于存储与顶点相邻的点在图中的位置,另一部分是指针域,指向下一条边(如果边还有权值,还需要一个数据域用于存储权值,共三部分)。

    三、图的遍历

    从图中某一个顶点出发遍历图中其余顶点,且使每一个顶点仅被访问一次,这个过程就叫做图的遍历。一个图有多个顶点,如何遍历这些顶点,需要特定策略,一般有两种访问策略:深度优先遍历、广度优先遍历。

    3.1 图的深度优先遍历

    3.1.1 什么是深度优先遍历

    深度优先遍历(Depth First Search),也称深度优先搜索,简称为 DFS。

    深度优先遍历的思想说起来可能比较抽象,下面举个例子说一下。

    古时候有个功夫平平的剑客,一直想找到武林秘籍来提升自己的功夫。也算他命好,在行走江湖的路上他认识了一位神秘的老者,老者看他心系武林,就把守护了一生的秘密告诉他:在黄山、华山、泰山、峨眉山中的其中一座山里藏着失传已经的降龙十八掌,但是具体在哪座山需要他自己去找。

    一听说这个,剑客可就不困了。但是冷静下来之后,这个剑客有点懵逼了,这几座山这么大,离得还这么远,该怎么去寻找武林秘籍呢?

    经过一夜的辗转反侧,剑客最终确定了行动思路:先去黄山,不放过黄山的任何一个角落,把黄山的所有山洞、所有的小溪、所有的山路、所有的树木甚至是动物都找个遍,简单来说就是翻个底朝天,然后再去下一座山,再翻个底朝天,直到找到为止。

    这就是深度优先遍历的思想,简单来说就是优先向纵深挖掘,它类似于树的先序遍历的过程。

    3.1.2 深度优先遍历的步骤

    假设初始状态是图中所有顶点未曾被访问,则深度优先搜索可从图中某个顶点 v 出发,访问此顶点,然后依次从 v 的未被访问的邻接点出发深度优先遍历图,直至图中所有和 v 有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    以下面一个无向图为例,讲解其深度优先遍历过程。

    在这里插入图片描述

    假设从顶点 v1 出发,在访问完 v1 之后,选择邻接点 v2,因为 v2 未被访问,则从 v2 出发进行搜索。依次类推,接着从 v4、v7 出发进行搜索。在访问了 v7 之后,由于 v7 的邻接点都已经被访问,则搜索退回到 v4。由于同样的理由搜索继续回到 v2,直至 v1。此时由于 v1 的另一个邻接点未被访问,则搜索又从 v1 到 v3,再继续进行下去。由此,得到的顶点访问序列为:
    v 1 → v 2 → v 4 → v 7 → v 3 → v 5 → v 6 v1→v2→v4→v7→v3→v5→v6 v1v2v4v7v3v5v6
    显然,这是一个递归加回溯的过程。为了在遍历过程中便于区分顶点是否已被访问,需附设访问标志数组 isVisited[0.. n-1],其初始值为false,一旦某个顶点被访问,则其相应的分量置为 true

    3.1.3 深度优先遍历代码实现

    boolean[] isVisited = new boolean[vertexList.size];	// 标志数组
    
    /**
     * 从顶点 v 开始深度优先搜索 (DFS)
     * @param v 顶点
     */
    public void dfs(int v){
        isVisited[v] = true;    // 设置当前顶点状态为已访问
        System.out.print(vertexList.get(v) + "->");     // 打印当前顶点
        for (int i=0; i<vertexList.size(); i++){	// 遍历顶点	
            if (edges[v][i]==1 && !isVisited[i]){   // 如果某个顶点和当前顶点有直连的边且该顶点未被访问过
                dfs(i); // 递归深度优先遍历这个顶点
            }
        }
    }
    
    /**
     * 对图深度优先搜索
     */
    public void dfsTraverse(){
        /* 有可能是非连通图,出现顶点独立现象,因此有可能要以每个顶点为起点都来一次深度优先搜索 */
        for (int i=0; i<vertexList.size(); i++){
            if (!isVisited[i]){ // 如果顶点未被访问过,则从它开始 dfs。对于连通图,只会执行一次。
                dfs(i);
            }
        }
    }
    

    3.2 图的广度优先遍历

    3.2.1 什么是广度优先遍历

    广度优先遍历(Breadth First Search),又称为广度优先搜索,简称 BFS。

    还是以剑客找武林秘籍为例。剑客在赶往黄山的路上一想到要把整座山都翻个遍,瞬间头皮就麻了,他觉得武林秘籍总不至于会藏在山上的某个小石头下面吧,一定是藏在某个有灵气的地方。于是他改变了策略:先到每座山上大概瞅一眼,看看山的山势、灵气是不是像有武林秘籍的地方,如果都没有,再依次到各个山的山洞、小溪中找一找,如果没找到,再依次到各个山的小石头下翻一翻…,直到找到为止。

    这就是广度优先遍历的思想,它类似于树的按层次遍历的过程。

    3.2.2 广度优先遍历的步骤

    假设从图中顶点 v 出发,在 访问了 v 之后依次访问 v 的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使 “先被访问的顶点的邻接点” 先于 “后被访问的顶点的邻接点” 被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    还是以下面一个无向图为例,讲解广度优先遍历过程。

    在这里插入图片描述

    首先访问 v1 和 v1 的邻接点 v2 和 v3,然后依次访问 v2 的邻接点 v4 和 v7 以及 v3 的邻接点 v5 和 v6。由于这些顶点的邻接点均已被访问,并且图中所有的顶点都被访问,由此完成了图的遍历。最终得到的顶点访问序列为:
    v 1 → v 2 → v 3 → v 4 → v 7 → v 5 → v 6 v1→v2→v3→v4→v7→v5→v6 v1v2v3v4v7v5v6
    和深度优先遍历类似,广度优先遍历在遍历的过程中也需要一个访问标志数组。并且,为了顺次访问路径长度为 2、3 … 的顶点,需要附设队列以存储已被访问的路径长度为 1、2 … 的顶点。

    3.2.3 广度优先遍历代码实现

    /**
     * 从顶点 v 开始广度优先遍历 (BFS)
     * @param v 顶点
     */
    public void bfs(int v){
        LinkedList<Integer> queue = new LinkedList<>(); // 队列,用于存放已被访问的顶点
        isVisited[v] = true;    // 设置状态为已访问
        System.out.print(vertexList.get(v) + "->"); // 打印顶点
        queue.addLast(v);	// 添加当前顶点到队列中
    
        while (!queue.isEmpty()){   // 如果当前队列不为空
            v = queue.removeFirst();   // 队头元素出队列,接下来将以这个出队列的元素为起点访问邻接点
            for (int i=0; i<vertexList.size(); i++){
                if (edges[v][i] == 1 && !isVisited[i]){ // 判断其它顶点与当前顶点是否有边且是否访问过
                    isVisited[i] = true;    // 标记符合条件的顶点状态为已访问
                    System.out.print(vertexList.get(i) + "->"); // 打印顶点
                    queue.addLast(i);   // 将此顶点入队列
                }
            }
        }
    }
    
    /**
     * 广度优先遍历图
     */
    public void bfsTraverse(){
        /* 可能是非连通图,出现顶点独立现象,因此有可能每个顶点都要广度优先搜索 */
        for (int i=0; i<vertexList.size(); i++){
            if (!isVisited[i]){ // 如果顶点未被访问过,则对该顶点广度优先搜索,对于连通图只会执行一次
                bfs(i);
            }
        }
    }
    
    展开全文
  • C语言实现的深度优先遍历和广度优先遍历

    千次阅读 多人点赞 2019-11-28 20:29:17
    图的深度优先遍历和广度优先遍历图的遍历深度优先遍历广度优先遍历 图的遍历 从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中所有顶点,使每个顶点仅被访问一次,这个过程称为图的...
  • 广度优先遍历和深度优先遍历等js函数
  • 主要介绍了python实现树的深度优先遍历与广度优先遍历,详细分析了树的深度优先遍历与广度优先遍历原理及Python相关实现技巧,需要的朋友可以参考下
  • 深度优先遍历和广度优先遍历
  • 主要介绍了JavaScript树的深度优先遍历和广度优先遍历算法,结合实例形式分析了JavaScript树的深度优先遍历、广度优先遍历递归与非递归相关实现技巧,需要的朋友可以参考下
  • C语言非连通图广度优先遍历

    千次阅读 2017-01-20 17:25:40
    广度优先遍历算法的实现
  • 一步一步带你用Python实现的深度遍历和广度优先遍历;Python详解DFS和BFS过程
  • 主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
  • 广度优先遍历的一种遍历方式, 它的思想就是遍历这个点相邻的所有的点, 再对这些点进行广度优先遍历. 如下所示 图解 首先我们从A点开始遍历, 然后遍历所有和A相邻的点F和点G: 然后对F和点G进行遍历进行...
  • 无向图广度优先遍历 并判断这个图是否是树 首先要遍历图, 我们就要创建一个图 再进行广度优先遍历 再判断是不是树 一.创建一个图 1. 准备工作 在小学二年级学离散的时候我们都知道,图上结点之间的关系可以用邻接...
  • 广度优先遍历(breadth-first traverse,bfts),称作广度优先搜索(breadth first search)是连通的一种遍历策略。之所以称作广度优先遍历是因为他的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域。 ...
  • 数据结构系列是我学习做的笔记,会持续更新,源码分享...教科书上解释:广度优先搜索类似于类似于树的层次遍历,是数的层次遍历的推广 算法描述: 从中某个顶点v开始,先访问该顶点,再依此访问该顶点的每一个未被...
  • 深度优先遍历 广度优先遍历 图解算法过程
  • 的深度优先遍历和广度优先遍历

    千次阅读 2015-12-09 16:41:05
    的深度优先遍历和广度优先遍历 的深度优先遍历和广度优先遍历 的深度优先遍历和广度优先遍历 的深度优先遍历:V1 V2 V4 V8 V5 V3 V6 V7 广度优先遍历:V1 V2 V3 V4 V5 V6 V7 V8 #include #include ...
  • graphTraverse 的深度优先遍历(Stack)和广度优先遍历(Queue)算法
  • 广度优先遍历和最短路径算法

    万次阅读 多人点赞 2018-09-12 19:33:42
    广度优先遍历和最短路径算法 前言 广度优先遍历算法的探讨 核心代码分析 测试用例 完整代码获取 博客文章版权声明 广度优先遍历和最短路径算法 前言 上一次,我们讨论了有关的深度优先遍历算法...
  • 漫画:深度优先遍历 和 广度优先遍历.pdf
  • 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。 深度优先遍历二叉树。 1. 中序遍历(LDR)的递归算法: 若二叉树为空,则算法结束;否则:  中序遍历根结点的左子树...
  • 的深度优先遍历和广度优先遍历-Java实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 48,861
精华内容 19,544
关键字:

图的广度优先遍历