算法第四版Part II：2014最新修订高清英文版

5星 · 超过95%的资源需积分: 31 37 浏览量更新于2024-07-23 1 收藏 10.67MB PDF 举报

"算法：第4版(Algorithms, 4th Edition) Part II，由Robert Sedgewick和Kevin Wayne合著，2014年2月发布，是该书的最新修订版，专注于Part II的内容。" 算法是计算机科学的核心组成部分，这本书《算法第四版》Part II深入探讨了这一主题。作者Robert Sedgewick和Kevin Wayne都是普林斯顿大学的教授，他们在算法领域具有深厚的理论基础和实践经验，使得本书成为学习算法的经典之作。 Part II通常涵盖了原书的高级主题或更深入的内容，可能包括但不限于以下几个方面的知识点： 1. **排序与搜索算法**：这部分可能会深入讲解各种排序算法，如快速排序、归并排序、堆排序、计数排序、基数排序等，以及搜索算法，如二分查找、哈希表查找等。它们的时间复杂度和空间复杂度分析对于理解算法效率至关重要。 2. **图算法**：图是描述许多实际问题的有效模型，书中可能涵盖深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法（Dijkstra、Floyd-Warshall、Bellman-Ford）、最小生成树（Prim、Kruskal）等。 3. **动态规划**：动态规划是一种用于解决最优化问题的强大技术，可能包括经典的背包问题、最长公共子序列、矩阵链乘法等例子，以及如何构造最优解的备忘录和迭代策略。 4. **数据结构**：除了基本的数据结构如数组、链表、栈和队列，可能还会涉及更复杂的数据结构，如红黑树、AVL树、B树、Trie树、字典树等，以及它们在特定问题中的应用。 5. **字符串处理**：这部分可能涵盖模式匹配算法（如KMP、Boyer-Moore、Rabin-Karp），字符串排序和压缩算法，以及文本处理中的其他技术。 6. **计算几何**：包括平面几何中的碰撞检测、最近点对查找、多边形处理等问题，以及相应的算法设计。 7. **概率和随机化算法**：这些算法利用概率论的概念，如Monte Carlo方法和Las Vegas算法，解决NP完全问题或者提高效率。 8. **网络流与匹配**：介绍最大流算法（如Ford-Fulkerson和Edmonds-Karp）和最小生成树在网络中的应用，以及 bipartite匹配问题。 9. **近似算法**：针对NP难问题，探讨如何找到接近最优解的算法，例如旅行商问题（TSP）和整数规划的近似算法。 10. **并行和分布式算法**：介绍如何在多处理器或多计算机环境下设计和分析算法，如分布式排序、分布式计算等。每一章通常包含实例、习题和编程挑战，旨在帮助读者理解和实现这些算法。此外，书中还可能包含对实际应用的讨论，比如如何在Google、Facebook等大型互联网公司的数据处理中应用这些算法。学习《算法第四版》Part II，读者不仅能掌握一系列高级算法，还能培养解决问题的能力，这对于任何想要在计算机科学领域深造或工作的人都极其有价值。

ptg12441863

airwise connections between items play a critical role in a vast array of compu-

tational applications. The relationships implied by these connections lead im-

mediately to a host of natural questions: Is there a way to connect one item to

another by following the connections? How many other items are connected to a given

item? What is the shortest chain of connections between this item and this other item?

To model such situations, we use abstract mathematical objects called graphs. In this

chapter, we examine basic properties of graphs in detail, setting the stage for us to study

a variety of algorithms that are useful for answering questions of the type just posed.

These algorithms serve as the basis for attacking problems in important applications

whose solution we could not even contemplate without good algorithmic technology.

Graph theory, a major branch of mathematics, has been studied intensively for hun-

dreds of years. Many important and useful properties of graphs have been discovered,

many important algorithms have been developed, and many difcult problems are still

actively being studied. In this chapter, we introduce a variety of fundamental graph

algorithms that are important in diverse applications.

Like so many of the other problem domains that we have studied, the algorithmic in-

vestigation of graphs is relatively recent. Although a few of the fundamental algorithms

are centuries old, the majority of the interesting ones have been discovered within the

last several decades and have beneted from the emergence of the algorithmic technol-

ogy that we have been studying. Even the simplest graph algorithms lead to useful com-

