临界矩阵与邻接表实现图的广度深度遍历

布满荆棘的人生 2023-07-12 08:42 7阅读 0赞

> 只是把自己学的发一下,代码可以直接copy直接跑

# 广度优先遍历 #

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

具体算法表述如下：

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

# 深度优先遍历 #

深度优先遍历，从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

我们从这里可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。

具体算法表述如下：

1.  访问初始结点v，并标记结点v为已访问。
2.  查找结点v的第一个邻接结点w。
3.  若w存在，则继续执行4，否则算法结束。
4.  若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
5.  查找结点v的w邻接结点的下一个邻接结点，转到步骤3。

# 临界矩阵实现 #

我们知道，要表示结点，我们可以用一个一维数组来表示，然而对于结点和结点之间的关系，则无法简单地用一维数组来表示了，我们可以用二维数组来表示，也就是一个矩阵形式的表示方法。

我们假设A是这个二维数组，那么A中的一个元素aij不仅体现出了结点vi和结点vj的关系，而且aij的值正可以表示权值的大小。

//构造器
    public Graph(int n) {
    	//初始化矩阵和vertexList
    	edges = new int[n][n];
    	vertexList = new ArrayList<String>(n);
    	numOfEdges = 0;
    	
    }
    
    //得到第一个邻接结点的下标 w 
    /**
     * 
     * @param index 
     * @return 如果存在就返回对应的下标，否则返回-1
     */
    public int getFirstNeighbor(int index) {
    	for(int j = 0; j < vertexList.size(); j++) {
    		if(edges[index][j] > 0) {
    			return j;
    		}
    	}
    	return -1;
    }
    //根据前一个邻接结点的下标来获取下一个邻接结点
    public int getNextNeighbor(int v1, int v2) {
    	for(int j = v2 + 1; j < vertexList.size(); j++) {
    		if(edges[v1][j] > 0) {
    			return j;
    		}
    	}
    	return -1;
    }
    
    //深度优先遍历算法
    //i 第一次就是 0
    private void dfs(boolean[] isVisited, int i) {
    	//首先我们访问该结点,输出
    	System.out.print(getValueByIndex(i) + "->");
    	//将结点设置为已经访问
    	isVisited[i] = true;
    	//查找结点i的第一个邻接结点w
    	int w = getFirstNeighbor(i);
    	while(w != -1) {//说明有
    		if(!isVisited[w]) {
    			dfs(isVisited, w);
    		}
    		//如果w结点已经被访问过
    		w = getNextNeighbor(i, w);
    	}
    	
    }
    
    //对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs
    public void dfs() {
    	isVisited = new boolean[vertexList.size()];
    	//遍历所有的结点，进行dfs[回溯]
    	for(int i = 0; i < getNumOfVertex(); i++) {
    		if(!isVisited[i]) {
    			dfs(isVisited, i);
    		}
    	}
    }
    
    //对一个结点进行广度优先遍历的方法
    private void bfs(boolean[] isVisited, int i) {
    	int u ; // 表示队列的头结点对应下标
    	int w ; // 邻接结点w
    	//队列，记录结点访问的顺序
    	LinkedList queue = new LinkedList();
    	//访问结点，输出结点信息
    	System.out.print(getValueByIndex(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(getValueByIndex(w) + "=>");
    				//标记已经访问
    				isVisited[w] = true;
    				//入队
    				queue.addLast(w);
    			}
    			//以u为前驱点，找w后面的下一个邻结点
    			w = getNextNeighbor(u, w); //体现出我们的广度优先
    		}
    	}
    	
    } 
    
    //遍历所有的结点，都进行广度优先搜索
    public void bfs() {
    	isVisited = new boolean[vertexList.size()];
    	for(int i = 0; i < getNumOfVertex(); i++) {
    		if(!isVisited[i]) {
    			bfs(isVisited, i);
    		}
    	}
    }
    
    //图中常用的方法
    //返回结点的个数
    public int getNumOfVertex() {
    	return vertexList.size();
    }
    //显示图对应的矩阵
    public void showGraph() {
    	for(int[] link : edges) {
    		System.err.println(Arrays.toString(link));
    	}
    }
    //得到边的数目
    public int getNumOfEdges() {
    	return numOfEdges;
    }
    //返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
    public String getValueByIndex(int i) {
    	return vertexList.get(i);
    }
    //返回v1和v2的权值
    public int getWeight(int v1, int v2) {
    	return edges[v1][v2];
    }
    //插入结点
    public void insertVertex(String vertex) {
    	vertexList.add(vertex);
    }
    //添加边
    /**
     * 
     * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1
     * @param v2 第二个顶点对应的下标
     * @param weight 表示 
     */
    public void insertEdge(int v1, int v2, int weight) {
    	edges[v1][v2] = weight;
    	edges[v2][v1] = weight;
    	numOfEdges++;
    }

