Notes
  • Introduce
  • Go
    • Grammar
      • Basic
      • Goroutines & Channels
      • Test
    • System Library
      • Module
      • sync
      • context
      • net
    • Concurrency in Go
    • The Go Memory Model
    • Code Snippet
  • Rust
    • The Rust Programming Language
    • Rust by Example
  • JAVA
    • Preface
    • Grammar
      • Basic
      • Data Types
      • Operator
      • Exceptions
    • Class Libraries
      • Collection
      • Stream
      • IO
      • NIO
      • RMI
    • Concurrency
      • Preface
      • JMM
      • Synchronized & CAS
      • Deadlock
      • Thread
      • Lock & Condition
      • Utility Class
      • Thread-safe Collection
      • Atomic Class
      • Fork/Join
      • Concurrency Design Patterns
        • Immutable
        • Copy-on-Write
        • ThreadLocal
        • Multitheading If
        • Division
    • JVM
      • Class & Instance Initialization
      • Runtime Data Area
      • Garbage Collection
    • Web Container
      • Tomcat Architecture
      • Jetty Architecture
    • Spring
    • Tuning
      • Programming
  • Computer Science
    • Computer Organization
    • Algorithm
      • Complexity
      • Linear List
      • Sort
      • Binary Search
      • Skip List
      • Hash Table
      • Tree
      • Graph
      • String Matching
      • Bloom Filter
      • Greedy Algorithm
      • Divide and Conquer
      • Back Tracking
      • Dynamic Programming
    • Network Protocol
      • Pysical Layer
      • Data Link Layer
      • Network Layer
      • Transport Layer
      • Application layer
      • HTTP
      • HTTP/2 in Action
    • Operating System
      • Basic
      • System Initialization
      • Diagnostic Tools
      • CPU Diagnosis
      • Memory Diagnosis
      • Disk Diagnosis
      • Network Diagnosis
      • Monitor System
    • Design Patterns
      • UML
      • OOP
      • Principle
      • Refactoring & Specification
      • Creational
        • Singleton
        • Factory
        • Builder
        • Prototype
      • Structural
        • Proxy
        • Bridge
        • Decorator
        • Adapter
        • Facade
        • Composite
        • FlyWeight
      • Behavioral
        • Observer
        • Template Method
        • Strategy
        • State
        • Iterator
        • Chain of Responsibility
    • Distributed System
      • Protocol & Algorithm
      • Transcation
      • Theory
      • Resource Management
      • Scheduling
      • Computing
      • Message Queue
      • Cache
      • Consistent Hashing
  • database
    • InfluxDB
      • In-Memory Index
      • Meta
    • MySQL
      • SQL
      • Architecture
      • Log
      • Transaction
      • Indexing
      • Lock
      • Storage
    • Redis
    • Elasticsearch
      • Local Debug
    • HBase
    • Kafka
    • ZooKeeper
  • Reading
    • RocketMQ
    • 演说之禅
    • So Good They Can't Ignore You
    • 学会提问
    • Lecture
  • Other
    • v2ray
    • Kubernetes
    • Git
    • Maven
    • Anaconda And Conda
    • Fuck! Shit!
      • Remove Final by Reflection
      • Ingress Host
      • ExecuterService submit
  • Open source contribution
Powered by GitBook
On this page
  • 概念
  • 存储
  • 邻接矩阵
  • 邻接表
  • BFS
  • 例题
  • DFS
  • 例题

Was this helpful?

  1. Computer Science
  2. Algorithm

Graph

PreviousTreeNextString Matching

Last updated 5 years ago

Was this helpful?

概念

图(Graph)是一种非线性表结构。图中的元素叫做顶点(vertex),图中的顶点可以与任意其它顶点建立连接,这种连接叫做边(edge),与顶点相连接的边数叫做度(degree)。

边有方向的图叫做有向图,比如微博的用户关注与粉丝的关系,有向图中的度分为出度(Out-degree)和入度(In-degree)。入度表示指向这个顶点的边数,即粉丝数;出度表示这个顶点指向多少个其它顶点,即关注数。边没有方向的叫做无向图,比如微信好友关系。

边有权重的图叫做带权图(weighted graph),比如 qq 好友的亲密度。

所有的顶点都是连通的图叫做连通图。

存储

邻接矩阵

邻接矩阵(Adjacency Matrix)底层依赖于一个二维数组。如下图:

缺点:浪费存储空间。若是无向图,就白白浪费一半。若是稀疏图,则浪费非常严重,比如微信几亿用户。

优点:获取顶点关系时非常高效;方便计算,很多问题可以转换为矩阵计算。

邻接表

邻接表(Adjacency List)底层依赖于一维数组 + 列表。每个顶点对应一个列表。如下图:

这就是时间换空间的思想。尽管节约了很多空间,但是使用起来比较耗时。

// 无向图的实现
public final class Graph {
    private final int v;
    private final List<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        adj = new List[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }
}

优化:可以将列表换成其它数据结构,比如红黑树、跳表、散列表、有序动态数组(可用二分查找)等。

对于有向图来说,列表存储的是顶点指向的顶点,所以很容易查找用户关注了哪些用户。但是若要查找用户的粉丝列表,就很困难。所以需要一个逆邻接表,顶点存储的是指向它的顶点。

BFS

广度优先搜索(Breath-First-Search)即先查找最近的,然后是次近的。

/**
* bfs 搜索到的路径就是最短路径
*/
public void bfs(int s, int t) {
    int[] prev = new int[v];
    Arrays.fill(prev, -1);
    
    if (s == t) {
        print(prev, t);
    }
    
    boolean[] visited = new boolean[v];
    Arrays.fill(visited, false);
    visited[s] = true;
    
    Queue<Integer> queue = new LinkedList<>();
    queue.add(s);
    
    while (queue.size() > 0) {
        Integer p = queue.poll();
        for (int i : adj[p]) {
            if (!visited[i]) {
                prev[i] = p;
                if (i == t) {
                    print(prev, t);
                    return;
                }
                visited[i] = true;
                queue.add(i);
            }
        }
    }
}

时间复杂度 O(E),空间复杂度 O(V),E 表示边数,V 表示顶点数。

例题

DFS

深度优先搜索(Depth-First-Search)采用的是回溯思想,非常适合递归实现。

/**
* dfs 搜索到的路径不一定是最短路径
*/
public void dfs(int s, int t) {
    final AtomicReference<Boolean> found = new AtomicReference<>(false);
    
    boolean[] visited = new boolean[v];
    Arrays.fill(visited, false);
    
    int[] prev = new int[v];
    Arrays.fill(prev, -1);
    
    recurDfs(found, visited, prev, s, t);
    print(prev, t);
}

private void recurDfs(AtomicReference<Boolean> found, boolean[] visited, int[] prev, int s, int t) {
    if (visited[s] || found.get()) {
        return;
    }
    if (s == t) {
        found.set(true);
        return;
    }
    visited[s] = true;
    for (Integer i : adj[s]) {
        prev[i] = s;
        recurDfs(found, visited, prev, i, t);
    }
}

时间复杂度 O(E),空间复杂度 O(V),E 表示边数,V 表示顶点数。

DFS 和 BFS 是最简单的两种搜索方法,简单粗暴,没有什么优化,也叫做暴力搜索算法。适合于状态空间不大的图的搜索。

例题

LeetCode 102:二叉树按层输出。
LeetCode 104:二叉树叶子节点的最小深度。
LeetCode 111:二叉树叶子节点的最大深度。