精华内容
下载资源
问答
  • 深度遍历
    2022-03-18 22:21:02

    题目:省份数量

    有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
    省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
    给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。
    返回矩阵中 省份 的数量。

    深度遍历

    var findCircleNum = function(isConnected) {
        //深度遍历
        let provinces=isConnected.length//城市长度
        let visited=[]//是否拜访过的空数组
        let circles=0//省份数量
        for(let i=0;i<provinces;i++){//遍历城市
            if(!visited[i]){//如果这个城市没有访问过
            dfs(isConnected,visited,provinces,i)//递归调用
            circles++//省份+1
            }
        }
        return circles
    };
        const dfs=(isConnected,visited,provinces,i)=>{
            for(let j=0;j<provinces;j++){
                if(isConnected[i][j]==1&&!visited[j]){//如果这个省份没有访问过,且有相连的
                    visited[j]=true;//将这个城市更改成拜访过的
                    dfs(isConnected,visited,provinces,j)//递归调用,跳到与这个城市相连的另一个继续遍历
                }
            }
        }
    

    广度遍历

    遍历完一行再一行

    var findCircleNum = function(isConnected) {
        //广度遍历
        let provinces=isConnected.length//城市长度
        let visited=[]//是否拜访过的空数组
        let circles=0//省份数量
        let queue=[]//队列
        for(let i=0;i<provinces;i++){//遍历城市
            if(!visited[i]){//如果这个城市没有访问过
            queue.push(i)
            while(queue.length){
                //拿出来去遍历
                let j=queue.shift()
                visited[j]=true
                for(let k=0;k<provinces;k++){
                    if(isConnected[j][k]==1&&!visited[k]){
                        queue.push(k)
                    }
                }
            }
            circles++
            }
        }
        return circles
    };
    
    更多相关内容
  • 邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历
  • 邻接矩阵 深度遍历.cpp
  • 图的深度遍历

    2015-06-25 21:01:36
    图的DFS实现,Description 请定一个无向图,顶点编号从0到n-1,用广度优先搜索(BFS),遍历并输出。遍历时,先遍历节点编号小的。
  • 邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历
  • 邻接矩阵的深度遍历深度遍历

    千次阅读 2020-10-15 20:02:24
    //深度遍历 void DFSRecursion(int v);//非递归遍历 void BFSTraverse(int v);//广度遍历 }; MGraph::MGraph(int v[],int n,int e){ vertexNum = n;//初始化顶点个数 arcNum = e;//初始化边的个数 for(int i=0;...
    #include<iostream>
    const int MAX_VERTEX = 10;
    using namespace std;
    int visitd[MAX_VERTEX] = {0};//设置标志变量,并且初始化 0 
    class MGraph{
    	private:
    		int vertex[MAX_VERTEX] ;//定义顶点表 
    		int arc[MAX_VERTEX][MAX_VERTEX];//定义邻接矩阵
    		int vertexNum,arcNum;//定义顶点个数,和边的个数
    	public:
    	MGraph(int vertex[],int n,int e) ;//n  各节点 e 条边 
    	~MGraph();
    	void printfMGraph();//打印邻接矩阵 
    	void DFSTraverse(int v);//深度遍历 
    	void DFSRecursion(int v);//非递归遍历 
    	void BFSTraverse(int v);//广度遍历 
    };
    MGraph::MGraph(int v[],int n,int e){
    	vertexNum = n;//初始化顶点个数 
    	arcNum = e;//初始化边的个数 
    	for(int i=0;i<vertexNum;i++){ //初始化图顶点 
    		vertex[i] = v[i];
    	}
    	for(int i=0;i<vertexNum;i++){//矩阵初始化 0 
    		for(int j=0;j<vertexNum;j++){
    			arc[i][j]=0;
    		}
    	}
    	int vi,vj;
    	for(int i=0;i<arcNum;i++){//输入对应的边关系  无向图是对称的 
    		
    		cin>>vi>>vj;
    		arc[vi][vj]=1;
    		arc[vj][vi]=1;
    	}
    	
    } 
    
    void MGraph::printfMGraph(){//打印图 
    	for(int i=0;i<vertexNum;i++){
    		for(int j=0;j<vertexNum;j++){
    			cout<<arc[i][j]<<"  ";
    		}
    		cout<<"\n";
    	}
    }
    void MGraph::DFSTraverse(int v){//深度优先遍历  递归方式 (使用系统栈方式)
    	int n = vertexNum;//获取顶点个数 
    	if(v<0||v>n) throw "位置出错";
    	cout<<vertex[v]<<" "; //打印顶点信息 
    	visitd[v]=1;// 0 表示为遍历 1 表示遍历过 ,设置为已经遍历过 
    	for(int i =0;i<n;i++){//查看某个顶点的相邻表,只需要看对应顶点的行即可 
    		if(visitd[i] == 0 && arc[v][i]!=0){//符合要求 表示找到未被遍历的点 
    			DFSTraverse(i);
    		}
    	}
    }
    
    void MGraph::DFSRecursion(int v){
    		int n = vertexNum;//获取顶点个数
    		if(v<0||v>n) throw "位置出错";
    		int stackGraph[n],top=-1,i;//设置栈 和 栈指针 
    		cout<<vertex[v]<<" ";
    		visitd[v]=1;
    		stackGraph[++top]=v;
    		while(top!=-1){
    				v = stackGraph[top];
    			for(i=0;i<n;i++){
    				if(visitd[i] == 0 && arc[v][i]!=0){
    					cout<<vertex[i]<<" ";
    					visitd[i]=1;
    					stackGraph[++top]=i;
    					break;
    				}
    			}
    			if(i==n){//没有可用的点了,出栈减一 
    				top--;
    			}
    		}	
    } 
    void MGraph::BFSTraverse(int v){//广度优先遍历,使用队列实现, 
    		int n = vertexNum;
    		if(v<0||v>n) throw "位置错误";
    		int queueGraph[MAX_VERTEX],front=-1,tail=-1;//定义队列,和头指针和尾指针		
    		cout<<vertex[v]<<" ";//输出首个顶点 
    		visitd[v]=1;//设置已读 
    		queueGraph[++tail] = v;//顶点入队 
    		while(front!=tail){//队列不为空,一直循环 
    			v = queueGraph[++front];//顶点出队 
    			for(int i=0;i<n;i++){//循环查找未被遍历的 
    				if(visitd[i]==0&&arc[v][i]!=0){
    					cout<<vertex[i]<<" ";//打印顶点 
    					visitd[i]=1;//设置已读 
    					queueGraph[++tail]=i;//顶点入队 
    				}
    			}
    		}
    
    }
    int main(){
    	int v[]={0,1,2,3,4,5,6};//顶点信息 
    	 MGraph* mg = new MGraph(v,7,9); // 通过顶点数组,点数,边数构造图 
    	 mg->printfMGraph();//打印邻接矩阵 
    	 mg->DFSTraverse(0);//深度遍历 
    	for(int i=0;i<MAX_VERTEX;i++){
    		visitd[i]=0;
    	}
    	cout<<"\n深度非递归遍历\n";
    	 mg->DFSRecursion(0);//深度非递归 
    	for(int i=0;i<MAX_VERTEX;i++){
    		visitd[i]=0;
    	} 
    	cout<<"\n广度遍历\n";
    	 mg->BFSTraverse(0);//广度遍历 
    	return 0;
    } 
    

    在这里插入图片描述

    展开全文
  • 深度遍历和广度遍历

    千次阅读 2021-08-02 20:01:37
    深度遍历和广度遍历1.图解2.区别3.代码 最近看深度遍历和广度遍历看到了一篇很好的文章,在此记录一下,原文地址点这。什么是深度遍历和广度遍历呢?简单来说,深度遍历和广度遍历都是针对树进行遍历的,不同的是...

    深度遍历和广度遍历


    最近看深度遍历和广度遍历看到了一篇很好的文章,在此记录一下, 原文地址点这。什么是深度遍历和广度遍历呢?简单来说,深度遍历和广度遍历都是针对树进行遍历的,不同的是深度优先从上到下进行遍历,而广度遍历则是逐层遍历的

    1.图解

    1. 深度优先
      深度优先

    2. 广度优先
      广度优先

    2.区别

    对于算法来说 无非就是时间换空间 空间换时间

    深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大

    1. 深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点
    2. 深度优先采用的是堆栈的形式, 即先进后出
    3. 广度优先则采用的是队列的形式, 即先进先出

    通常 深度优先不全部保留结点,扩展完的结点从数据库中弹出删去,这样,一般在数据库中存储的结点数就是深度值,因此它占用空间较少。
    所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。  
    广度优先搜索算法,一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。
    但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些

    3.代码

    const data = [
        {
            name: 'a',
            children: [
                { name: 'b', children: [{ name: 'e' }] },
                { name: 'c', children: [{ name: 'f' }] },
                { name: 'd', children: [{ name: 'g' }] },
            ],
        },
        {
            name: 'a2',
            children: [
                { name: 'b2', children: [{ name: 'e2' }] },
                { name: 'c2', children: [{ name: 'f2' }] },
                { name: 'd2', children: [{ name: 'g2' }] },
            ],
        }
    ]
    
    // 深度遍历, 使用递归
    function getName(data) {
        const result = [];
        data.forEach(item => {
            const map = data => {
                result.push(data.name);
                data.children && data.children.forEach(child => map(child));
            }
            map(item);
        })
        return result.join(',');
    }
    
    // 广度遍历, 创建一个执行队列, 当队列为空的时候则结束
    function getName2(data) {
        let result = [];
        let queue = data;
        while (queue.length > 0) {
            [...queue].forEach(child => {
                queue.shift();
                result.push(child.name);
                child.children && (queue.push(...child.children));
            });
        }
        return result.join(',');
    }
    
    console.log(getName(data))
    console.log(getName2(data))
    
    展开全文
  • 深度优先遍历(DFS):类似于二叉树的前序前序遍历 广度优先遍历(BFS):类似于二叉树的层次遍历 一、出度与入度 在讲图的遍历之前,我们需要先了解图的数据结构。 对于图,我们一般定义横向是出度,纵向是入度。比如...

    图是一种常见的数据格式,它的遍历主要分为两种:

    深度优先遍历(DFS):类似于二叉树的前序前序遍历

    广度优先遍历(BFS):类似于二叉树的层次遍历

    一、出度与入度

    在讲图的遍历之前,我们需要先了解图的数据结构。

    对于图,我们一般定义横向是出度,纵向是入度。比如对于左图我们转成领接矩阵如右图

    image-20220127202810611

    这里我们构建一个图的数据结构Graph,顺序遍历二维数组matrix的index[0]、index[1]、index[2]···获取出度。同理顺序遍历[0]index···获取入度。用java实现如下:

    public class Graph {
        private int vertexSize;//顶点数量
        private int[] vertexs;//顶点数组
        private int[][] matrix;//边或者弧的矩阵
        private static final int MAX_WEIGHT = 1000;//无穷大常量
        private boolean[] isVisited;
    
        public Graph(int vertexSize) {
            this.vertexSize = vertexSize;
            matrix = new int[vertexSize][vertexSize];
            // 初始化顶点数组为123···
            vertexs = new int[vertexSize];
            for (int i = 0; i < vertexSize; i++) {
                vertexs[i] = i;
            }
            isVisited = new boolean[vertexSize];
        }
    
        // 获取某个顶点的出度
        public int getOutDegree(int index) {
            int degree = 0;
            for (int j = 0; j < matrix[index].length; j++) {
                int weight = matrix[index][j];
                if (weight != 0 && weight != MAX_WEIGHT) {
                    degree++;
                }
            }
            return degree;
        }
    
        // 获取某个顶点的入度
        public int getInDegree(int index) {
            int degree = 0;
            for (int j = 0; j < matrix.length; j++) {
                int weight = matrix[j][index];
                if (weight != 0 && weight != MAX_WEIGHT) {
                    degree++;
                }
            }
            return degree;
        }
        public static void main(String[] args) {
            Graph graph = new Graph(9);
    
            int[] a1 = new int[]{0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT};
            int[] a2 = new int[]{10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12};
            int[] a3 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8};
            int[] a4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21};
            int[] a5 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT};
            int[] a6 = new int[]{11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT};
            int[] a7 = new int[]{MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT};
            int[] a8 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT};
            int[] a9 = new int[]{MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0};
    
            graph.matrix[0] = a1;
            graph.matrix[1] = a2;
            graph.matrix[2] = a3;
            graph.matrix[3] = a4;
            graph.matrix[4] = a5;
            graph.matrix[5] = a6;
            graph.matrix[6] = a7;
            graph.matrix[7] = a8;
            graph.matrix[8] = a9;
    
            System.out.println("v4的出度:" + graph.getOutDegree(4));
            System.out.println("v4的入度:" + graph.getInDegree(4));
        }
    }
    

    经验证输出

    v4的出度:3
    v4的入度:3

    二、深度优先遍历

    深度优先遍历(Deep_First_Search,简称为DFS):它从图中某个顶点ⅴ出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和 v 有路径相通的顶点都被访问到。

    image-20220127202810611

    如上图所示,按照上图所示,深度遍历顺序应该是ABCDEFGHI。

    遍历过程:A->B B->C C->D D->E E->F F->G G->H,然后回到B,B->I。类似于二叉树的前序前序遍历方式(DLR),中 -> 左 -> 右。

    已知原理,下面用java实现。首先对数组的每一层进行depthFirstSearch(index)遍历,其中isVisited用于记录该顶点是否遍历过

    /**
     * 对外公开的深度优先遍历
     */
    public void depthFirstSearch() {
        isVisited = new boolean[vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            if (!isVisited[i]) {
                System.out.println("访问到了:" + i + "顶点");
                depthFirstSearch(i);
            }
        }
        isVisited = new boolean[vertexSize];
    }
    

    对于depthFirstSearch(index)的具体实现:首先获取某个顶点的第一个邻接点(getFirstNeighbor),然后对于该顶点递归循环获取第一个临界点以达到深度的效果。如果遍历不到则获取相对于改顶点的下一个邻接点,同样用isVisited字段标记是否访问过。

    /**
     * 图的深度优先遍历算法
     */
    private void depthFirstSearch(int i) {
        isVisited[i] = true;
        int w = getFirstNeighbor(i);//
        while (w != -1) {
            if (!isVisited[w]) {
                //需要遍历该顶点
                System.out.println("访问到了:" + w + "顶点");
                depthFirstSearch(w);
            }
            w = getNextNeighbor(i, w);//第一个相对于w的邻接点
        }
    }
    

    对于这两个辅助函数的实现如下

    其中getFirstNeighbor肯定会从0查找它的出度(这里我们用不上入度),因为要确保不会遗漏。而对于getNextNeighbor我们则需要从index+1查找它的出度,因为深度优先的话,序列号在前面的顶点已被遍历过了不需要重复损耗性能。

    /**
     * 获取某个顶点的第一个邻接点
     */
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexSize; j++) {
            if (matrix[index][j] > 0 && matrix[index][j] < MAX_WEIGHT) {
                return j;
            }
        }
        return -1;
    }
    
    /**
     * 根据前一个邻接点的下标来取得下一个邻接点
     *
     * @param v 表示要找的顶点
     * @param index 表示该顶点相对于哪个邻接点去获取下一个邻接点
     */
    public int getNextNeighbor(int v, int index) {
        for (int j = index + 1; j < vertexSize; j++) {
            if (matrix[v][j] > 0 && matrix[v][j] < MAX_WEIGHT) {
                return j;
            }
        }
        return -1;
    }
    

    最后调用graph.depthFirstSearch();函数验证如下

    访问到了:0顶点
    访问到了:1顶点
    访问到了:2顶点
    访问到了:3顶点
    访问到了:4顶点
    访问到了:5顶点
    访问到了:6顶点
    访问到了:7顶点
    访问到了:8顶点

    三、广度优先遍历

    广度优先遍历(Broad_First_Search,简称为BFS):它从图中某个顶点ⅴ出发,访问此顶点,然后从v的未被访问的邻接点出发广度优先遍历图,直至图中所有和 v 有路径相通的顶点都被访问到。

    image-20220127202810611

    还是这个图,广度遍历顺序应该是0 1 5 2 6 8 4 3 7。

    遍历过程:第一层0 0->1 0->5 第二层1->2 1->6 1->8 5->4 第三层2->3 第四层3->7。类似于二叉树的层次遍历。

    已知原理,下面用java实现。首先对数组的每一层进行broadFirstSearch(index)遍历,其中isVisited用于记录该顶点是否遍历过

    public void broadFirstSearch() {
        isVisited = new boolean[vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            if (!isVisited[i]) {
                broadFirstSearch(i);
            }
        }
    }
    

    对于broadFirstSearch(index),我们需要用到队列,每次广度优先遍历都会入队列,然后遍历它所有的邻接点,完了之后退一个队列,继续广度遍历,当然遍历完成的标志就是队列清空。

    比如这里我们入队v0,然后再第一层while循环中退队v0,同时找到w为v1,然后在第二层while循环中继续遍历v0的所有邻接点得到v5入栈。然后返回到第一层while循环对v1进行广度遍历。

    /**
     * 实现广度优先遍历
     *
     * @param i
     */
    private void broadFirstSearch(int i) {
        int u, w;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        System.out.println("访问到:" + i + "顶点");
        isVisited[i] = true;
        queue.add(i);//第一次把v0加到队列
        while (!queue.isEmpty()) {
            u = (queue.removeFirst()).intValue();
            w = getFirstNeighbor(u);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.println("访问到了:" + w + "顶点");
                    isVisited[w] = true;
                    queue.add(w);
                }
                w = getNextNeighbor(u, w);
            }
        }
    }
    

    运行graph.broadFirstSearch();获取结果

    访问到:0顶点
    访问到了:1顶点
    访问到了:5顶点
    访问到了:2顶点
    访问到了:6顶点
    访问到了:8顶点
    访问到了:4顶点
    访问到了:3顶点
    访问到了:7顶点

    四、demo源码

    import java.util.LinkedList;
    
    public class Graph {
        private int vertexSize;//顶点数量
        private int[] vertexs;//顶点数组
        private int[][] matrix;//边或者弧的矩阵
        private static final int MAX_WEIGHT = 1000;//无穷大常量
        private boolean[] isVisited;
    
        public Graph(int vertexSize) {
            this.vertexSize = vertexSize;
            matrix = new int[vertexSize][vertexSize];
            // 初始化顶点数组为123···
            vertexs = new int[vertexSize];
            for (int i = 0; i < vertexSize; i++) {
                vertexs[i] = i;
            }
            isVisited = new boolean[vertexSize];
        }
    
        // 获取某个顶点的出度
        public int getOutDegree(int index) {
            int degree = 0;
            for (int j = 0; j < matrix[index].length; j++) {
                int weight = matrix[index][j];
                if (weight != 0 && weight != MAX_WEIGHT) {
                    degree++;
                }
            }
            return degree;
        }
    
        // 获取某个顶点的入度
        public int getInDegree(int index) {
            int degree = 0;
            for (int j = 0; j < matrix.length; j++) {
                int weight = matrix[j][index];
                if (weight != 0 && weight != MAX_WEIGHT) {
                    degree++;
                }
            }
            return degree;
        }
    
        // 获取两个顶点之间的权值
        public int getWeight(int v1, int v2) {
            int weight = matrix[v1][v2];
            return weight == 0 ? 0 : (weight == MAX_WEIGHT ? -1 : weight);
        }
    
        /**
         * 对外公开的深度优先遍历
         */
        public void depthFirstSearch() {
            isVisited = new boolean[vertexSize];
            for (int i = 0; i < vertexSize; i++) {
                if (!isVisited[i]) {
                    System.out.println("访问到了:" + i + "顶点");
                    depthFirstSearch(i);
                }
            }
            isVisited = new boolean[vertexSize];
        }
    
        /**
         * 图的深度优先遍历算法
         */
        private void depthFirstSearch(int i) {
            isVisited[i] = true;
            int w = getFirstNeighbor(i);//
            while (w != -1) {
                if (!isVisited[w]) {
                    //需要遍历该顶点
                    System.out.println("访问到了:" + w + "顶点");
                    depthFirstSearch(w);
                }
                w = getNextNeighbor(i, w);//第一个相对于w的邻接点
            }
        }
    
        /**
         * 获取某个顶点的第一个邻接点
         */
        public int getFirstNeighbor(int index) {
            for (int j = 0; j < vertexSize; j++) {
                if (matrix[index][j] > 0 && matrix[index][j] < MAX_WEIGHT) {
                    return j;
                }
            }
            return -1;
        }
    
        /**
         * 根据前一个邻接点的下标来取得下一个邻接点
         *
         * @param v 表示要找的顶点
         * @param index 表示该顶点相对于哪个邻接点去获取下一个邻接点
         */
        public int getNextNeighbor(int v, int index) {
            for (int j = index + 1; j < vertexSize; j++) {
                if (matrix[v][j] > 0 && matrix[v][j] < MAX_WEIGHT) {
                    return j;
                }
            }
            return -1;
        }
    
        public void broadFirstSearch() {
            isVisited = new boolean[vertexSize];
            for (int i = 0; i < vertexSize; i++) {
                if (!isVisited[i]) {
                    broadFirstSearch(i);
                }
            }
        }
    
        /**
         * 实现广度优先遍历
         *
         * @param i
         */
        private void broadFirstSearch(int i) {
            int u, w;
            LinkedList<Integer> queue = new LinkedList<Integer>();
            System.out.println("访问到:" + i + "顶点");
            isVisited[i] = true;
            queue.add(i);//第一次把v0加到队列
            while (!queue.isEmpty()) {
                u = (queue.removeFirst()).intValue();
                w = getFirstNeighbor(u);
                while (w != -1) {
                    if (!isVisited[w]) {
                        System.out.println("访问到了:" + w + "顶点");
                        isVisited[w] = true;
                        queue.add(w);
                    }
                    w = getNextNeighbor(u, w);
                }
            }
        }
    
        public static void main(String[] args) {
            Graph graph = new Graph(9);
    
            int[] a1 = new int[]{0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT};
            int[] a2 = new int[]{10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12};
            int[] a3 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8};
            int[] a4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21};
            int[] a5 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT};
            int[] a6 = new int[]{11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT};
            int[] a7 = new int[]{MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT};
            int[] a8 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT};
            int[] a9 = new int[]{MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0};
    
            graph.matrix[0] = a1;
            graph.matrix[1] = a2;
            graph.matrix[2] = a3;
            graph.matrix[3] = a4;
            graph.matrix[4] = a5;
            graph.matrix[5] = a6;
            graph.matrix[6] = a7;
            graph.matrix[7] = a8;
            graph.matrix[8] = a9;
    
            System.out.println("v4的出度:" + graph.getOutDegree(4));
            System.out.println("v4的入度:" + graph.getInDegree(4));
            System.out.println("<v2,v3>的权值:" + graph.getWeight(2, 3));
    //        graph.depthFirstSearch();
            graph.broadFirstSearch();
        }
    }
    
    展开全文
  • python深度遍历

    2022-04-16 10:27:42
    深度遍历: from os import listdir from os.path import join, isfile, isdir def listDirDepthFirst(directory): '''深度优先遍历文件夹''' #遍历文件夹,如果是文件就直接输出 #如果是文件夹,就输出...
  • 今天小编就为大家分享一篇Python实现深度遍历和广度遍历的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 深度遍历和广度遍历(图解)

    千次阅读 2022-05-06 09:08:18
    深度遍历和广度遍历(图解)
  • 深度遍历和广度遍历生成树,C++实现,可直接运行。
  • 深度遍历--广度遍历

    2021-09-15 10:08:47
    深度遍历(DFS) 遍历完父节点的所有子节点的子节点的子节点...再遍历其兄弟节点。 const DFS = { nodes: [], do (root) { for (let i = 0;i < root.length;i++) { var node = root[i]; // 过滤 text 节点...
  • 该二叉树的创建必须输入非空整数,作为建立一个完全二叉树的条件 注意:此二叉树是无序的,不属于二叉平衡搜索树!!! 本次构建二叉树采用链式存储...二叉树的遍历方式分为两种:深度优先遍历 和 广度优先遍历 ...
  • !!这是一个直接可用的方法!! 看看效果! 我们有这样一个多层嵌套的多维字典: # 老千层饼 data = { '千层饼': { '你以为我是第一层': { '其实我是第五层': '呵呵', ... '对': '对又怎么了',
  • 这就是这棵树的结构 然后我们来写两个方法对他们进行深度遍历与广度遍历 : public static void depthErgodic(Node01<T> root) {//深度遍历 if (root == null) return; System.out.print(root.getValue()+" "); for...
  • 深度遍历算法详细解释及例题应用

    千次阅读 2020-05-14 17:26:29
    深度遍历算法原理及图解 深度遍历算法例题应用 1:全排列问题 2:ABC+DEF=GHI问题 3:二维数组寻找点到点的最短路径 4:求岛屿的面积 5:求岛屿的个数 6:地板的埔法有多少种 7:二叉树的深度遍历 8:图的深度遍历 9...
  • 深度遍历:一个树形结构中,由一个数据分支全部遍历完才去遍历另外一个分支,直至全部数据遍历完成。 广度遍历:先遍历最外层的分支数据,然后一层一层的进行深入遍历,直至全部数据遍历完成。...
  • 数组结构如下: let treeData=[ { id:1, children:[{ id:2 },{ id:3, ...深度遍历 对单个元素由浅到深,一层层递进循环扒取数据 方法1: for循环 function flatten(arr){ let fl
  • 分别是一种广度遍历,和三种深度遍历方法:先序遍历,中序遍历,后序遍历。下面是代码实现:   1、先序遍历 遍历顺序:根==》左子树==》右子树,实现代码: def pre(self,node):#定义一个先序遍历的方法 if node is...
  • 二叉树的深度遍历

    2020-02-29 16:34:34
    对于一棵二叉树,深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。 二、二叉树的深度遍历的三种方法 这三种方法常被用于访问树的节点,它们之间的不同在于访问每个节点的...
  • 文章目录什么是二叉树属性节点TreeNode手动构建如下所示二叉树遍历广度遍历算法思想实现细节深度遍历先序遍历(根左右)算法思想实现细节中序遍历(左根右)算法思想实现细节后续遍历(左右根)算法思想实现细节 ...
  • Walkdict walkdict是深度遍历字典和列表的工具,没有递归深度限制walkdict可以使用深度遍历dict和列表,不受dict限制深度## install安装pip install walkdict用法 >> > from walkdict import walkdict>> > d = { ...
  • 最近在数据结构的学习中,学习到了图这一章节,在图中,有两个遍历的策略:一种是广度优先遍历,一种是深度优先遍历。 先上运行结果吧 图的结构 这里以D顶点为起始顶点 广度优先遍历 首先我们介绍...
  • 深度遍历算法,开发环境VC6.0,实现了对所有节点的深度遍历
  • js中树形结构数据的深度遍历和广度遍历深度遍历广度遍历 实例数据: let tree = [ { id: '1', children: [ { id: '1-1', children: [ { id: '1-1-1', }, { id: '1-1-2', },
  • 数据结构之树的3种深度遍历(DFS)

    千次阅读 2020-06-21 09:18:31
    树的三种深度遍历方式 树的深度遍历(DFS): 这与层次遍历相对应(BFS),这是一种使用固定规则,从根节点出发以遍历每条子树从而遍历完整棵树的方式。 这种思想,在图的遍历方式上也存在。 一、三大方式 对于...
  • 树的深度遍历

    2015-11-10 22:11:38
    某人要带一条狗、一只鸡、一箩米过河,但小船必须要由人来划,最多只能载一物过河,而,当人不在场时、狗要咬鸡、鸡要吃米。问此人应如何过河。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 240,629
精华内容 96,251
关键字:

深度遍历

友情链接: 6.rar