Mabuxi
  • Hello World
  • 12/2017 - 01/2018 Google 电面汇总
  • LeetCode Summary
    • Data Structure
      • Stack
      • Queue
      • 单调栈/单调队列
      • Heap (PriorityQueue)
      • Trie
      • Union Find
      • HashTable
      • Custom DS Design
    • Array
      • Two Pointer
      • Find Duplicate 系列
      • Single Number 系列
      • Sequence 系列
    • String
      • Substring Search
      • String Rotation
    • Sort
      • Topological Sort
      • 数据太大怎么办 External Sort
    • Binary Search
    • Index
    • Interval
    • LinkedList
      • Fast and Slow pointer
      • Intersection
      • Entrance of the Cycle
    • Math
      • Problems
    • Greedy
    • Divide & Conquer
    • Sliding Window
    • Dynamic Programming
      • Bottom Up
      • Top Down
      • Knapsack Problems
    • Bit Manipulation
      • Bit Vector
    • Recursion
    • Tree
      • Binary Search Tree
      • Traversal
      • Top Down
      • Bottom Up
      • Binary Indexed Tree
    • Graph
      • BFS
      • DFS
      • DFS + Backtracking
    • Advanced Algorithm
      • Boyer Moore Voting Algorithm
      • Virtual Indexing
      • Reservoir Sampling
    • Game Play
    • 综合题
      • Design Hit Counter
    • Brainstorm 脑筋急转弯
  • CS Foundamental 计算机基础
    • Database
    • Java
    • Java Spring
    • Network
    • Linux
    • Cache
    • Distributed System
      • 分布式配置中心
    • Big Data
  • OOD 面向对象设计
  • System Design 系统设计
  • Regular Expression 正则表达式
  • Resume Deep Dive 简历技术栈
    • MongoDB
    • Docker
    • Nginx
  • TODO List
Powered by GitBook
On this page
  • Graph 的表示方法
  • Graph的遍历方法 （DFS and BFS）
  • DAG (Directed Acyclic Graph)
  • Reference
  1. LeetCode Summary

Graph

PreviousBinary Indexed TreeNextBFS

Last updated 6 years ago

Graph 的表示方法

一般求解Graph题的时候，input给你一些点或者一些边，需要你自己用数据结构来存储（方便之后的调用）。那么，一般有2种：

邻接表 (Adjacent List)

邻接矩阵 (Adjacent matrix)

space cost

O(|V| + |E|)

O(|V|^2)

scenario

sparse graph

dense graph

implementation

List<List<Integer>>, outer list with the size of |V|

int[N][M]

Graph的遍历方法 （DFS and BFS）

  • 一般需要遍历所有情况的时候，比如连通性问题，用DFS

  • 一般找最短路径的时候，用BFS

DAG (Directed Acyclic Graph)

  • Directed Acyclic Graph 有向无环图，不需要考虑infinite loop，即不需要boolean array记录状态。

  • Directed Cyclic Graph 有向有环图，需要考虑 infinite loop。

Reference

http://people.cs.vt.edu/shaffer/Book/JAVA3e20130328.pdf