精华内容
下载资源
问答
  • 图的深度优先遍历
    千次阅读
    2022-03-20 11:58:42

            深度优先遍历,也有称为深度优先搜索,简称为DFS。

            深度优先遍历其实就是一个递归的过程,它从图中某个顶点ⅴ出发,访问此顶点,然后从V的未被访问的邻接点出发深度优先遍历图,直至图中所有和V有路径相通的顶点都被访问到。

    邻接矩阵方式的深度优先遍历

    #include<iostream>
    #include<vector>
    using namespace std;
    
    #define MAXVEX 100//最大顶点数
    typedef char VertexType;//顶点类型
    typedef int EdgeType;//边上的权值类型
    typedef struct
    {
    	VertexType vexs[MAXVEX];//顶点表
    	EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵
    	int numVertexte;//当前顶点数
    	int numEdges;//当前边数
    }MGraph;
    
    void DFS(MGraph G, int i, vector<bool>& visited)
    {
    	visited[i] = true;
    	cout << G.vexs[i] << " ";//打印当前节点
    	for (int j = 0; j < G.numVertexte; ++j)
    	{
    		if (G.arc[i][j] == 1 && !visited[j])//如果节点i和节点j之间可达,并且节点j未被访问过
    		{
    			DFS(G, j, visited);//则从几点j开始继续深度遍历
    		}
    	}
    }
    void DFSTraverse(MGraph G)
    {
    	vector<bool> visited(G.numVertexte,false);//初始所有的顶点状态都是未访问过的
    	for (int i = 0; i < G.numVertexte; ++i)
    	{
    		if (!visited[i])//如果当前节点没被访问过,则从当前节点开始深度遍历
    		{
    			DFS(G, i, visited);
    		}
    	}
    }

    时间复杂度:O(n^{2})

     

    邻接表方式的深度优先遍历

    #include<iostream>
    #include<vector>
    using namespace std;
    
    #define MAXVEX 100//最大顶点数
    typedef char VertexType;//顶点类型
    typedef int EdgeType;//边上的权值类型
    
    typedef struct EdgeNode
    {
    	int adjvex;//邻接点域,存储该顶点对应的下标
    	EdgeType weight;//用于存储权值,对于非网图可以不需要
    	struct EdgeNode* next;//指向下一个邻接点
    }EdgeNode;
    
    typedef struct VertexNode //顶点表结点
    {
    	VertexType data;//存储顶点信息
    	EdgeNode* firstedge;//指向该顶点的第一个相邻结点
    }VertexNode,AdjList[MAXVEX];
    
    typedef struct
    {
    	AdjList adjList;
    	int numVertexes;//当前顶点数
    	int numEdges;//当前边数
    }GraphAdjList;
    
    void DFS(GraphAdjList G, int i, vector<bool>& visited)
    {
    	EdgeNode* p;
    	visited[i] = true;
    	cout << G.adjList[i].data << " ";
    	p = G.adjList[i].firstedge;
    	while (p)
    	{
    		if (!visited[p->adjvex])//如果当前顶点未被访问过,则从当前节点开始深度优先遍历
    		{
    			DFS(G, p->adjvex, visited);
    		}
    		p = p->next;//当前节点的后一个节点
    	}
    }
    
    void DFSTraverse(GraphAdjList G)
    {
    	vector<bool> visited(G.numVertexes, false);//初始所有顶点状态都是未访问过状态
    	for (int i = 0; i < G.numVertexes; ++i)
    	{
    		if (!visited[i])//如果当前顶点未被访问过,则从当前节点开始深度优先遍历
    		{
    			DFS(G, i, visited);
    		}
    	}
    }

    时间复杂度:O(n+e)

     

    如果对图的邻接矩阵或者邻接表不清楚,则可以参考下面这篇博客:

    一、图的定义,邻接矩阵和邻接表的实现_瘦弱的皮卡丘的博客-CSDN博客

    更多相关内容
  • 本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
  • 深度优先遍历DFS 与树的先序遍历比较类似。 假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的...
  • 主要介绍了JavaScript树的深度优先遍历和广度优先遍历算法,结合实例形式分析了JavaScript树的深度优先遍历、广度优先遍历递归与非递归相关实现技巧,需要的朋友可以参考下
  • 主要介绍了python实现树的深度优先遍历与广度优先遍历,详细分析了树的深度优先遍历与广度优先遍历原理及Python相关实现技巧,需要的朋友可以参考下
  • 主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
  • 本程序方便的实现了深度、广度优先遍历,txt文档代码复制即可使用。
  • C++实现,数据结构,的邻接矩阵表示,深度优先遍历,广度优先遍历,DFS,BFS,为什么要五十个字才能上传啊
  • 使用邻接表表示法创建无向,然后使用非递归算法进行深度优先遍历和广度优先遍历
  • 深度优先遍历和广度优先遍历

    万次阅读 多人点赞 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());
    
    }
    

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

    展开全文
  • 天津理工大学实验报告 学院系名称 计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009 级 1 班 实验项目 实验四 深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 实验时间 2011 年 5 月...
  • 若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至中所有和源点v有路径相通的顶点均已被访问为止。若此时中仍有未访问的顶点,则另选一个尚未访问的顶点为新的源点重复上述过程,直至中所有的顶点...

    一. 什么是深度优先遍历

    深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点为新的源点重复上述过程,直至图中所有的顶点均已被访问为止。

    深度优先遍历结果是: A B E F C D G H 

        深度优先遍历尽可能优先往深层次进行搜索

    二.广度优先遍历

    广度优先遍历可定义如下:首先访问出发点v,接着依次访问v的所有邻接点w1、w2......wt,然后依次访问w1、w2......wt邻接的所有未曾访问过的顶点。以此类推,直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。

     

     

    广度优先遍历结果是: A B C D E F G H I

    广度优先遍历按层次优先搜索最近的结点,一层一层往外搜索。

    三. 创建的步骤 

        深度优先遍历创建步骤(Depth First Search)

     1.访问初始节点 v,并标记为已访问

     2.查找结点v的第一个邻接点 w

     3.若w存在   则执行4   若不存在回到第一步 再找 v结点的下一个结点

     4.判断w是否被访问   未访问对w深度优先遍历(即把w当作另一个v ,再进行1 2 3);

     5.查找v 在w 后面是否还有下一个邻接点   再执行步骤3 

      广度优先遍历步骤

    (需要用到队列来实现对 顺序的访问他的所有邻接点)

     1.访问初始节点 v,并标记为已访问

     2.结点v 入队列

     3.当队列非空时 继续执行,否则结束

     4. 出队列 ,取得头结点u

     5. 查找结点u 的第一个邻接点w

    6. 若结点u 邻接点不存在 则执行 步骤3 否则循环执行以下三个步骤

          6.1. 若结点w 未被访问 则访问节点w 并标记为已访问

          6.2 结点w 入队

          6.3 查找结点u的 除了w 之后的下一个其他邻接点

    四. 代码实现

    //深度优先遍历
    		public void dfs(boolean [] isVisied,int i) {
    			
    			//传入是否被访问的数组  ,和第几个邻接点 
    			System.out.printf(getVertexInf(i)+"-->");
    			isVisied[i]=true;
    			//查找i节点的第一个邻接点
    			int f = getFirstNeighbor(i);
    			while(f!=-1) {
    				//表示第一个邻接点存在
    				//判断是否被访问
    				if(!isVisied[f]) {
    				  dfs(isVisied, f);
    				 } 
    				//这个i 的下一个邻接点已经被访问了,再找这个节点的下一个结点
    				f= getNextNeighbor(i,f);
    			}
    			
    			
    		}
    	//对每个节点遍历
        //当一个节点访问完后 还有其他未访问的,利用循环 遍历所有的结点
    		public void DFS() {
    			isVisited= new boolean[getNumOfV()];
    			for(int i=0;i<vertexList.size();i++){
    				
    				if(!isVisited[i]) {
    					dfs(isVisited,i);
    				}
    			}
    		}

     

    //广度优先遍历   对第i个结点遍历  利用队列来实现
    		public void bfs(boolean [] isVisied,int i) {
    			int u;  //表示队列的第一个元素
    			int w ;  //表示这个节点的邻接点
    			LinkedList queue = new LinkedList(); //创建出队列
    			
    			 //调用这个方法就意味着 满足条件可以输出
    			System.out.printf(getVertexInf(i)+"==>");
    			//把这个结点置为i访问
    			isVisied[i]=true;
    			//将节点加入 到队列中
    			queue.addLast(i);  //在队尾添加元素
    			
    			//循环判断队列是否还有元素
    			while(!queue.isEmpty()) {
    				//给第一个元素出队列
    				u = (int) queue.removeFirst();
    				//找这个元素的邻接点
    				w = getFirstNeighbor(u);
    				while(w!=-1) {
    					//找到邻接点
    					if(!isVisied[w]) {
    						//判断是否已访问
    						System.out.printf(getVertexInf(w)+"==>");
    						//把这个结点置为i访问
    						isVisied[w]=true;
    						//将节点加入 到队列中
    						queue.addLast(w);  //在队尾添加元素
    					}
    					//继续寻找下一个  广度的
    					w = getNextNeighbor(u, w);
    				}
    			}
    			
    		}
    		//对每个节点遍历
    				public void BFS() {
    					isVisited= new boolean[getNumOfV()];
    					for(int i=0;i<vertexList.size();i++){
    						
    						if(!isVisited[i]) {
    							bfs(isVisited,i);
    						}
    					}
    				}
    		

    五. 结果展示

     

    展开全文
  • 的引出:前面我们学了线性表和树。线性表局限于一个直接前驱和一个直接后继的关系;树也只能有一个直接前驱也就是父结点。但我们需要表示多对多的关系时,我们就...深度优先遍历思想:深度优先遍历是一种纵向切入..

    图的引出:前面我们学了线性表和树。线性表局限于一个直接前驱和一个直接后继的关系;树也只能有一个直接前驱也就是父结点。但我们需要表示多对多的关系时,我们就需要用到图这种数据结构。

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

    邻接矩阵中,如果两个顶点相连通,则为1,如果不连通,则为零。

    图的遍历

    有两种策略。1、深度优先遍历(Depth First Search)。2、广度优先遍历(Broad First Search)

    深度优先遍历思想:深度优先遍历是一种纵向切入的思想。思想是先访问当前顶点,然后再以这个顶点作为初始顶点,访问该顶点的第一个邻接顶点。可以这样理解:每次访问完当前顶点后首先访问当前顶点的第一个邻接顶点。这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。由此可以看出,需要通过递归来实现深度优先遍历

    广度优先遍历思想:广度优先遍历类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的节点的顺序,以便按这个顺序来访问这些结点的邻接结点。

    接下来我举一个例子,讲述深度优先遍历的思想

    接下来还是以同样一个例子讲述广度优先的遍历思想:

     两者的区别:深度优先就是一直到底遍历;而广度优先就好似一张网,一步一步迈进遍历。

    这是两者最主要的区别

    深度优先遍历的步骤

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

    广度优先遍历的步骤

    1. 访问初始结点v并标记结点v为已访问。
    2. 结点v入队列
    3. 当队列非空时,继续执行,否则算法结束。
    4. 出队列,取得队列头结点u。
    5. 查找结点u的第一个邻接结点w。
    6. 若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:

            6.1若结点w尚未被访问,则访问结点w并标记为已访问。

            6.2结点w入队列。

            6.3查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。

    具体实现代码附上,大家可以通过代码仔细去感悟。

    package com.liu.chart;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    
    
    /**
     * @author liuweixin
     * @create 2021-09-20 8:50
     */
    //图
    public class VertexChart {
        ArrayList<String> VertexList;
        int[][] edges;//用来储存顶点之间的关系
        int numOfEdges;//表示边的个数
    
        public static void main(String[] args) {
    //        String[] data = new String[]{"A", "B", "C", "D", "E"};
            String[] data = new String[]{"1", "2", "3", "4", "5", "6", "7", "8"};
            VertexChart vertexChart = new VertexChart(data.length);
            for (String value : data) {
                vertexChart.addVertex(value);
            }
    //        vertexChart.addEdge(0,1,1);
    //        vertexChart.addEdge(0,2,1);
    //        vertexChart.addEdge(1,2,1);
    //        vertexChart.addEdge(1,3,1);
    //        vertexChart.addEdge(1,4,1);
            vertexChart.addEdge(0, 1, 1);
            vertexChart.addEdge(0, 2, 1);
            vertexChart.addEdge(1, 3, 1);
            vertexChart.addEdge(1, 4, 1);
            vertexChart.addEdge(2, 5, 1);
            vertexChart.addEdge(2, 6, 1);
            vertexChart.addEdge(3, 7, 1);
            vertexChart.addEdge(4, 7, 1);
            vertexChart.addEdge(5, 6, 1);
            vertexChart.show();
            System.out.println();
            vertexChart.dfs();//深度优先遍历:1-2-4-8-5-3-6-7
            System.out.println();
            vertexChart.bfs();//广度优先遍历:1-2-3-4-5-6-7-8
        }
    
        public VertexChart(int VertexCount) {
            edges = new int[VertexCount][VertexCount];
            VertexList = new ArrayList<String>(VertexCount);
            numOfEdges = 0;
        }
    
        /**
         * 对广度优先方法的封装
         */
        public void bfs(){
            boolean[] isVisited = new boolean[VertexList.size()];
            //添加该循环的原因在于,有可能数据是分布在两张图甚至多张图上的,所以我们需要对所有的数据实现广度优先遍历
            //如果数据都分布在单一的一张图上,则不需要加此循环
            for (int i = 0; i < VertexList.size(); i++) {//对所有数据进行广度优先遍历
                if(!isVisited[i]){//判断是否访问过
                    bfs(isVisited,i);//进行广度优先遍历
                }
            }
        }
        /**
         *广度优先
         * @param isVisited 是否被访问
         * @param i  初始结点
         */
        public void bfs(boolean[] isVisited, int i){
            int u;//表示队列的头结点对应的下标
            int w;//邻接结点w
            //队列,记录结点访问的顺序
            LinkedList queue = new LinkedList();
            //访问结点,输出结点信息
            System.out.print(VertexList.get(i)+ " ");
            //标记为已访问
            isVisited[i]=true;
            //将结点加入队列
            queue.addLast(i);
            while (!queue.isEmpty()){
                //取出队列的头结点下标
                u=(Integer)queue.removeFirst();
                //得到第一个邻接结点的下标w
                w=getFirstNeighbor(u);
                while (w!=-1){//找到
                    //是否访问过
                    if(!isVisited[w]){
                        System.out.print(VertexList.get(w)+" ");
                        //标记已经访问
                        isVisited[w]=true;
                        //入队
                        queue.addLast(w);
                    }
                    //以u为前驱点,找w后面的下一个邻接点
                    w=getNextNeighbor(u,w);//体现出广度优先.
                }
            }
        }
    
        //对深度优先遍历方法进行封装
        public void dfs() {
            boolean[] isVisited = new boolean[VertexList.size()];
            //添加该循环的原因在于,有可能数据是分布在两张图甚至多张图上的,所以我们需要对所有的数据实现深度优先遍历
            //如果数据都分布在单一的一张图上,则不需要加此循环
            for (int i = 0; i < VertexList.size(); i++) {//对所有数据进行深度优先遍历
                if(!isVisited[i]){//判断是否访问过
                    dfs(isVisited, 0);//进行深度优先
                }
            }
    
        }
    
        /**
         * 深度优先遍历
         *
         * @param isVisited 是否被访问
         * @param i         初始结点
         */
        public void dfs(boolean[] isVisited, int i) {
            System.out.print(VertexList.get(i) + " ");
            isVisited[i] = true;//设置该点已被访问过
            //获取该结点的第一个邻接结点的下标
            int index = getFirstNeighbor(i);
            while (index != -1) {//如果循环能进来,此时表明有下一个邻接结点
                if (!isVisited[index]) {//如果该结点未被访问过
                    //进行递归遍历+回溯
                    dfs(isVisited, index);
                }
                //如果该结点已被访问过
                index = getNextNeighbor(i, index);
            }
        }
    
        /**
         * 根据前一个结点的邻接结点的下标获取下一个邻接结点
         *
         * @param v1
         * @param v2
         * @return
         */
        public int getNextNeighbor(int v1, int v2) {
            for (int i = v2 + 1; i < VertexList.size(); i++) {
                if (edges[v1][i] > 0) {
                    return i;
                }
            }
            return -1;
        }
    
        /**
         * 得到该下标的第一个邻接结点
         *
         * @param index
         * @return 如果找到,则返回该下标值,如果找不到,返回-1
         */
        public int getFirstNeighbor(int index) {
            for (int i = 0; i < VertexList.size(); i++) {
                if (edges[index][i] == 1) {
                    return i;
                }
            }
            return -1;
        }
    
        /**
         * 显示图的邻接矩阵
         */
        public void show() {
            for (int[] arr : edges) {
                for (int data : arr) {
                    System.out.print(data + " ");
                }
                System.out.println();
            }
        }
    
        /**
         * 获取顶点的个数
         *
         * @return 返回顶点的个数
         */
        public int getVexCount() {
            return VertexList.size();
        }
    
        /**
         * 获取边的个数
         *
         * @return 返回边的个数
         */
        public int getNumOfEdges() {
            return numOfEdges;
        }
    
        /**
         * 返回对应的两个顶点之间的关系
         *
         * @param v1 第一个顶点的下标
         * @param v2 第二个顶点的下标
         * @return 如果返回1,则表示其可以连通;如果返回0,则表示其不连通
         */
        public int getWeight(int v1, int v2) {
            return edges[v1][v2];
        }
    
        /**
         * 获取对应下标的顶点值
         *
         * @param index 对应下标
         * @return 返回该顶点值
         */
        public String getVertex(int index) {
            return VertexList.get(index);
        }
    
        /**
         * 把顶点的数据存储到List中
         *
         * @param data
         */
        public void addVertex(String data) {
            VertexList.add(data);
        }
    
        /**
         * 将顶点之间的关系进行表示
         *
         * @param v1     表示点的下标,即第几个顶点
         * @param v2     第二个顶点对应的下边
         * @param weight 两者的关系。如果为1,则表示两者连通;如果为0,则表示两者不连通。
         */
        public void addEdge(int v1, int v2, int weight) {
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    }
    

    展开全文
  • 深度优先遍历

    2022-06-25 14:38:49
    深度优先遍历是按照深度优先搜索方式对图进行遍历的。深度优先遍历的秘籍:后被访问的节点,其邻接点先被访问。根据深度优先遍历秘籍,后来者先服务,这可以借助栈实现。递归本身就是使用栈实现的,因此使用递归的...
  • PTA 7-1 图深度优先遍历 (C语言实现)
  • 文章目录一、邻接矩阵存储深度优先遍历过程分析二、结果分析三、C语言编程实现深度优先遍历四、的遍历及其应用 一、邻接矩阵存储深度优先遍历过程分析 对图1这样的无向,要写成邻接矩阵,则就是...
  • 一个有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历 深度优先遍历基本思想 的深度优先搜索(Depth First Search) 。 深度优先遍历,从初始访问结点...
  • 建立的邻接矩阵或邻接表存储并在此基础上实现深度优先遍历和广度优先遍历.doc
  • 深度优先遍历和广度优先遍历-Java实现
  • 一、遍历图可能遇到的问题 图的特点: 图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又...三、深度优先遍历(DFS) 1、遍历的方法 ■在访问图中某一起始顶点V后.
  • c++实现的邻接表深度优先遍历,广度优先遍历
  • 深度优先遍历与广度优先遍历

    千次阅读 2021-04-21 17:04:31
    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。 我们来到一个游乐场,游乐场里有11个景点。我们从景点0开始,要玩遍游乐场的...
  • 本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
  • 图深度优先遍历

    千次阅读 2020-12-03 16:15:46
    编写程序对给定的有向(不一定连通)进行深度优先遍历中包含n个顶点,编号为0至n-1。本题限定在深度优先遍历过程中,如果同时出现多个待访问的顶点,则优先选择编号最小的一个进行访问,以顶点0为遍历起点。 ...
  • 深度优先遍历算法之二叉树一、什么是深度优先遍历二、二叉树1. 二叉树简介2.二叉树类型3.二叉树相关术语4. 二叉树的节点代码5. 二叉树遍历顺序6.深度优先遍历和广度优先遍历三、面试题+励志 这不就是二叉树吗?嗯,...
  • C++实现深度优先遍历和广度优先遍历

    千次阅读 多人点赞 2020-09-24 08:25:04
    深度优先遍历 深度优先遍历参考 深度优先遍历 参考 1、https://blog.csdn.net/todd911/article/details/9191481 2、https://blog.csdn.net/weixin_42109012/article/details/94199335

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,277
精华内容 40,110
关键字:

图的深度优先遍历

友情链接: STC89C51.rar