在线客服: 点击这里给我发消息  新用户使用步骤:会员注册→充值→重新登入→进入资源
标题:Weighted Graphs
时间:2020-11-21 10:24:46
DOI:10.1007/978-3-030-59758-0_6
大小:3890 kb
页数:357 PAGES
下载: 点击下载
预览:

浏览器不支持嵌入PDF阅读,打开新页面在线阅读

目录:
  • Preface
  • Contents
  • 1. Introduction
    • 1.1 Correctness of Algorithms
    • 1.2 Running Time of Algorithms
      • 1.2.1 Explicit Formulas
      • 1.2.2 O-Notation
    • 1.3 Linear Difference Equations
      • 1.3.1 First-Order Linear Difference Equations
      • 1.3.2 Fibonacci Numbers
    • 1.4 The Master Method for Recurrences
    • 1.5 Design Techniques for Algorithms
      • 1.5.1 Recursion
      • 1.5.2 Divide and Conquer
      • 1.5.3 Greedy Algorithms
      • 1.5.4 Dynamic Programming
      • 1.5.5 Branch and Bound with Backtracking
    • 1.6 Randomized Algorithms
      • 1.6.1 Comparing Polynomials
      • 1.6.2 Verifying the Identity of Large Numbers
      • 1.6.3 Comparing Multivariate Polynomials
      • 1.6.4 Random Numbers
    • 1.7 Pseudo-code for Algorithms
    • 1.8 Textbooks on Algorithms and Data Structures
  • 2. Sorting and Searching
    • 2.1 Quicksort
      • 2.1.1 Running Time Analysis
      • 2.1.2 Memory Space Analysis
      • 2.1.3 Quicksort Without Stack
      • 2.1.4 Randomized Quicksort
    • 2.2 Heapsort
      • 2.2.1 Binary Heaps
      • 2.2.2 The Sorting Phase of Heapsort
      • 2.2.3 Running Time Analysis
      • 2.2.4 Heapsort Optimizations
      • 2.2.5Comparison of Quicksort and Heapsort
    • 2.3 A Lower Bound for Sorting by Comparison
    • 2.4 Searching in Arrays
      • 2.4.1 Sequential Search
      • 2.4.2 Binary Search
      • 2.4.3 Searching for the kth-Smallest Element
  • 3. Hashing
    • 3.1 Basic Terms
    • 3.2 Hash Functions
      • 3.2.1 Division and Multiplication
      • 3.2.2 Universal Families
    • 3.3 Collision Resolution
      • 3.3.1 Collision Resolution by Chaining
      • 3.3.2 Open Addressing
    • 3.4 Analysis of Hashing
      • 3.4.1 Chaining
      • 3.4.2 Open Addressing
  • 4. Trees
    • 4.1 Rooted Trees
    • 4.2 Binary Search Trees
      • 4.2.1 Searching and Inserting
      • 4.2.2 Deletion
    • 4.3 Balanced Trees
      • 4.3.1 Insert
      • 4.3.2 Delete
    • 4.4 Randomized Binary Search Trees
      • 4.4.1 The Treap Data Structure
      • 4.4.2 Search, Insert and Delete in Treaps
      • 4.4.3 Treaps with Random Priorities
    • 4.5 B-Trees
      • 4.5.1 Path Lengths
      • 4.5.2 Search and Insert
      • 4.5.3 Deleting Elements
    • 4.6 Code Trees
      • 4.6.1 Uniquely Decodable Codes
      • 4.6.2 Huffman Codes
      • 4.6.3 Arithmetic Codes
      • 4.6.4 Lempel-Ziv Codes
  • 5. Graphs
    • 5.1 Modeling Problems with Graphs
    • 5.2 Basic Definitions and Properties
    • 5.3 Representations of Graphs
    • 5.4 Basic Graph Algorithms
      • 5.4.1 Breadth-First Search
      • 5.4.2 Depth-First Search
    • 5.5 Directed Acyclic Graphs
    • 5.6 The Strongly Connected Components
    • 5.7 A Randomized Min-Cut Algorithm
  • 6. Weighted Graphs
    • 6.1 Basic Algorithms
      • 6.1.1 The Priority Queue
      • 6.1.2 The Union-Find Data Type
      • 6.1.3 The LCA and the RMQ Problem
    • 6.2 The Algorithms of Dijkstra and Prim
    • 6.3 The Algorithm of Kruskal
    • 6.4 The Algorithm of Boruvka
    • 6.5 Verification of Minimum Spanning Trees
    • 6.6 A Randomized MST Algorithm
    • 6.7 Transitive Closure and Distance Matrix
    • 6.8 Flow Networks
  • A. Probabilities
    • A.1 Finite Probability Spaces and Random Variables
    • A.2 Special Discrete Distributions
  • B. Mathematical Terminology and Useful Formulas
  • References
  • Symbols
  • Index

本页内容由网络收集而来,版权归原创者所有,如有侵权请及时联系