图的遍历（广度优先遍历、深度优先遍历）

小灰灰 2022-02-05 08:45 359阅读 0赞

# 图的数据结构 #

[https://blog.csdn.net/weixin\_43093501/article/details/89840219][https_blog.csdn.net_weixin_43093501_article_details_89840219]

# 广度优先遍历 #

### 思路 ###

准备：队列、set：查重  
1.将图的起始节点添加到队列中，同时加到set中  
2.只要队列中有元素，就执行代码  
3.弹出队列中的元素，并打印，  
4.将该元素的邻居节点集合全部加入到队列中（重复的不加）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]

### 代码 ###

public static void bfs(Node node) { 
    		if (node == null) { 
    			return;
    		}
    		Queue<Node> queue = new LinkedList<>();
    		HashSet<Node> map = new HashSet<>();
    		queue.add(node);
    		map.add(node);
    		while (!queue.isEmpty()) { 
    			Node cur = queue.poll();
    			System.out.println(cur.value);
    			for (Node next : cur.nexts) { 
    				if (!map.contains(next)) { 
    					map.add(next);
    					queue.add(next);
    				}
    			}
    		}
    	}

# 深度优先遍历 #

### 思路 ###

准备：栈，set（查重）  
1.将图的起始节点添加到栈中，同时加到set中  
2.只要队列中有元素，就执行代码  
3.弹出栈顶元素  
4.遍历元素的邻居集合  
5.如果邻居节点不重复（不在set中），则：

*  将刚弹出的栈顶元素加入栈中，
 *  邻居节点加入栈中，
 *  邻居节点加入set中，
 *  打印邻居节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70 1]

### 代码 ###

public static void dfs(Node node) { 
    		if (node == null) { 
    			return;
    		}
    		Stack<Node> stack = new Stack<>();
    		HashSet<Node> set = new HashSet<>();
    		stack.add(node);
    		set.add(node);
    		System.out.println(node.value);
    		while (!stack.isEmpty()) { 
    			Node cur = stack.pop();
    			for (Node next : cur.nexts) { 
    				if (!set.contains(next)) { 
    					stack.push(cur);
    					stack.push(next);
    					set.add(next);
    					System.out.println(next.value);
    					break;
    				}
    			}
    		}
    	}

[https_blog.csdn.net_weixin_43093501_article_details_89840219]: https://blog.csdn.net/weixin_43093501/article/details/89840219
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]: /images/20220205/25dd200400c74573a27ebcce6834b5d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70 1]: /images/20220205/261e381a4fc140c393d5b8a8270525db.png