puter programs, and the nontrivial algorithms that we examine are among the most

elegant and interesting algorithms known.

To illustrate the diversity of applications that involve graph processing, we begin our

exploration of algorithms in this fertile area by introducing several examples.

515

ptg12441863

Maps. A person who is planning a trip may need to answer questions such as “What is

the shortest route from Providence to Princeton?” A seasoned traveler who has experi-

enced trafc delays on the shortest route may ask the question “What is the fastest way

to get from Providence to Princeton?” To answer such questions, we process informa-

tion about connections (roads) between items (intersections).

Web content. When we browse the web, we encounter pages that contain references

(links) to other pages and we move from page to page by clicking on the links. The

entire web is a graph, where the items are pages and the connections are links. Graph-

processing algorithms are essential components of the search engines that help us lo-

cate information on the web.

Circuits. An electric circuit comprises devices such as transistors, resistors, and ca-

pacitors that are intricately wired together. We use computers to control machines that

make circuits and to check that the circuits perform desired functions. We need to an-

swer simple questions such as “Is a short-circuit present?” as well as complicated ques-

tions such as “Can we lay out this circuit on a chip without making any wires cross?”

The answer to the rst question depends on only the properties of the connections

(wires), whereas the answer to the second question requires detailed information about

the wires, the devices that those wires connect, and the physical constraints of the chip.

Schedules. A manufacturing process requires a variety of jobs to be performed, under

a set of constraints that specify that certain jobs cannot be started until certain other

jobs have been completed. How do we schedule the jobs such that we both respect the

given constraints and complete the whole process in the least amount of time?

Commerce. Retailers and nancial institutions track buy/sell orders in a market. A

connection in this situation represents the transfer of cash and goods between an in-

stitution and a customer. Knowledge of the nature of the connection structure in this

instance may enhance our understanding of the nature of the market.

Matching. Students apply for positions in selective institutions such as social clubs,

universities, or medical schools. Items correspond to the students and the institutions;

connections correspond to the applications. We want to discover methods for matching

interested students with available positions.

Computer networks. A computer network consists of interconnected sites that send,

forward, and receive messages of various types. We are interested in knowing about the

nature of the interconnection structure because we want to lay wires and build switches

that can handle the trafc efciently.

516 CHAPTER 4

Graphs

ptg12441863

Software. A compiler builds graphs to represent relationships among modules in a

large software system. The items are the various classes or modules that comprise the

system; connections are associated either with the possibility that a method in one class

might call another (static analysis) or with actual calls while the system is in operation

(dynamic analysis). We need to analyze the graph to determine how best to allocate

resources to the program most efciently.

Social networks. When you use a social network, you build explicit connections with

your friends. Items correspond to people; connections are to friends or followers. Un-

derstanding the properties of these networks is a modern graph-processing application

of intense interest not just to companies that support such networks, but also in poli-

tics, diplomacy, entertainment, education, marketing, and many other domains.

       for which graphs are the ap-

propriate abstraction and also the range of computational problems that we might

encounter when we work with graphs. Thousands of such problems have been studied,

but many problems can be addressed in the context of one of several basic graph mod-

els—we will study the most important

ones in this chapter. In practical appli-

cations, it is common for the volume of

data involved to be truly huge, so that

efcient algorithms make the difference

between whether or not a solution is at

all feasible.

To organize the presentation, we

progress through the four most impor-

tant types of graph models: undirected

graphs (with simple connections), di-

graphs (where the direction of each con-

nection is signicant), edge-weighted

graphs (where each connection has an

associated weight), and edge-weighted

digraphs (where each connection has

both a direction and a weight).

application item connection

map intersection road

web content page link

circuit device wire

schedule job constraint

commerce customer transaction

matching student application

computer network site connection

soware method call

social network person friendship

Typical graph applications

517CHAPTER 4

Graphs

ptg12441863

4.1 UNDIRECTED GRAPHS

   is the study of graph models where edges are nothing more than

connections between vertices. We use the term undirected graph in contexts where we

need to distinguish this model from other models (such as the title of this section), but,

since this is the simplest model, we start with the following denition:

Definition. A graph is a set of vertices and a collection of edges that each connect a

pair of vertices.

Vertex names are not important to the denition, but we need a way

to refer to vertices. By convention, we use the names 0 through V1

