CodeBook
  • Introduction
  • Array
    • Maximum Product of Three Numbers
    • Set Mismatch
    • Find the Duplicate Number
    • Find All Duplicates in an Array
    • Find All Numbers Disappeared in an Array
    • Missing Number
    • Single Number
    • Find Difference
    • Find the Celebrity
    • Word Distance
    • Product of Array Except Self
  • Binary Search
    • First Bad Version
    • Search in a Big Sorted Array
    • Search Range
    • Find the Peak
    • Maximum Number in Mountain Sequence
    • Search in Rotated Sorted Array
    • Find Minimum in Rotated Sorted Array
    • Search a 2D Matrix
    • Search a 2D Matrix II
    • Smallest Rectangle Enclosing Black Pixels
    • [Binary Search] Merge Two Sorted Array
    • Single Element in a Sorted Array
  • Two Pointers
    • 1 Forward
      • Moving Zeros
      • Remove Elements
      • Remove Duplicated
      • Longest Continuous Increasing Subsequence
      • Replace all Occurrences of String AB with C
    • 2 Oppsite
      • Rotate Array
      • Container With Most Water
      • Trapping Rain Water
      • Triangle Count
    • 3 Sliding Windows
      • Permutation in String
      • Find All Anagrams in a String
      • Longest Substring with At Most K Distinct Characters
      • Max Consecutive Ones II
      • Minimum Size Subarray Sum
      • Longest Substring Without Repeating Characters
      • Minimum Window Substring
      • Subarrays with K Different Integers
    • 4 Partition
      • Color Sort
      • Color Sort II
      • Partition Array
    • # Sum
      • Two Sum
      • Two Sum - Unique Pairs
      • Two Sum - Less Or Equal
      • Two Sum - Greater Than Target
      • Two Sum - Closest
      • Two Sum - Difference
      • Two Sum - Data Structure Design
      • Three Sum
      • Three Sum With Multiplicity
      • Three Sum Smaller
      • Three Sum - Triangle Count
      • Four Sum
  • BFS
    • 1 Traverse
      • Number of Islands
      • Clone Gragh
      • Number of Distinct Islands
      • Pacific Atlantic Water Flow
      • Surrounded Regions
      • Walls and Gates
      • Max Area of Island
    • 2 Shortest
      • 01 Matrix
      • Knight Shortest Path
      • Shortest Distance from All Buildings
      • Best Meet Point
      • Shortest Bridge
      • Snakes and Ladders
      • Bus Route
  • DFS
    • 0 Basic
      • Subsets
      • Subsets II
      • Permutations
      • Permutations II
      • Prev/Next Permutation
      • Kth Permutation
      • Permutation Index
      • Combination Sum
      • Combination Sum II
      • Combination Sum III
      • Combination
      • Path Sum
    • 1 Enumeration
      • Cartesian Product
      • Letter Combinations of a Phone Number
      • Split String
      • Palindrome Partitioning
      • Expression Add Operators
      • Target Sum
      • Restore IP Addresses
      • Generate Parentheses
      • Generalized Abbreviation
      • Remove Invalid Parentheses
      • Letter Case Permutation
      • Factor Combinations
      • Find the Missing Number II
    • 2 Search
      • N-Queens
      • Sudoku
      • Employee Importance
      • Increasing Subsequences
      • Nested List Weight Sum
    • 3 Flood Fill
      • Flood Fill
      • Number of Enclaves
    • 4 Path
      • Longest Increasing Path in a Matrix
      • Unique Paths III
    • 5 Memo
      • Knight Dialer
      • Regular Expression Matching
      • Wildcard Matching
    • # Word Big Four
      • Word Break
      • Word Break II
      • Word Pattern
      • Word Pattern II
      • Word Search
      • Word Search II
      • Word Ladder
      • Word Ladder II
  • Tree
    • 0 Binary Search Tree
      • Validate Binary Search Tree
      • Recover Binary Search Tree
      • Minimum Absolute Difference in BST
      • Find Mode in Binary Search Tree
      • Verify Preorder Sequence in Binary Search Tree
      • Unique Binary Search Trees
      • Count of Smaller Numbers After Self
      • Trim a Binary Search Tree
      • Closest Binary Search Tree Value
      • Closest Binary Search Tree Value II
    • 1 Traversal
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
    • 2 Divide and Conquer
      • Balanced Binary Tree
      • Max/Min Depth of Binary Tree
      • Diameter of Tree
      • DiffSum
      • Find Leaves of Binary Tree
    • 3 SubTree
      • Same/Symmetric Tree
      • TreeIsomorphism
      • Subtree of Another Tree
      • Find Duplicate Subtrees
      • Most Frequent Subtree Sum
      • Minimum Subtree
      • Subtree with Maximum Average
      • Equal Tree Partition
      • Flip Binary Tree To Match Preorder Traversal
    • 4 Path
      • Path Sum
      • Path Sum II
      • Path Sum III
      • Path Sum IV
      • Path Sum with Digits Representation
      • Binary Tree Paths
      • Binary Tree Longest Consecutive Sequence
      • Binary Tree Longest Consecutive Sequence II
      • Binary Tree Maximum Path Sum
      • Sum Root to Leaf Numbers
      • Boundary of Binary Tree
      • Smallest String Starting From Leaf
    • 5 Level Order
      • Level Order Traversal
      • Maximum Width of Binary Tree
      • Binary Tree Right Side View
      • Binary Tree Vertical Order Traversal
    • 6 LCA
      • LCA
      • LCA II
      • LCA III
      • LCA IV
      • Smallest Deepest Subtree
      • LCA of a BST
      • Cousins in Binary Tree
    • 7 Build Tree
      • Build Maximum Binary Tree
      • Convert Sorted List to Binary Search Tree
      • Serialize Deserialize
      • Verify Preorder Serialization of a Binary Tree
      • Construct Binary Tree from Traversals
    • 8 Distance
      • Closest Leaf in a Binary Tree
      • All Nodes Distance K in Binary Tree
    • 9 Structure
      • Flatten Binary Tree to Linked List
      • Binary Tree Upside Down
      • BST to Doubly LinkedList
      • Populating Next Right Pointers in Each Node
      • Populating Next Right Pointers in Each Node II
      • Invert Binary Tree
    • # N-ary Tree
  • String
    • 1 Pattern
      • Is Subsequence
      • One Edit Distance
      • Backspace String Compare
    • 2 Implementation
      • Reverse
      • Find the Closest Palindrome
      • Reverse Words in a String
      • Text Justification
    • 3 Substring
      • Implement Str
      • Longest Substring with At Least K Repeating Characters
      • Longest Common Prefix
    • 4 Number
      • Maximum Swap
      • Add Strings
      • Nth Digit
      • Compare Version Numbers
      • String to Integer (atoi)
      • Integer to English Words
      • Integer to Roman
      • Roman to Integer
      • Multiply Strings
      • Reverse Integer
    • 5 Decode
      • Decode String
      • Encode and Decode Strings
    • 6 Palindrome
      • Valid Palindrome
      • Valid Palindrome II
      • Palindrome Number
      • Palindrome Linked List
      • Palindromic Substrings
      • Palindrome Permutation
      • Palindrome Partitioning
      • Find Longest Palindromic Substring
      • Longest Palindromic Subsequence
      • Longest Palindromic Substrings
    • 7 Evaluation
      • Solve the Equation
      • Simplify Path
      • Valid Number
    • 8 Binary String
      • Count Binary Substrings
    • 9 Parenthesis
      • Valid Parenthesis String
      • Valid Parentheses
  • Data Structures
    • 0 Design
      • LRU
      • LFU
    • 1 LinkedList
      • Merge Sort
      • Find Cycle
      • Palindrome Linked List
      • Remove Duplicates
      • Flatten a Multilevel Doubly Linked List
      • Copy List with Random Pointer
    • 2 Stack
      • Min Stack
      • Max Stack
      • Implement Queue by Stacks
      • Implement Stack by Queues
    • 3 Queue/Deque
      • Moving Average
      • Design Circular Queue
      • Design Circular Deque
    • 4 Heap
      • Median for Data Stram
      • Kth Largest Data Stream
      • Top K Words
      • Top K Elements
      • Kth Smallest Number in Sorted Matrix
    • 5 Interval
      • Merge Intervals
      • Insert Interval
      • Non-overlapping Intervals
      • Maximum Length of Pair Chain
      • Meeting Room
      • Merge Two Sorted Interval List
      • Merge K Sorted Interval List
      • Intersection of Two Sorted Intervals
      • Meeting Room II
    • 6 Matrix
      • Multiply Sparse Matrix
      • Matrix Diagonal Traverse
      • Valid Sudoku
      • Spiral Matrix
    • 7 Iterator
      • Flatten 2D Vector
      • Pair Iterator
      • Peeking Iterator
      • Zigzag Iterator
    • 8 Hash
      • Design HashSet
      • Design HashMap
      • Hash Function
      • ReHash
      • Consistent Hash
      • Bloom Filter
      • Robin-Karp Algorithm
  • Advanced Data Structures
    • 1 Trie
      • Implement Trie
      • Stream of Characters
    • 2 Union Find
      • Number of Islands II
      • [Union Find]Graph Connect Tree
      • Minimum Spanning Tree
      • Bricks Falling When Hit
      • Most Stones Removed with Same Row or Column
      • Satisfiability of Equality Equations
    • 3 Monotonous Stack
      • Increasing Triplet Subsequence
      • Largest Rectangle in Histogram
      • Maximal Rectangle
      • Remove K Digits
      • Remove Duplicate Letters
      • Next Greater Element I
      • Next Greater Element II
    • 4 TreeSet/TreeMap
      • My Calendar I
      • My Calendar II
    • 5 Random
      • Shuffle an Array
      • Random Pick with Weight
      • Random Pick Index
    • 6 Binary Index Tree
    • 7 Segment Tree
      • Range Sum Query - Mutable
  • Graph
    • 1 General
      • Graph Deep Copy
    • 2 Topological Sorting
      • Course Schedule
      • Sequence Reconstruction
      • Alien Dictionary
    • 3 Bipartition
      • Is Graph Bipartition
      • Possible Bipartition
    • Detect Cycle in an Undirected Graph
    • Shortest Path in Undirected Graph
    • All Paths From Source to Target
    • Graph Valid Tree
    • Number of Connected Components in an Undirected Graph
    • Minimum Height Trees
  • Dynamic Programming
    • 0 Basic DP
      • Triangle
      • House Robber
      • House Robber II
      • Paint Fence
      • Paint House
    • 1 Sequence DP
      • Decode Ways
    • 2 Match Sequence DP
      • Edit Distance
      • K Edit Distance
      • Longest Common Subsequence
      • Minimum Swaps To Make Sequences Increasing
      • Scramble String
    • 3 Interval DP
      • Burst Ballons
      • Stone Game
    • 4 Matrix DP
      • Number Of Corner Rectangles
      • Max Square
      • Longest Increasing Path in a Matrix
    • 5 Backpack
      • K-Sum
      • Backpack1-01
      • Backpack2-01
      • Backpack4-Complete
      • Backpack3-Complete
      • Backpack7-Multiply
    • 6 Game DP
      • Predict the Winner
      • Can I Win
      • Coins In Line I
      • Coins In Line II
      • Coins In Line III
  • Common Methods
    • 1 Presum
      • Subarray Sum Equals K
      • Continuous Subarray Sum
      • Path Sum II
      • Min/Max Subarry
      • Contiguous 01-Array
      • Flip 01String to Monotone Increasing
      • Maximum Sum of Two Non-Overlapping Subarrays
    • 2 Bucket
      • Maximum Gap
    • 3 Simulation
      • Pour Water
    • 4 Buffer
      • Read N Characters Given Read4 II - Call multiple times
      • Read N Characters Given Read4
      • Third Maximum Number
    • 5 Merge/Union
      • Merge k Sorted Lists
      • Merge k Sorted Arrays
      • Merge k Sorted Intervals
      • Intersection of Three Sorted Array
      • Intersection of Two Arrays
      • Intersection of Two Arrays II
    • 6 Geometry
      • Max Points on a Line
    • 7 Math
      • GCD
      • Matrix Coordinate
      • Sqrt(x)
      • Divide Two Integers
      • pow(x, n)
    • 8 Sorting
      • Merge Sort
      • Quick Sort
      • Quick Select
  • Design/OOD
    • Design Rate Limiter
    • Design Hit Counter
    • Design Twitter
    • Design MapWithExpiration
    • Design Tiny URL
  • Appendix
    • Java Built-in
      • Comparator
      • Stream
      • String Pool
    • Multithreading
      • Synchronized
      • Producer-Consumer
      • CountDownLatch
      • Semaphore
      • Thread Pool
      • DeadLock
      • Inter-thread Communication