# 邻接表实现 #

/**
     * @Author: lyq
     * @Description: 邻接表 本来是 无向图 写成了单向图
     * 但是问题不大 只需要修改addEdges 就可以了 或者在添加边的时候自行添加一下
     * 注意我的边 不包含0这条边的
     * @Date:Create：in 2020/3/7 15:10
     */
    public class GraphByList {
    
        private Node[] graph;
    
        public GraphByList(int size) {
            this.graph = new Node[size];
            //将这个图的顶点填充 以1 2 3 来填
            for (int i = 0; i < size; i++) {
                this.graph[i] = new Node(i + 1);
            }
        }
    
        public static void main(String[] args) {
            GraphByList graph = new GraphByList(8);
            graph.addEdges(1, 2, 1);
            graph.addEdges(1, 3, 1);
            graph.addEdges(2, 5, 1);
            graph.addEdges(2, 1, 1);
            graph.addEdges(2, 4, 1);
            graph.addEdges(4, 8, 1);
            graph.addEdges(4, 2, 1);
            graph.addEdges(3, 6, 1);
            graph.addEdges(3, 7, 1);
            graph.addEdges(3, 1, 1);
            graph.addEdges(5, 8, 1);
            graph.addEdges(5, 2, 1);
            graph.addEdges(6, 7, 1);
            graph.addEdges(6, 3, 1);
            graph.addEdges(8, 4, 1);
            graph.addEdges(8, 5, 1);
            graph.addEdges(7, 6, 3);
            graph.addEdges(7, 3, 1);
            graph.printGraph();
    //        graph.dfs();
    //        graph.dfsRecursion();
    //        graph.bfs();
            graph.bfsByQueue(1);
        }
    
    
    
        /**
         * 深度优先,每访问到了一个node 就 得到first 然后转到node 往复,直到 graph里的结点
         * 被访问完 所以需要一个记录已经访问了的结点的集合 可以使用visited
         * 非递归
         */
        public void dfs() {
            //创建一个visit的数组 1表示已经访问
            int[] visited = new int[this.graph.length];
            //首先要得到 一个node的first
            for (int i = 0; i < this.graph.length; i++) {
                if (visited[i] != 1) {
                    //说明当前结点还未被访问
                    System.out.print(i + 1 + " ");
                    visited[i] = 1;
                    Edge first = this.graph[i].getFirst();
                    while (first != null && visited[first.getNode() - 1] != 1) {
                        //有边,而且这条边对的结点没有被访问过, 那么就访问
                        visited[first.getNode() - 1] = 1;
                        System.out.print(first.getNode() + " ");
                        //循环
                        first = this.graph[first.getNode() - 1].getFirst();
                    }
                }
            }
        }
    
        /**
         * 深度搜索 递归写法
         */
        public void dfsRecursion() {
            //创建一个visit的数组 1表示已经访问
            int[] visited = new int[this.graph.length];
            for (int i = 0; i < this.graph.length; i++) {
                if (visited[i] != 1) {
                    //说明没有被访问过,那么就访问 访问放到递归体里面去
                    dfsRecursion(i, visited);
                }
            }
        }
    
        /**
         * 递归子体
         *
         * @param i
         * @param visited
         */
        private void dfsRecursion(int i, int[] visited) {
            //先访问
            System.out.print(i + 1 + " ");
            visited[i] = 1;
            //然后得到这个结点的first
            Edge first = this.graph[i].getFirst();
            if (first == null) {
                //判断是否还有临界边
                return;
            }
            int next = first.getNode() - 1;
            if (visited[next] != 1) {
                //说明first 没有被访问过 那么就递归访问
                dfsRecursion(next, visited);
            } else {
                //说明没有邻接点了,就退出
                return;
            }
        }
    
        public void addEdges(int node, int edge, int weight) {
            node = node - 1;
            if (this.graph[node].getFirst() == null) {
                this.graph[node].setFirst(new Edge(edge, weight));
            } else {
                Edge p = this.graph[node].getFirst();
                //找到最后一条边 最后一条边的 p.next == null
                while (p.getNext() != null) {
                    p = p.getNext();
                }
                p.setNext(new Edge(edge, weight));
            }
        }
    
    
        //广度优先遍历 思考:先拿到一个node,然后就需要遍历这个node的每一个Edge , 
       // 然后每遍历一次就置相应 的结点已经访问就行
        //非递归
        //存在的问题 我这个写法 是访问过的结点就不访问了,正规的网上的写法,是将访问的结点放入一个队列里面,每次出队一个进行递归访问
        //其实我有一个想法,如果存在一个孤立的点呢? 我这个方法就可以解决存在孤立的点,我仍然能够访问到它
        //先不谈性能问题
        public void bfs() {
            //创建一个visit的数组 1表示已经访问
            int[] visited = new int[this.graph.length];
            for (int i = 0; i < this.graph.length; i++) {
                //判断这个结点是否已经访问
                if (visited[i] != 1) {
                    //未访问 就循环访问edges 不过先得访问这个点
                    System.out.print(i + 1 + " ");
                    Edge first = this.graph[i].getFirst();
                    //判空,这个结点且未被访问过
                    while (first != null) {
                        if (visited[first.getNode() - 1] != 1) {
                            //那就访问
                            System.out.print(first.getNode() + " ");
                            visited[first.getNode() - 1] = 1;
                        }
                        first = first.getNext();
                    }
                }
            }
        }
    
    
        //算法描述为:选择一个初始结点 将初始结点访问到的结点入队,初始结点访问完,就出队一个结点,访问,循环
        //要满足既能够在循环里添加,还要保证能够判断非空 队列是一个效果最好的数据结构,懒得自己写了,就用了java里内置的一个stack ,其他的队列没学过
        public void bfsByQueue(int init) {
            //创建一个visit的数组 1表示已经访问
            int[] visited = new int[this.graph.length];
            System.out.print(init + " ");
            visited[init-1]=1;
            //嘿嘿 用stack 来实现
            Stack<Integer> tmp = new Stack<>();
    
            tmp.push(init);
    
            while (!tmp.isEmpty()){
                //取出来
                Integer next = tmp.pop();
                Edge first = this.graph[next-1].getFirst();
                //访问到的第一个结点
                while (first!=null){
                    int i = first.getNode() - 1;
                    if (visited[i]!=1){
                        //没有被访问过
                        System.out.print(first.getNode()+" ");
                        visited[i]=1;
                        //同时把first 入队
                        tmp.push(i);
                    }
    
                    first = first.getNext();
                }
               // iterator=hashSet.iterator();
            }
    
    
        }
    
        public void printGraph() {
            for (int i = 0; i < this.graph.length; i++) {
                Edge p = this.graph[i].getFirst();
                while (p != null) {
                    System.out.print(i + 1 + "->" + p.getNode() + " ");
                    p = p.getNext();
                }
                System.out.println();
            }
        }
    }
    
    
    class Node {
        private int nodeNum;
        private Edge first;
    
        public Node(int nodeNum) {
            this.nodeNum = nodeNum;
        }
    
        public Node() {
        }
    
        public int getNodeNum() {
            return nodeNum;
        }
    
        public void setNodeNum(int nodeNum) {
            this.nodeNum = nodeNum;
        }
    
        public Edge getFirst() {
            return first;
        }
    
        public void setFirst(Edge first) {
            this.first = first;
        }
    }
    
    class Edge {
        private int weight;
        private int node;
        private Edge next;
    
        public Edge(int node, int weight) {
            this.weight = weight;
            this.node = node;
        }
    
        public int getWeight() {
            return weight;
        }
    
        public void setWeight(int weight) {
            this.weight = weight;
        }
    
        public int getNode() {
            return node;
        }
    
        public void setNode(int node) {
            this.node = node;
        }
    
        public Edge getNext() {
            return next;
        }
    
        public void setNext(Edge next) {
            this.next = next;
        }
    }