【算法笔记】图结构及图的 DFS 和 BFS 介绍

前言： 该篇文章将介绍如何应付面试中的图结构，并且还简单介绍了 BFS 和 DFS

1. 图的基本介绍

基本概念：

图由点的集合和边的集合构成
虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
边上可能带有权值

图的结构：

邻接表法
邻接矩阵法
还有其它众多的方式

如何搞定图的面试题： 图的算法都不难，但是写代码时会很复杂，coding 代价比较高，因此可以通过以下的方式来应付图的面试题

先用自己最熟练的方式，实现图结构的表达
在自己熟悉的结构上，实现所有常用图的算法作为模板
把面试题提供的图结构转化为自己熟悉的图结构，再调用模板或改写即可（做一个适配器）

2. 图的实现

实现代码：

点结构的实现 <pre>import java.util.ArrayList;

// 点结构的描述 public class Node {

<!-- --></span>
<span class="token comment">// 该点的值</span>
<span class="token keyword">public</span> <span class="token keyword">int</span> value<span class="token punctuation">;</span>
<span class="token comment">// 该点的入度数</span>
<span class="token keyword">public</span> <span class="token keyword">int</span> in<span class="token punctuation">;</span>
<span class="token comment">// 该点的出度数</span>
<span class="token keyword">public</span> <span class="token keyword">int</span> out<span class="token punctuation">;</span>
<span class="token comment">// 该点的相邻点（指该点指向的点）</span>
<span class="token keyword">public</span> ArrayList<span class="token generics function"><span class="token punctuation">&lt;</span>Node<span class="token punctuation">&gt;</span></span> nexts<span class="token punctuation">;</span>
<span class="token comment">// 该点的相邻边（指该点指向的边）</span>
<span class="token keyword">public</span> ArrayList<span class="token generics function"><span class="token punctuation">&lt;</span>Node<span class="token punctuation">&gt;</span></span> edges<span class="token punctuation">;</span>

<span class="token keyword">public</span> <span class="token function">Node</span><span class="token punctuation">(</span><span class="token keyword">int</span> value<span class="token punctuation">)</span> <span class="token punctuation">{ 
<!-- --></span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>value <span class="token operator">=</span> value<span class="token punctuation">;</span>
    in <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    out <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    nexts <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ArrayList</span><span class="token operator">&lt;</span><span class="token operator">&gt;</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    edges <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ArrayList</span><span class="token operator">&lt;</span><span class="token operator">&gt;</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

}

边结构的实现 <pre>// 边结构的描述 public class Edge {

<!-- --></span>
<span class="token comment">// 边的权重</span>
<span class="token keyword">public</span> <span class="token keyword">int</span> weight<span class="token punctuation">;</span>
<span class="token comment">// 入边节点</span>
<span class="token keyword">public</span> Node from<span class="token punctuation">;</span>
<span class="token comment">// 出边节点</span>
<span class="token keyword">public</span> Node to<span class="token punctuation">;</span>

<span class="token keyword">public</span> <span class="token function">Edge</span><span class="token punctuation">(</span><span class="token keyword">int</span> weight<span class="token punctuation">,</span> Node from<span class="token punctuation">,</span> Node to<span class="token punctuation">)</span> <span class="token punctuation">{ 
<!-- --></span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>weight <span class="token operator">=</span> weight<span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>from <span class="token operator">=</span> from<span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>to <span class="token operator">=</span> to<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

}

图结构的实现 <pre>import java.util.HashMap; import java.util.HashSet;

// 图的描述 public class Graph {

<!-- --></span>
<span class="token comment">// 点的集合，Integer 表示节点的值，先有值，再创建节点</span>
<span class="token keyword">public</span> HashMap<span class="token generics function"><span class="token punctuation">&lt;</span>Integer<span class="token punctuation">,</span> Node<span class="token punctuation">&gt;</span></span> nodes<span class="token punctuation">;</span>
<span class="token comment">// 边的集合</span>
<span class="token keyword">public</span> HashSet<span class="token generics function"><span class="token punctuation">&lt;</span>Edge<span class="token punctuation">&gt;</span></span> edges<span class="token punctuation">;</span>