Powered by GitBook
On this page
  • Define
  • 自定义邻接表
  • 使用 Map 和 Set(面试时)
  • 简化版
  • OJ's undirected graph serialization:
  • Some statement for tree in graph theory
  • BFS/DFS

Graph

Define

有很多种方法可以存储一个图,最常用的莫过于:

  1. 邻接矩阵

  2. 邻接表

而邻接矩阵因为耗费空间过大,我们通常在工程中都是使用邻接表作为图的存储结构。

邻接矩阵 Adjacent Matrix

[
  [1,0,0,1],
  [0,1,1,0],
  [0,1,1,0],
  [1,0,0,1]
]

例如上图表示0号点和3号点有连边。1号点和2号店有连边。 当然,每个点和自己也是默认有连边的。 图中的0表示不连通,1表示连通。 我们也可以用一个更具体的整数值来表示连边的长度。 邻接矩阵我们可以直接用一个二维数组表示,如int[][] matrix;。这种数据结构因为耗费 O(n^2) 的空间,所以在稀疏图上浪费很大,因此并不常用。

邻接表 (Adjacent List)

[
  [1],
  [0,2,3],
  [1],
  [1]
]

这个图表示 0 和 1 之间有连边,1 和 2 之间有连边,1 和 3 之间有连边。即每个点上存储自己有哪些邻居(有哪些连通的点)。 这种方式下,空间耗费和边数成正比,可以记做 O(m),m代表边数。m最坏情况下虽然也是 O(n^2),但是邻接表的存储方式大部分情况下会比邻接矩阵更省空间。

