山东大学 Design and Analysis of Algorithm 2019年 期末考试
Summary of Course
如题,后天上午期末考试,因课表冲突不得不突击复习,以下内容包括教材信息以及重点分析 (本科学过图论算法,简单的概念和证明以及本人熟悉的部分一带而过)
Textbook
《Introduction to Algorithm (Third Edition)》by Thomas H. Cormen,Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
Temporary Link:download PDF
Selected Solutions for《Introduction to Algorithm》
Temporary Link:download PDF
Key Points
Chapter 22 Basic Graph Algorithm
-
Graph Basics
Graph (Edge&Vertex)
Undirected Graph&Directed Graph
Adjacency
Repeated edge, Self-loop & Simple graph
Degree, Isolated vertex
Cycle, Sub-graph,
Connected (connected component, strongly connected, strongly connected component)
Special Graph (complete, bipartite, forest, tree, sparse, dense)
Theorem 1.1
Given an undirected graph ,
Copollary 1.2
Given an undirected graph , the number of vertices with odd degrees is even.
-
Representations of graphs
For an undirected graph ,
-
Adjacency-list:
Advantage:
When the graph is sparse, uses only O() memory.
Disvantage:
No quicker way to determine if a given edge is present in the graph than to search for v in the adjacency list . O() -
Adjacency matrix
Advantage:
Easily or quickly to determine if an edge is in the graph or not. O(1)
Disvantage:
Uses more memory to store a graph. O(2)
- Elementary graph algorithms
-
BFS(Breadth-First Search)
-
DFS(Deep-First Search)
-
White Path Theorem
-
Topological Sort
-
Strongly connected components
Chapter 23 Minimum spanning tree
- Kruskal algorithm
- Prim algorithm
Chapter 24 Single-Source Shortest Path
- Bellman-Ford algorithm
- Dijkstra Algorithm
- Proof of Dijkstra algorithm
Chapter 15 Dynamic programming
- Shortest path in DAGs
- Knapsack problem
- Bellman-Ford algorithm
Chapter 26 Maximum Flow
- Capacity-scaling algorithm
- Bipartite matching