<span class="token keyword">public</span> <span class="token function">Graph</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{ 
<!-- --></span>
    nodes <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">HashMap</span><span class="token operator">&lt;</span><span class="token operator">&gt;</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    edges <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">HashSet</span><span class="token operator">&lt;</span><span class="token operator">&gt;</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

} </pre>

常见面试题的图结构：

用一个二维数组表示，每个一维数组里面有三个值
第一个值表示边的权重
第二个值表示边的出发节点
第三个值表示边的目的节点

假设现有一个数组表示是这样的：{ {3, 0, 7}, {5, 1, 2}, {6, 2, 7}}，它符合上面图的结构，那么它用图表示如下

当我们面试遇见这种结构的图时，就可以使用我们上述已经定义好的图的结构来表示，因此我们只需要再做一个适配的过程

适配代码：

public class Create { 
    
    public static Graph createGraph(int[][] matrix) { 
        Graph graph=new Graph();
        for(int i=0;i<matrix.length;i++) { 
            // 边的权重
            int weight=matrix[i][0];
            // 出发节点的值
            int from=matrix[i][1];
            // 目的节点的值
            int to=matrix[i][2];
            // 如果该图中还没有包含该节点，则将节点入图
            if(!graph.nodes.containsKey(from)) { 
                graph.nodes.put(from, new Node(from));
            }
            if(!graph.nodes.containsKey(to)) { 
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode=graph.nodes.get(from);
            Node toNode=graph.nodes.get(to);
            Edge edge=new Edge(weight,fromNode,toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.nexts.add(toNode);
            fromNode.edges.add(edge);
            graph.edges.add(edge);
        }
        return graph;
    }
}

`3. BFS`

BFS 方式：

从图中弹出最高层的节点，用一个集合 Set 注册该节点，然后将该节点入队列。当我们从队列中将它弹出时，将它的相邻节点（指向的节点）进行入队列，但是首先需要判断相邻节点是否在集合中注册，如果注册了，就不做处理；如果未注册，就进行注册，并将该节点进行入队列。然后重复刚刚的操作，对每层进行遍历

方法模板：

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class BFS { 
    // BFS 需要有一个头节点
    public static void bfs(Node start) { 
        if (start == null) { 
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> set = new HashSet<>();
        queue.add(start);
        set.add(start);
        while (!queue.isEmpty()) { 
            Node node = queue.poll();
            System.out.println(node.value);
            for (Node cur : node.nexts) { 
                if (!set.contains(cur)) { 
                    set.add(cur);
                    queue.add(cur);
                }
            }
        }
    }
}

`4. DFS`

DFS 方式：

一条路走到底为止，但是不能形成环路，当到底为止后，就返回上一个节点，如果该节点没有其它路，就继续往上。当某个节点还有其它路，先判断新的节点是否已经打印果过，打印过就继续往上，直到找到新的节点且未打印过。当最终返回头节点，则深度遍历结束。其中使用集合 Set 来标记该节点是否走过或打印过，使用栈来存储当前遍历路线的节点

方法模板：

import java.util.HashSet;
import java.util.Stack;

public class DFS { 

    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.add(cur);
                    stack.add(next);
                    set.add(next);
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }
}

    
  本文为互联网自动采集或经作者授权后发布，本文观点不代表立场，若侵权下架请联系我们删帖处理！文章出自：https://t4dmw.blog.csdn.net/article/details/123243184

【算法笔记】图结构及图的 DFS 和 BFS 介绍

1. 图的基本介绍

2. 图的实现

`3. BFS`

`4. DFS`

相关推荐

Redis底层数据结构--跳跃表

发表评论

热门文章

标签TAG

# java

# 安全

# 网络安全

# WEB安全

# 渗透测试

# 开发语言

# 信息安全

# linux

# 安全漏洞

# python

# Spring

# c语言

# 网络

# 后端

最近回复