自定义邻接表

可以用自定义的类来实现邻接表

class DirectedGraphNode {
     int label;
     ArrayList<DirectedGraphNode> neighbors;
     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
}

class UndirectedGraphNode {
     int label;
     List<UndirectedGraphNode> neighbors;
     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
};

其中 neighbors 表示和该点连通的点有哪些。

使用 Map 和 Set(面试时)

也可以使用 HashMap 和 HashSet 搭配的方式来存储邻接表

Map<T, Set<T>> = new HashMap<Integer, HashSet<Integer>>();

其中 T 代表节点类型。通常可能是整数(Integer)。 这种方式虽然没有上面的方式更加直观和容易理解,但是在面试中比较节约代码量。 而自定义的方法,更加工程化,所以在面试中如果时间不紧张题目不难的情况下,推荐使用自定义邻接表的方式。

简化版

有的时候节点会简化成0-1000的数字,这时图的表示就比较简化了

Input: [[1,3], [0,2], [1,3], [0,2]]
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2

这种就是邻接表的一个例子,注意节点从1开始还是从0开始,有些情况会告诉最大节点数,方便初始化邻接表

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use#as a separator for each node, and,as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph{0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by#.

  1. First node is labeled as0. Connect node0to both nodes1and2

  2. Second node is labeled as1. Connect node1to node2.

  3. Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Some statement for tree in graph theory