for the vertices in a V-vertex graph. The main reason that we choose

this system is to make it easy to write code that efciently accesses in-

formation corresponding to each vertex, using array indexing. It is not

difcult to use a symbol table to establish a 1-1 mapping to associate

V arbitrary vertex names with the V integers between 0 and V1 (see

page 548), so the convenience of using indices as vertex names comes

without loss of generality (and without much loss of efciency). We

use the notation

v-w to refer to an edge that connects v and w; the nota-

tion w-v is an alternate way to refer to the same edge.

We draw a graph with circles for the vertices and lines connecting

them for the edges. A drawing gives us intuition about the structure of

the graph; but this intuition can be misleading, because the graph is

dened independently of the drawing. For example, the two drawings

at left represent the same graph, because the graph is nothing more than its (unor-

dered) set of vertices and its (unordered) collection of edges (vertex pairs).

Anomalies. Our denition allows two simple anomalies:

n

A self-loop is an edge that connects a vertex to itself.

n

Two edges that connect the same pair of vertices are parallel.

Mathematicians sometimes refer to graphs with parallel edges

as multigraphs and graphs with no parallel edges or self-loops as

simple graphs. Typically, our implementations allow self-loops and

parallel edges (because they arise in applications), but we do not include them in ex-

amples. Thus, we can refer to every edge just by naming the two vertices it connects.

Two drawings of the same graph

Anomalies

parallel

edges

self-loop

518

ptg12441863

Glossary A substantial amount of nomenclature is associated with graphs. Most of

the terms have straightforward denitions, and, for reference, we consider them in one

place: here.

When there is an edge connecting two vertices, we say that the vertices are adjacent

to one another and that the edge is incident to both vertices. The degree of a vertex is the

number of edges incident to it. A subgraph is a subset of a graph’s edges (and associated

vertices) that constitutes a graph. Many computational tasks

involve identifying subgraphs of various types. Of particular

interest are edges that take us through a sequence of vertices

in a graph.

Definition. A path in a graph is a sequence of vertices

connected by edges. A simple path is one with no repeated

vertices. A cycle is a path with at least one edge whose rst

and last vertices are the same. A simple cycle is a cycle with

no repeated edges or vertices (except the requisite repeti-

tion of the rst and last vertices). The length of a path or

a cycle is its number of edges.

Most often, we work with simple cycles and simple paths and

drop the simple modifer; when we want to allow repeated ver-

tices, we refer to general paths and cycles. We say that one vertex is connected to another

if there exists a path that contains both of them. We use notation like

u-v-w-x to repre-

sent a path from u to x and u-v-w-x-u to represent a cycle from u to v to w to x and back

to u again. Several of the algorithms that we consider nd paths and cycles. Moreover,

paths and cycles lead us to consider the structural properties of a graph as a whole:

Definition. A graph is connected if there is a path from every vertex to every other

vertex in the graph. A graph that is not connected consists of a set of connected com-

ponents, which are maximal connected subgraphs.

Intuitively, if the vertices were physical objects, such as knots or beads, and the edges

were physical connections, such as strings or wires, a connected graph would stay in

one piece if picked up by any vertex, and a graph that is not connected comprises two or

more such pieces. Generally, processing a graph necessitates processing the connected

components one at a time.

Anatomy of a graph

cycle of

length 5

vertex

vertex of

degree 3

edge

path of

length 4

connected

components

5194.1

Undirected Graphs

剩余436页未读，继续阅读

wihiw

粉丝: 5
资源: 3

算法第四版Part II：2014最新修订高清英文版

算法第4版Part I：2014年2月最新修订高清英文PDF

Java算法练习精要：Algorithms-Exercises（第4版）解析

Java算法课程练习：Algorithms_4th实践指南

AWP.Algorithms.Part.I II.4th.2014.2

Algorithms 4th Edition.pdf.zip

读书笔记：Introduction to Algorithms, Third Edition 算法导论第3版.zip

Mit Press - Introduction To Algorithms 2Nd Edition Incl Exercises Edition.part2.rar

Introduction.to.Algorithms,2th.part2.rar

Introduction.to.Algorithms,2th.part1.rar

[麻省理工学院-算法导论].Introduction.to.Algorithms,.Second.Edition.part2.rar

最新资源