(1) A tree is an undirected graph in which any two vertices are connected by exactly one path.

(2) Any connected graph who hasnnodes withn-1edges is a tree.

(3) The degree of a vertex of a graph is the number of edges incident to the vertex.

(4) A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2.

(5) A path graph is a tree with two or more vertices that is not branched at all.

(6) A tree is called a rooted tree if one vertex has been designated the root.

(7) The height of a rooted tree is the number of edges on the longest downward path between root and a leaf.

BFS/DFS

Graph 是非常重要而又涵盖很广的内容,以至于有单独的 “图论” 研究方向。LeetCode 上很多问题都可以抽象成 “图” ,比如搜索类问题,树类问题,迷宫问题,矩阵路径问题,等等。

重点在于 DFS 和 BFS 的比较;可以看到;

  • BFS 的时间空间占用以 branching factor 为底, 到解的距离 d 为指数增长;空间占用上 Queue 是不会像 DFS 一样只存一条路径的,而是从起点出发越扩越大,因此会有空间不够的风险,空间占用为 O(b^d)。

  • DFS 的时间占用以 branching factor 为底,树的深度 m 为指数增长;而空间占用上,却只是 O(bm),可视化探索过程中只把每个 Node 的所有子节点存在 Stack 上, 探索完了再 pop 出来接着探,因此储存的节点数为 O(bm)。

可以看到无论是 BFS 还是 DFS,树的 branching factor 都是对空间与时间复杂度影响最大的参数;除此之外,BFS 中最重要的是到解的距离,而 DFS 看从当前节点的深度。普遍来讲,DFS 空间上会经济一些,当然也要分情况讨论。

Topological sort,拓扑排序,是 graph 搜索中一种特殊的顺序,本质上还是完全可以靠 BFS / DFS 解决。

有向图 DFS 图示:

有向图 BFS 图示:

可以看到两种搜索都用了三种颜色表示状态。

  • 有向图 Directed:

    • DFS:

        • 暴力解法:DFS + Backtracking,寻找“所有从当前节点的” path,如果试图访问 visited 则有环;缺点是,同一个点会被探索多次,而且要从所有点作为起点保证算法正确性,时间复杂度非常高

        • 最优解法是 CLRS 上用三种状态表示每个节点:

          • "0" 还未访问过;

          • "1" 代表正在访问;

          • "2" 代表已经访问过;

        • DFS 开始时把当前节点设为 "1";

        • 在从任意节点出发的时候,如果我们试图访问一个状态为 "1" 的节点,都说明图上有环。

        • 当前节点的 DFS 结束时,设为 "2";

        • 在找环上,DFS 比起 BFS 最大的优点是"对路径有记忆",DFS 记得来时的路径和导致环的位置,BFS 却不行。

        • 类似剥洋葱,可以选择任意点开始向里 DFS ,记录path,后面做的其他 DFS path 都放在之前结果的前面。(CLRS有)

        • 等价做法是,把每次 DFS 探索中的 path 按照由内向外的顺序添加(单序列反序), 后进行的 DFS 结果放在之前运行完的结果后面(全序列反序),然后 reverse 就好了,可以改良 ArrayList 添加的时间复杂度。

        • 更简单的做法是用 Java 内置的 LinkedList,支持双端操作。

      • Count # of connected components

      • Determine if A is reachable from B

    • BFS:

        • 首先,在 DAG 上找环,DFS 要比 BFS 强。

        • 其次重点注意,有向图靠 3 个状态 BFS 是不能正确判断是否有环的,要靠 indegree,一个例子是 【0, 1】 和 【1,0】,环在发现之前已经被标注为 state 2 了。

        • 扫一遍所有 edge,记录每个节点的 indegree.

        • 在有向无环图中,一定会存在至少一个 indegree 为 0 的起点,将所有这样的点加入queue。

        • 依次处理queue里的节点,把每次poll出来的节点的 children indegree -1. 减完之后如果 child 的 indegree = 0 了,就也放入队列。

        • 如果图真的没有环,可以顺利访问完所有节点,如果还有剩的,说明图中有环,因为环上节点的 indegree 没法归 0.

        • 步骤同上,扫的时候按顺序 append 就好了。

        • 类似于“剥洋葱”,从最外面一层出发,逐步向里。

      • Count # of connected components

      • Determine if A is reachable from B

        • 这个任务最适合用 BFS 做,从 B 做起点一路扫看看能不能扫到 A 就行了。

  • Un-directed:

    无向图算法的整体思路和有向图基本一致,但是需要重点注意 正确处理 “原路返回” 的情况,免得死循环或者误报。

    在无向图的2个状态基础上增加一个 “正在访问” 的新状态,加上注意 prev 就可以了。

    • DFS:

        • 用 int[] 表示每个点的状态,其中

          • 0 代表“未访问”;

          • 1 代表“访问中”;

          • 2 代表“已访问”;

        • DFS call 里要传入 "prev节点" 参数,避免出现原路返回,或者回到前一个节点误判为有环。(和 directed graph DFS 唯一的不同之处)

        • 其他情况下,如果我们试图访问一个状态为 “1” 的节点,都可以说明图中有环。

      • Topological Sort

        • 都无向图了,topological 。。。。

      • Determine if A is reachable from B

    • BFS:

        • 扫描所有 edges 记录图到底长啥样;

        • 用 "0,1,2" states;

        • 随便扔一个点进 queue,标记 "1",然后 BFS,所有 child = "0" 的都加入队列

        • 所有 child 都检查完之后,立刻把当前 node = 2,不然下一层 BFS 会回头去看自己然后误报。

        • 如果遇到 child = "1" 的说明有环

      • Topological Sort

        • 都无向图了,topological 。。。。

        • 和 Detect Cycle 一样,同时记录下到底做了几次 BFS 才扫遍全图,图上就有几个 connected components

      • Determine if A is reachable from B

        • BFS 搜到底看看能不能到就可以了,这个和只靠 g(x) 的 uniform-cost search 一致。

PreviousRange Sum Query - MutableNext1 General

Last updated 6 years ago

Detect Cycle ()

Detect Cycle ()

Detect Cycle ()

Count # of connected components ()

Detect Cycle ()

Count # of connected components ()

Course Schedule
Topological Sort
Course Schedule
Topological Sort
Graph Valid Tree
Graph Valid Tree
Graph Valid Tree
Graph Valid Tree