十、附录

关于

包括这一部分是为了帮助学生完成书中的活动。它包括学生为实现活动目标而要执行的详细步骤。

第 1 章:列表、栈和队列

活动 1:实现歌曲播放列表

在本练习中，我们将实现一个双重链表的调整版本，它可以用来存储歌曲播放列表并支持必要的功能。按照以下步骤完成活动:

让我们首先包含头部，并用所需的数据成员编写节点结构:

#include <iostream>
template <typename T>
struct cir_list_node
{
    T* data;
    cir_list_node *next, *prev;

~cir_list_node()
    {
        delete data;
    }
};
template <typename T>
struct cir_list
{
    public:
        using node = cir_list_node<T>;
        using node_ptr = node*;
    private:
        node_ptr head;
        size_t n;

Now, let's write a basic constructor and size function:

public:
cir_list(): n(0)
{
    head = new node{NULL, NULL, NULL};  // Dummy node – having NULL data
    head->next = head;
    head->prev = head;
}
size_t size() const
{
    return n;
}

稍后我们将讨论在使用迭代器进行迭代的情况下，为什么在第一个和最后一个节点之间需要一个伪节点。

现在，让我们编写insert和erase函数。两者都需要插入或删除一个值:

void insert(const T& value)
{
    node_ptr newNode = new node{new T(value), NULL, NULL};
    n++ ;
auto dummy = head->prev;
dummy->next = newNode;
newNode->prev = dummy;
    if(head == dummy)
    {
        dummy->prev = newNode;
        newNode->next = dummy;
        head = newNode;
        return;
    }
    newNode->next = head;
    head->prev = newNode;
    head = newNode;
}
void erase(const T& value)
{
    auto cur = head, dummy = head->prev;
    while(cur != dummy)
    {
        if(*(cur->data) == value)
        {
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            if(cur == head)
                head = head->next;
            delete cur;
            n--;
            return;
        }
        cur = cur->next;
    }
}

现在，让我们为所需的迭代器编写一个基本结构，并添加成员来访问实际数据:

struct cir_list_it
{
private:
    node_ptr ptr;
public:
    cir_list_it(node_ptr p) : ptr(p)
    {}

    T& operator*()
    {
        return *(ptr->data);
    }
    node_ptr get()
    {
        return ptr;
    }

现在，让我们实现迭代器的核心功能——增量前和增量后:

cir_list_it& operator++()
{
    ptr = ptr->next;
    return *this;
}
cir_list_it operator++(int)
{
    cir_list_it it = *this;
    ++(*this);
    return it;    
}

让我们添加与减量相关的操作，使其双向化:

cir_list_it& operator--()
{
    ptr = ptr->prev;
    return *this;
}
cir_list_it operator--(int)
{
    cir_list_it it = *this;
    --(*this);
    return it;
}

让我们为迭代器实现等式相关的运算符，这对于基于范围的循环来说是必不可少的:

friend bool operator==(const cir_list_it& it1, const cir_list_it& it2)
{
    return it1.ptr == it2.ptr;
}
friend bool operator!=(const cir_list_it& it1, const cir_list_it& it2)
{
    return it1.ptr != it2.ptr;
}
};

现在，让我们也用它们的const版本来编写begin和end功能:

cir_list_it begin()
{
    return cir_list_it{head};
}
cir_list_it begin() const
{
    return cir_list_it{head};
}
cir_list_it end()
{
    return cir_list_it{head->prev};
}
cir_list_it end() const
{
    return cir_list_it{head->prev};
}

让我们编写一个复制构造函数、初始化列表构造函数和析构函数:

cir_list(const cir_list<T>& other): cir_list()
{
// Although, the following will insert the elements in a reverse order, it won't matter in a logical sense since this is a circular list.
    for(const auto& i: other)
        insert(i);
}
cir_list(const std::initializer_list<T>& il): head(NULL), n(0)
{

// Although, the following will insert the elements in a reverse order, it won't matter in a logical sense since this is a circular list.
    for(const auto& i: il)
        insert(i);
}
~cir_list()
{
    while(size())
    {
        erase(head->data);
    }
}
};

现在，让我们为实际应用的音乐播放器播放列表添加一个类。为了便于理解，我们不再存储歌曲，而是直接存储指示歌曲 ID 的整数:

```cpp
struct playlist
{
    cir_list<int> list;
```

现在让我们实现添加和删除歌曲的功能:

```cpp
void insert(int song)
{
    list.insert(song);
}
void erase(int song)
{
    list.erase(song);
}
```

现在，让我们实现打印所有歌曲的功能:

```cpp
void loopOnce()
{
    for(auto& song: list)
        std::cout << song << " ";
    std::cout << std::endl;
}
};
```

让我们写一个main函数来使用我们音乐播放器的播放列表:

```cpp
int main()
{
    playlist pl;
    pl.insert(1);
    pl.insert(2);
    std::cout << "Playlist: ";
    pl.loopOnce();
    playlist pl2 = pl;
    pl2.erase(2);
    pl2.insert(3);
    std::cout << "Second playlist: ";
    pl2.loopOnce();
}
```

执行此操作后，您应该会得到如下输出:

```cpp
Playlist: 2 1 
Second playlist: 3 1
```

活动 2:模拟纸牌游戏

在本练习中，我们将模拟一个纸牌游戏，并实现一个有效的数据结构来存储每个玩家的纸牌信息。按照以下步骤完成活动:

首先，让我们包括必要的标题:

#include <iostream>
#include <vector>
#include <array>
#include <sstream>
#include <algorithm>
#include <random>
#include <chrono>

现在，让我们创建一个存储卡片的类和一个正确打印卡片的实用方法:

struct card
{
    int number;
    enum suit
    {
        HEART,
        SPADE,
        CLUB,
        DIAMOND
    } suit;
    std::string to_string() const
    {
        std::ostringstream os;
        if(number > 0 && number <= 10)
            os << number;
        else
{
switch(number)
{
case 1:
    os << "Ace";
    break;
    case 11:
        os << "Jack";
        break;
    case 12:
        os << "Queen";
        break;
    case 13:
        os << "King";
        break;
    default:
        return "Invalid card";
}
        }
        os << " of ";
        switch(suit)
        {
            case HEART:
                os << "hearts";
                break;
            case SPADE:
                os << "spades";
                break;
            case CLUB:
                os << "clubs";
                break;
            case DIAMOND:
                os << "diamonds";
                break;            
        }
        return os.str();
    }
};

现在，我们可以创建一副牌并洗牌，将牌随机分发给四个玩家中的每一个。我们将在一个game类中编写这个逻辑，稍后在main函数中调用这些函数:

struct game
{
    std::array<card, 52> deck;
    std::vector<card> player1, player2, player3, player4;
    void buildDeck()
    {
        for(int i = 0; i < 13; i++)
            deck[i] = card{i + 1, card::HEART};
        for(int i = 0; i < 13; i++)
            deck[i + 13] = card{i + 1, card::SPADE};
        for(int i = 0; i < 13; i++)
            deck[i + 26] = card{i + 1, card::CLUB};
        for(int i = 0; i < 13; i++)
            deck[i + 39] = card{i + 1, card::DIAMOND};
    }
    void dealCards()
    {
        unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
        std::shuffle(deck.begin(), deck.end(), std::default_random_engine(seed));
        player1 = {deck.begin(), deck.begin() + 13};
player2 = {deck.begin() + 13, deck.begin() + 26};
player3 = {deck.begin() + 26, deck.begin() + 39};
player4 = {deck.begin() + 39, deck.end()};
    }

让我们写下玩一轮的核心逻辑。为了避免代码重复，我们将编写一个实用函数，该函数将比较两个玩家的手牌，并在需要时移除两张牌:

bool compareAndRemove(std::vector<card>& p1, std::vector<card>& p2)
{
    if(p1.back().number == p2.back().number)
    {
        p1.pop_back();
        p2.pop_back();
        return true;
    }
    return false;
}
void playOneRound()
{
        if(compareAndRemove(player1, player2))
        {
            compareAndRemove(player3, player4);
            return;
        }
        else if(compareAndRemove(player1, player3))
        {
            compareAndRemove(player2, player4);
            return;
        }
        else if(compareAndRemove(player1, player4))
        {
            compareAndRemove(player2, player3);
            return;
        }
        else if(compareAndRemove(player2, player3))
        {
            return;
        }
        else if(compareAndRemove(player2, player4))
        {
            return;
        }
        else if(compareAndRemove(player3, player4))
        {
return;
        }
        unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
        std::shuffle(player1.begin(), player1.end(), std::default_random_engine(seed));
        std::shuffle(player2.begin(), player2.end(), std::default_random_engine(seed));
        std::shuffle(player3.begin(), player3.end(), std::default_random_engine(seed));
        std::shuffle(player4.begin(), player4.end(), std::default_random_engine(seed));
}

现在，让我们写下主要逻辑，找出谁是赢家。我们将在一个循环中调用前面的函数，直到其中一个玩家可以扔掉他们所有的牌。为了使代码更易读，我们将编写另一个实用函数来检查游戏是否已经完成:

bool isGameComplete() const
{
    return player1.empty() || player2.empty() || player3.empty() || player4.empty();
}
void playGame()
{
        while(not isGameComplete())
        {
            playOneRound();    
        }
}

为了找出谁是赢家，让我们在启动main函数之前写一个实用函数:

int getWinner() const
{
    if(player1.empty())
        return 1;
    if(player2.empty())
        return 2;
    if(player3.empty())
        return 3;
    if(player4.empty())
        return 4;
}
};

最后，我们编写main函数来执行游戏:

int main()
{
    game newGame;
    newGame.buildDeck();
    newGame.dealCards();
    newGame.playGame();
    auto winner = newGame.getWinner();
    std::cout << "Player " << winner << " won the game." << std::endl;
}

One of the possible outputs could be as follows:
```
Player 4 won the game.
```
注意

获胜者可以是从 1 到 4 的任何玩家。由于游戏是基于执行期间时间播种的随机性，任何玩家都可以获胜。多次运行代码可能每次都会产生不同的输出。

活动 3:模拟办公室中共享打印机的队列

在本练习中，我们将实现一个队列，用于处理对办公室共享打印机的打印请求。按照以下步骤完成活动:

让我们包括所需的标题:
```
#include <iostream>
#include <queue>
```

让我们实现一个Job类:

class Job
{
    int id;
    std::string user;
    int time;
    static int count;
public:
    Job(const std::string& u, int t) : user(u), time(t), id(++ count)
    {}
    friend std::ostream& operator<<(std::ostream& os, const Job& j)
     {
    os << "id: " << id << ", user: " << user << ", time: " << time << " seconds" << std::endl;    return os;
     }
};
int Job::count = 0;

现在，让我们实现Printer类。我们将使用std::queue为jobs制定先到先得的政策。我们将根据类可以在内存中存储的最大作业数来保持类模板化:

template <size_t N>
class Printer
{
    std::queue<Job> jobs;
public:
    bool addNewJob(const Job& job)
    {
        if(jobs.size() == N)
            return false;
        std::cout << "Added job in the queue: " << job;
        jobs.push(job);
        return true;
    }

现在，让我们实现另一个主要功能——打印作业:

    void startPrinting()
    {
        while(not jobs.empty())
        {
            std::cout << "Processing job: " << jobs.front();
            jobs.pop();
        }
    }
};

现在，让我们使用这些类来模拟场景:

int main()
{
    Printer<5> printer;
    Job j1("John", 10);
    Job j2("Jerry", 4);
    Job j3("Jimmy", 5);
    Job j4("George", 7);
    Job j5("Bill", 8);
    Job j6("Kenny", 10);
    printer.addNewJob(j1);
    printer.addNewJob(j2);
    printer.addNewJob(j3);
    printer.addNewJob(j4);
    printer.addNewJob(j5);
    if(not printer.addNewJob(j6))  // Can't add as queue is full.
    {
        std::cout << "Couldn't add 6th job" << std::endl;
    }
    printer.startPrinting();

    printer.addNewJob(j6);  // Can add now, as queue got emptied
    printer.startPrinting();
}

下面是前面代码的输出:

Added job in the queue: id: 1, user: John, time: 10 seconds
Added job in the queue: id: 2, user: Jerry, time: 4 seconds
Added job in the queue: id: 3, user: Jimmy, time: 5 seconds
Added job in the queue: id: 4, user: George, time: 7 seconds
Added job in the queue: id: 5, user: Bill, time: 8 seconds
Couldn't add 6th job
Processing job: id: 1, user: John, time: 10 seconds
Processing job: id: 2, user: Jerry, time: 4 seconds
Processing job: id: 3, user: Jimmy, time: 5 seconds
Processing job: id: 4, user: George, time: 7 seconds
Processing job: id: 5, user: Bill, time: 8 seconds
Added job in the queue: id: 6, user: Kenny, time: 10 seconds
Processing job: id: 6, user: Kenny, time: 10 seconds

第 2 章:树、堆和图

活动 4:为文件系统创建数据结构

在本练习中，我们将使用文件系统的 N 元树创建一个数据结构。按照以下步骤完成活动:

首先，让我们包含所需的标题:

#include <iostream>
#include <vector>
#include <algorithm>

现在，让我们写一个节点来存储一个目录/文件的数据:

struct n_ary_node
{
    std::string name;
    bool is_dir;
    std::vector<n_ary_node*> children;
};

现在，让我们将这个节点包装在一个树形结构中，以获得一个好的接口，并添加一个静态成员，这样我们就可以存储当前目录:

struct file_system
{
    using node = n_ary_node;
    using node_ptr = node*;
private:
    node_ptr root;
    node_ptr cwd;

现在，让我们添加一个构造函数，这样我们就可以创建一个带有根目录的树:

public:
    file_system()
    {
        root = new node{"/", true, {}};
        cwd = root;  // We'll keep the current directory as root in the beginning
    }

现在，让我们添加一个函数来查找目录/文件:

node_ptr find(const std::string& path)
{
    if(path[0] == '/')  // Absolute path
    {
        return find_impl(root, path.substr(1));
    }
    else
    {
        return find_impl(cwd, path);
    }
}
private:
node_ptr find_impl(node_ptr directory, const std::string& path)
{
    if(path.empty())
        return directory;
    auto sep = path.find('/');
    std::string current_path = sep == std::string::npos ? path : path.substr(0, sep);
    std::string rest_path = sep == std::string::npos ? "" : path.substr(sep + 1);
    auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
    return child->name == current_path;
});
        if(found != directory->children.end())
        {
            return find_impl(*found, rest_path);
        }
    return NULL;
}

现在，让我们添加一个函数来添加一个目录:

public:
bool add(const std::string& path, bool is_dir)
{
    if(path[0] == '/')
    {
        return add_impl(root, path.substr(1), is_dir);
    }
    else
    {
        return add_impl(cwd, path, is_dir);
    }
}
private:
bool add_impl(node_ptr directory, const std::string& path, bool is_dir)
{
    if(not directory->is_dir)
    {
        std::cout << directory->name << " is a file." << std::endl;
        return false;
    }

auto sep = path.find('/');
// This is the last part of the path for adding directory. It's a base condition of the recursion
    if(sep == std::string::npos)
    {
        auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
    return child->name == path;
});
if(found != directory->children.end())
{
    std::cout << "There's already a file/directory named " << path << " inside " << directory->name << "." << std::endl;
    return false;
}
directory->children.push_back(new node{path, is_dir, {}});
return true;
    }

    // If the next segment of the path is still a directory
    std::string next_dir = path.substr(0, sep);
    auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
    return child->name == next_dir && child->is_dir;
});
        if(found != directory->children.end())
        {
            return add_impl(*found, path.substr(sep + 1), is_dir);
        }

std::cout << "There's no directory named " << next_dir << " inside " << directory->name << "." << std::endl;
    return false;
}

现在，让我们添加一个函数来更改当前目录。这将非常简单，因为我们已经有一个函数来寻找路径:

public:
bool change_dir(const std::string& path)
{
    auto found = find(path);
    if(found && found->is_dir)
    {
        cwd = found;
        std::cout << "Current working directory changed to " << cwd->name << "." << std::endl;
        return true;
    }
    std::cout << "Path not found." << std::endl;
    return false;
}

现在，让我们添加一个函数来打印目录或文件。对于一个文件，我们只打印文件名。对于一个目录，我们将打印它所有孩子的名字，就像 Linux 中的ls命令:

public:
void show_path(const std::string& path)
{
    auto found = find(path);
    if(not found)
    {
        std::cout << "No such path: " << path << "." << std::endl;
        return;
    }
    if(found->is_dir)
    {
        for(auto child: found->children)
        {
std::cout << (child->is_dir ? "d " : "- ") << child->name << std::endl;}
    }
    else
    {
        std::cout << "- " << found->name << std::endl;
    }
}
};

Let's write a main function so that we can use the aforementioned functions:

int main()
{
    file_system fs;
    fs.add("usr", true);  // Add directory usr in "/"
    fs.add("etc", true);  // Add directory etc in "/"
    fs.add("var", true);  // Add directory var in "/"
    fs.add("tmp_file", false);  // Add file tmp_file in "/"
    std::cout << "Files/Directories under \"/\"" << std::endl;
    fs.show_path("/");  // List files/directories in "/"
    std::cout << std::endl;
    fs.change_dir("usr");
    fs.add("Packt", true);
    fs.add("Packt/Downloads", true);
    fs.add("Packt/Downloads/newFile.cpp", false);
    std::cout << "Let's see the contents of dir usr: " << std::endl;
    fs.show_path("usr");  // This will not print the path successfully, since we're already inside the dir usr. And there's no directory named usr inside it.
    std::cout << "Let's see the contents of \"/usr\"" << std::endl;
    fs.show_path("/usr");
    std::cout << "Let's see the contents of \"/usr/Packt/Downloads\"" << std::endl;
    fs.show_path("/usr/Packt/Downloads");

}

前面代码的输出如下:

Files/Directories under "/"
d usr
d etc
d var
- tmp_file
Current working directory changed to usr.
Let's try to print the contents of usr: 
No such path: usr.
Let's see the contents of "/usr"
d Packt
Contents of "/usr/Packt/Downloads"
- newFile.cpp

活动 5:使用堆的 K 路合并

在本练习中，我们将把多个排序数组合并成一个排序数组。这些步骤将帮助您完成活动:

从所需的标题开始:

#include <iostream>
#include <algorithm>
#include <vector>

Now, implement the main algorithm for merging. It will take a vector of a vector of int as input and will contain the vector of all the sorted vectors. Then, it will return the merged vector of int. First, let's build the heap node:

struct node
{
    int data;
    int listPosition;
    int dataPosition;
};
std::vector<int> merge(const std::vector<std::vector<int>>& input)
{
    auto comparator = [] (const node& left, const node& right)
        {
            if(left.data == right.data)
                return left.listPosition > right.listPosition;
            return left.data > right.data;
        };

正如我们所看到的，堆节点将包含三样东西——数据、列表在输入中的位置以及该列表中数据项的位置。

让我们建立堆。想法是用所有列表中最小的元素创建一个最小堆。所以，当我们从堆中弹出时，我们肯定会得到最小的元素。删除该元素后，我们需要插入同一列表中的下一个元素，如果它可用的话:
```
std::vector<node> heap;
for(int i = 0; i < input.size(); i++)
{
    heap.push_back({input[i][0], i, 0});
    std::push_heap(heap.begin(), heap.end(), comparator);
}
```

现在，我们将建立合成向量。我们将简单地从堆中移除元素，直到它为空，并用它所属的同一个列表中的下一个元素替换它，如果可用的话:

std::vector<int> result;
while(!heap.empty())
{
    std::pop_heap(heap.begin(), heap.end(), comparator);
    auto min = heap.back();
    heap.pop_back();
    result.push_back(min.data);
    int nextIndex = min.dataPosition + 1;
    if(nextIndex < input[min.listPosition].size())
    {
        heap.push_back({input[min.listPosition][nextIndex], min.listPosition, nextIndex});
        std::push_heap(heap.begin(), heap.end(), comparator);
    }
}
return result;
}

Let's write a main function so that we can use the preceding function:

int main()
{
    std::vector<int> v1 = {1, 3, 8, 15, 105};
    std::vector<int> v2 = {2, 3, 10, 11, 16, 20, 25};
    std::vector<int> v3 = {-2, 100, 1000};
    std::vector<int> v4 = {-1, 0, 14, 18};
    auto result = merge({v1, v2, v3, v4});
    for(auto i: result)
    std::cout << i << ' ';
    return 0;
}

您应该会看到以下输出:

-2 -1 0 1 2 3 3 8 10 11 14 15 16 18 20 25 100 105 1000

第 3 章:哈希表和布隆过滤器

活动 6:将长网址映射到短网址

在本练习中，我们将创建一个程序，将较短的网址映射到相应的较长的网址。按照以下步骤完成活动:

让我们包括所需的标题:

#include <iostream>
#include <unordered_map>

Let's write a struct called URLService that will provide the interface for the required services:
```
struct URLService
{
    using ActualURL = std::string;
    using TinyURL = std::string;
private:
    std::unordered_map<TinyURL, ActualURL> data;
```
如我们所见，我们已经创建了一个从小网址到原始网址的地图。这是因为我们使用小网址进行查找。我们想把它转换成原来的网址。正如我们前面看到的，地图可以基于一个键进行快速查找。因此，我们保留了较小的网址作为地图的关键字，原始网址作为地图的值。我们创建了别名，以避免混淆我们谈论的是哪个字符串。

我们来增加一个lookup功能:

public:
    std::pair<bool, ActualURL> lookup(const TinyURL& url) const
    {
        auto it = data.find(url);
        if(it == data.end())  // If small URL is not registered.
        {
            return std::make_pair(false, std::string());
        }
        else
        {
            return std::make_pair(true, it->second);
        }
    }

Now, let's write a function to register the smaller URL for the given actual URL:

bool registerURL(const ActualURL& actualURL, const TinyURL& tinyURL)
{
    auto found = lookup(tinyURL).first;
    if(found)
    {
        return false;
    }
    data[tinyURL] = actualURL;
    return true;
}

如果数据中已经存在条目，则registerURL函数返回。如果是这样，它将不会接触入口。否则，它将注册该条目并返回true以表明这一点。

Now, let's write a function to delete the entry:

bool deregisterURL(const TinyURL& tinyURL)
{
    auto found = lookup(tinyURL).first;
    if(found)
    {
        data.erase(tinyURL);
        return true;
    }
    return false;
}

可以看到，我们使用的是lookup函数，而不是再次重写查找逻辑。这个函数现在可读性更强了。

现在，让我们编写一个函数来打印日志记录的所有映射:

void printURLs() const
{
    for(const auto& entry: data)
    {
        std::cout << entry.first << " -> " << entry.second << std::endl;
    }
    std::cout << std::endl;
}
};

现在，编写main函数，这样我们就可以使用这个服务:

int main()
{
    URLService service;
    if(service.registerURL("https://www.packtpub.com/eu/big-data-and-business-intelligence/machine-learning-r-third-edition", "https://ml-r-v3"))
    {
        std::cout << "Registered https://ml-r-v3" << std::endl;
    }
    else
    {
        std::cout << "Couldn't register https://ml-r-v3" << std::endl;
    }
    if(service.registerURL("https://www.packtpub.com/eu/virtualization-and-cloud/hands-aws-penetration-testing-kali-linux", "https://aws-test-kali"))
    {
        std::cout << "Registered https://aws-test-kali" << std::endl;
    }
    else
    {
        std::cout << "Couldn't register https://aws-test-kali" << std::endl;
    }
    if(service.registerURL("https://www.packtpub.com/eu/application-development/hands-qt-python-developers", "https://qt-python"))
    {
        std::cout << "Registered https://qt-python" << std::endl;
    }
    else
    {
        std::cout << "Couldn't register https://qt-python" << std::endl;
    }

    auto findMLBook = service.lookup("https://ml-r-v3");
    if(findMLBook.first)
    {
        std::cout << "Actual URL: " << findMLBook.second << std::endl;
    }
    else
    {
        std::cout << "Couldn't find URL for book for ML." << std::endl;
    }
    auto findReactBook = service.lookup("https://react-cookbook");
    if(findReactBook.first)
    {
        std::cout << "Actual URL: " << findReactBook.second << std::endl;
    }
    else
    {
        std::cout << "Couldn't find URL for book for React." << std::endl;
    }
    if(service.deregisterURL("https://qt-python"))
    {
        std::cout << "Deregistered qt python link" << std::endl;
    }
    else
    {
        std::cout << "Couldn't deregister qt python link" << std::endl;
    }
    auto findQtBook = service.lookup("https://qt-python");
    if(findQtBook.first)
    {
        std::cout << "Actual URL: " << findQtBook.second << std::endl;
    }
    else
    {
        std::cout << "Couldn't find Qt Python book" << std::endl;
    }
    std::cout << "List of registered URLs: " << std::endl;
    service.printURLs();
}

让我们看看前面代码的输出:

Registered https://ml-r-v3
Registered https://aws-test-kali
Registered https://qt-python
Actual URL: https://www.packtpub.com/eu/big-data-and-business-intelligence/machine-learning-r-third-edition
Couldn't find URL for book for React.
Deregistered qt python link
Couldn't find Qt Python book
List of registered URLs: 
https://ml-r-v3 -> https://www.packtpub.com/eu/big-data-and-business-intelligence/machine-learning-r-third-edition
https://aws-test-kali -> https://www.packtpub.com/eu/virtualization-and-cloud/hands-aws-penetration-testing-kali-linux

正如我们所看到的，我们在最后得到了两个有效的网址，而不是我们成功注销的那个。

活动 7:电子邮件地址验证器

在本练习中，我们将创建一个验证器来检查用户请求的电子邮件地址是否已经被占用。使用以下步骤完成活动:

让我们包括所需的标题:

#include <iostream>
#include <vector>
#include <openssl/md5.h>

让我们为布隆过滤器添加一个类:

class BloomFilter
{
    int nHashes;
    std::vector<bool> bits;
    static constexpr int hashSize = 128/8;
    unsigned char hashValue[hashSize];

Let's add a constructor for this:
```
BloomFilter(int size, int hashes) : bits(size), nHashes(hashes)
{
    if(nHashes > hashSize)
    {
        throw ("Number of hash functions too high");
    }
    if(size > 255)
    {
        throw ("Size of bloom filter can't be >255");
    }
}
```
因为我们将使用哈希值缓冲区中的每个字节作为不同的哈希值，并且哈希值缓冲区的大小是 16 个字节(128 位)，所以我们不能有比这更多的哈希函数。由于每个哈希值只有 1 个字节，其可能的值为0到255。所以，布隆过滤器的尺寸不能超过255。因此，我们在构造函数本身抛出了一个错误。

现在，让我们写一个散列函数。它只是使用 MD5 函数来计算散列:

void hash(const std::string& key)
{
    MD5(reinterpret_cast<const unsigned char*>(key.data()), key.length(), hashValue);
}

Let's add the function so that we can insert an email:

void add(const std::string& key)
{
    hash(key);
    for(auto it = &hashValue[0]; it < &hashValue[nHashes]; it++)
    {
        bits[*it] = true;
    }
    std::cout << key << " added in bloom filter." << std::endl;
}

正如我们所看到的，我们从哈希值缓冲区中的字节0迭代到nHashes，并将每个位设置为1。

同样，让我们添加一个查找电子邮件地址的功能:

bool mayContain(const std::string &key)
    {
        hash(key);
        for (auto it = &hashValue[0]; it < &hashValue[nHashes]; it++)
        {
            if (!bits[*it])
            {
                std::cout << key << " email can by used." << std::endl;
                return false;
            }
        }
        std::cout << key << " email is used by someone else." << std::endl;
        return true;
    }
};

Let's add the main function:

int main()
{
    BloomFilter bloom(10, 15);
    bloom.add("abc@packt.com");
    bloom.add("xyz@packt.com");
    bloom.mayContain("abc");
    bloom.mayContain("xyz@packt.com");
    bloom.mayContain("xyz");
    bloom.add("abcd@packt.com");
    bloom.add("ab@packt.com");
    bloom.mayContain("abc");
    bloom.mayContain("ab@packt.com");
}

以下是上述代码的可能输出之一:

abc@packt.com added in bloom filter.
xyz@packt.com added in bloom filter.
abc email can by used.
xyz@packt.com email is used by someone else.
xyz email can by used.
abcd@packt.com added in bloom filter.
ab@packt.com added in bloom filter.
abcd email can by used.
ab@packt.com email is used by someone else.

这是可能的输出之一，因为 MD5 是一种随机化算法。如果我们深思熟虑地选择函数的数量和布隆过滤器的大小，我们应该使用 MD5 算法获得非常好的准确性。

第四章:分而治之

活动 8:接种疫苗

在本活动中，我们将存储和查找学生的疫苗接种状态，以确定他们是否需要接种疫苗。这些步骤应该有助于您完成活动:

首先包含以下标题:

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <numeric>

定义Student类如下:

class Student
{
private:
    std::pair<int, int> name;
    bool vaccinated;
public:
    // Constructor
    Student(std::pair<int, int> n, bool v) :
        name(n), vaccinated(v)
    {}
    // Getters
    auto get_name() { return name; }
    auto is_vaccinated() { return vaccinated; }
    // Two people are same if they have the same name
    bool operator ==(const Student& p) const
    {
        return this->name == p.name;
    }
    // The ordering of a set of people is defined by their name
    bool operator< (const Student& p) const
    {
        return this->name < p.name;
    }
    bool operator> (const Student& p) const
    {
        return this->name > p.name;
    }
};

下面的函数让我们从随机数据中生成一个学生:

auto generate_random_Student(int max)
{
    std::random_device rd;
    std::mt19937 rand(rd());
    // the IDs of Student should be in range [1, max]
    std::uniform_int_distribution<std::mt19937::result_type> uniform_dist(1, max);
    // Generate random credentials
    auto random_name = std::make_pair(uniform_dist(rand), uniform_dist(rand));
    bool is_vaccinated = uniform_dist(rand) % 2 ? true : false;
    return Student(random_name, is_vaccinated);
}

以下代码用于运行和测试我们的实现的输出:

 void search_test(int size, Student p)
{
    std::vector<Student> people;
    // Create a list of random people
    for (auto i = 0; i < size; i++)
        people.push_back(generate_random_Student(size));
    std::sort(people.begin(), people.end());
    // To measure the time taken, start the clock
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    bool search_result = needs_vaccination(p, people);
    // Stop the clock
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    std::cout << "Time taken to search = " <<
        std::chrono::duration_cast<std::chrono::microseconds>
        (end - begin).count() << " microseconds" << std::endl;
    if (search_result)
        std::cout << "Student (" << p.get_name().first 
<< " " << p.get_name().second << ") "
            << "needs vaccination." << std::endl;
    else
        std::cout << "Student (" << p.get_name().first 
<< " " << p.get_name().second << ") "
            << "does not need vaccination." << std::endl;
}

以下函数实现了我们判断是否需要接种疫苗的逻辑:

bool needs_vaccination(Student P, std::vector<Student>& people)
{
    auto first = people.begin();
    auto last = people.end();
    while (true)
    {
        auto range_length = std::distance(first, last);
        auto mid_element_index = std::floor(range_length / 2);
        auto mid_element = *(first + mid_element_index);
        // Return true if the Student is found in the sequence and 
// he/she's not vaccinated 
        if (mid_element == P && mid_element.is_vaccinated() == false)
            return true;
        else if (mid_element == P && mid_element.is_vaccinated() == true)
            return false;
        else if (mid_element > P)
            std::advance(last, -mid_element_index);
        if (mid_element < P)
            std::advance(first, mid_element_index);
        // Student not found in the sequence and therefore should be vaccinated
        if (range_length == 1)
            return true;
    }
}

Finally, the driver code is implemented as follows:

int main()
{
    // Generate a Student to search
    auto p = generate_random_Student(1000);
    search_test(1000, p);
    search_test(10000, p);
    search_test(100000, p);
    return 0;
}

注意

由于我们在步骤 3 中对值进行随机化，因此您的输出可能会与本练习中显示的预期输出不同。

活动 9:部分排序

部分快速排序只是对原始快速排序算法的轻微修改，该算法在练习 20 、快速排序中进行了演示。和那个练习相比，只有第四步不同。以下是参考实现:

添加以下头文件:

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>

接下来，我们将实现分区操作，如下所示:

 template <typename T>
auto partition(typename std::vector<T>::iterator begin,
    typename std::vector<T>::iterator end)
{
    auto pivot_val = *begin;
    auto left_iter = begin + 1;
    auto right_iter = end;
    while (true)
    {
        // Starting from the first element of vector, 
        // find an element that is greater than pivot.
        while (*left_iter <= pivot_val && std::distance(left_iter, right_iter) > 0)
            left_iter++ ;
        // Starting from the end of vector moving to the beginning, 
        // find an element that is lesser than the pivot.
        while (*right_iter > pivot_val && std::distance(left_iter, right_iter) > 0)
            right_iter--;
        // If left and right iterators meet, there are no elements left to swap. 
        // Else, swap the elements pointed to by the left and right iterators
        if (left_iter == right_iter)
            break;
        else
            std::iter_swap(left_iter, right_iter);
    }
    if (pivot_val > *right_iter)
        std::iter_swap(begin, right_iter);
    return right_iter;
}

由于期望的输出也需要快速排序算法的实现，我们将如下实现一个:

 template <typename T>
void quick_sort(typename std::vector<T>::iterator begin,
    typename std::vector<T>::iterator last)
{
    // If there are more than 1 elements in the vector
    if (std::distance(begin, last) >= 1)
    {
        // Apply the partition operation
        auto partition_iter = partition<T>(begin, last);
        // Recursively sort the vectors created by the partition operation
        quick_sort<T>(begin, partition_iter-1);
        quick_sort<T>(partition_iter, last);
    }
}

实现部分快速排序功能如下:

 template <typename T>
void partial_quick_sort(typename std::vector<T>::iterator begin,
    typename std::vector<T>::iterator last,
    size_t k)
{
    // If there are more than 1 elements in the vector
    if (std::distance(begin, last) >= 1)
    {
        // Apply the partition operation
        auto partition_iter = partition<T>(begin, last);
        // Recursively sort the vectors created by the partition operation
        partial_quick_sort<T>(begin, partition_iter-1, k);

        // Sort the right subvector only if the final position of pivot < k 
        if(std::distance(begin, partition_iter) < k)
            partial_quick_sort<T>(partition_iter, last, k);
    }
}

以下辅助函数可用于打印向量的内容并生成随机向量:

 template <typename T>
void print_vector(std::vector<T> arr)
{
    for (auto i : arr)
        std::cout << i << " ";
    std::cout << std::endl;
}
// Generates random vector of a given size with integers [1, size]
template <typename T>
auto generate_random_vector(T size)
{
    std::vector<T> V;
    V.reserve(size);
    std::random_device rd;
    std::mt19937 rand(rd());
    // the IDs of Student should be in range [1, max]
    std::uniform_int_distribution<std::mt19937::result_type> uniform_dist(1, size);
    for (T i = 0; i < size; i++)
        V.push_back(uniform_dist(rand));
    return std::move(V);
}

以下函数实现了我们的排序函数的测试逻辑:

// Sort the first K elements of a random vector of a given 'size'
template <typename T>
void test_partial_quicksort(size_t size, size_t k)
{
        // Create two copies of a random vector to use for the two algorithms
        auto random_vec = generate_random_vector<T>(size);
        auto random_vec_copy(random_vec);
        std::cout << "Original vector: "<<std::endl;
        print_vector<T>(random_vec); 

        // Measure the time taken by partial quick sort
        std::chrono::steady_clock::time_point 
begin_qsort = std::chrono::steady_clock::now();
        partial_quick_sort<T>(random_vec.begin(), random_vec.end()-1, k);
        std::chrono::steady_clock::time_point 
end_qsort = std::chrono::steady_clock::now();

        std::cout << std::endl << "Time taken by partial quick sort = " 
            << 'std::chrono::duration_cast<std::chrono::microseconds>
            (end_qsort - begin_qsort).count() 
            << " microseconds" << std::endl;

        std::cout << "Partially sorted vector (only first "<< k <<" elements):";
        print_vector<T>(random_vec);
        // Measure the time taken by partial quick sort
        begin_qsort = std::chrono::steady_clock::now();
        quick_sort<T>(random_vec_copy.begin(), random_vec_copy.end()-1);
        end_qsort = std::chrono::steady_clock::now();
        std::cout << std::endl <<"Time taken by full quick sort = " 
            << std::chrono::duration_cast<std::chrono::microseconds>
            (end_qsort - begin_qsort).count() 
            << " microseconds" << std::endl;

        std::cout << "Fully sorted vector: ";
        print_vector<T>(random_vec_copy);
}

最后添加驱动代码，如下:

 int main()
{
    test_partial_quicksort<unsigned>(100, 10);
    return 0;
}

活动 10:在 MapReduce 中实现字数统计

在本练习中，我们将实现 MapReduce 模型来解决字数统计问题。以下是本活动的解决方案:

Implement the map task as follows:

struct map_task : public mapreduce::map_task<
    std::string,                             // MapKey (filename)
    std::pair<char const*, std::uintmax_t>>  // MapValue (memory mapped file contents)
{
    template<typename Runtime>
    void operator()(Runtime& runtime, key_type const& key, value_type& value) const
    {
        bool in_word = false;
        char const* ptr = value.first;
        char const* end = ptr + value.second;
        char const* word = ptr;
        // Iterate over the contents of the file, extract words and emit a <word,1> pair.
        for (; ptr != end; ++ ptr)
        {
            // Convert the character to upper case.
            char const ch = std::toupper(*ptr, std::locale::classic());
            if (in_word)
            {
                if ((ch < 'A' || ch > 'Z') && ch != '\'')
                {
runtime.emit_intermediate(std::pair<char const*,
              std::uintmax_t> (word, ptr - word), 1);
                    in_word = false;
                }
            }
            else if (ch >= 'A' && ch <= 'Z')
            {
                word = ptr;
                in_word = true;
            }
        }
        // Handle the last word.
        if (in_word)
        {
            assert(ptr > word);
            runtime.emit_intermediate(std::pair<char const*,
                          std::uintmax_t>(word, ptr - word), 1);
        }
    }
};

前面的映射函数单独应用于输入目录中的每个文件。输入文件的内容被接受为value中的*字符。然后，内部循环遍历文件的内容，提取不同的单词并发出 <键，值> 对，其中键是一个单词，值设置为 1 。

Implement the reduce task as follows:

template<typename KeyType>
struct reduce_task : public mapreduce::reduce_task<KeyType, unsigned>
{
    using typename mapreduce::reduce_task<KeyType, unsigned>::key_type;
    template<typename Runtime, typename It>
    void operator()(Runtime& runtime, key_type const& key, It it, It const ite) const
    {
        runtime.emit(key, std::accumulate(it, ite, 0));    
}
};

然后，缩小操作可应用于地图功能发出的所有< key, value >对。由于在上一步中该值被设置为1，我们现在可以使用std::accumulate()来获得一个键在减少操作的输入对中出现的总次数。

第五章:贪婪算法

活动 11:区间调度问题

在本活动中，我们将找到任务的最佳计划，以最大限度地增加可以完成的任务数量。按照以下步骤完成活动:

添加需要的头文件，定义Task结构如下:

#include <list>
#include <algorithm>
#include <iostream>
#include <random>
// Every task is represented as a pair <start_time, end_time>
struct Task
{
    unsigned ID;
    unsigned start_time;
    unsigned end_time;
};

以下功能可用于生成带有随机数据的 N 任务列表:

auto initialize_tasks(size_t num_tasks)
{
    std::random_device rd;
    std::mt19937 rand(rd());
    std::uniform_int_distribution<std::mt19937::result_type> 
uniform_dist(1, num_tasks);
    // Create and initialize a set of tasks
    std::list<Task> tasks;
    for (unsigned i = 1; i <= num_tasks; i++)
    {
        auto start_time = uniform_dist(rand);
        auto duration = uniform_dist(rand);
        tasks.push_back({i, start_time, start_time + duration });
    }
    return tasks;
}

执行调度算法如下:

auto schedule(std::list<Task> tasks)
{
    // Sort the list of tasks by their end times
    tasks.sort([](const auto& lhs, const auto& rhs)
        { return lhs.end_time < rhs.end_time; });
    // Remove the tasks that interfere with one another
    for (auto curr_task = tasks.begin(); curr_task != tasks.end(); curr_task++)
    {
        // Point to the next task
        auto next_task = std::next(curr_task, 1);
        // While subsequent tasks interfere with the current task in iter
        while (next_task != tasks.end() &&
            next_task->start_time < curr_task->end_time)
        {
            next_task = tasks.erase(next_task);
        }
    }
    return tasks;
}

以下实用函数用于打印任务列表，测试我们的实现，并包含程序的驱动程序代码:

void print(std::list<Task>& tasks)
{
    std::cout << "Task ID \t Starting Time \t End time" << std::endl;
    for (auto t : tasks)
        std::cout << t.ID << "\t\t" << t.start_time << "\t\t" << t.end_time << std::endl;
}
void test_interval_scheduling(unsigned num_tasks)
{
    auto tasks = initialize_tasks(num_tasks);
    std::cout << "Original list of tasks: " << std::endl;
    print(tasks);
    std::cout << "Scheduled tasks: " << std::endl;
    auto scheduled_tasks = schedule(tasks);
    print(scheduled_tasks);
}
int main()
{
    test_interval_scheduling(20);
    return 0;
}

活动 12:威尔士-鲍威尔算法

在本练习中，我们将在图上实现威尔士-鲍威尔算法。这里给出了一个参考实现:

添加需要的头文件，声明后面要实现的图:

#include <unordered_map>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
template <typename T> class Graph;

实现结构，表示像这样的边:

template<typename T>
struct Edge
{
    size_t src;
    size_t dest;
    T weight;
    // To compare edges, only compare their weights,
    // and not the source/destination vertices
    inline bool operator< (const Edge<T>& e) const
    {
        return this->weight < e.weight;
    }
    inline bool operator> (const Edge<T>& e) const
    {
        return this->weight > e.weight;
    }
};

以下函数允许我们通过重载图数据类型的<<运算符来序列化和打印图:

template <typename T>
std::ostream& operator<<(std::ostream& os, const Graph<T>& G)
{
    for (auto i = 1; i < G.vertices(); i++)
    {
        os << i << ":\t";
        auto edges = G.outgoing_edges(i);
        for (auto& e : edges)
            os << "{" << e.dest << ": " << e.weight << "}, ";
        os << std::endl;
    }
    return os;
}

用边列表表示实现图，如下图所示:

template<typename T>
class Graph
{
public:
    // Initialize the graph with N vertices
    Graph(size_t N) : V(N)
    {}
    // Return number of vertices in the graph
    auto vertices() const
    {
        return V;
    }
    // Return all edges in the graph
    auto& edges() const
    {
        return edge_list;
    }
    void add_edge(Edge<T>&& e)
    {
        // Check if the source and destination vertices are within range
        if (e.src >= 1 && e.src <= V &&
            e.dest >= 1 && e.dest <= V)
            edge_list.emplace_back(e);
        else
            std::cerr << "Vertex out of bounds" << std::endl;
    }
    // Returns all outgoing edges from vertex v
    auto outgoing_edges(size_t v) const
    {
        std::vector<Edge<T>> edges_from_v;
        for (auto& e : edge_list)
        {
            if (e.src == v)
                edges_from_v.emplace_back(e);
        }
        return edges_from_v;
    }
    // Overloads the << operator so a graph be written directly to a stream
    // Can be used as std::cout << obj << std::endl;
    template <typename T>
    friend std::ostream& operator<< <>(std::ostream& os, const Graph<T>& G);
private:
    size_t V;        // Stores number of vertices in graph
    std::vector<Edge<T>> edge_list;
};

初始化我们将在威尔士-鲍威尔算法的实现中使用的颜色集。让这个颜色数为6，如下图unordered_map :

// Initialize the colors that will be used to color the vertices
std::unordered_map<size_t, std::string> color_map = {
    {1, "Red"},
    {2, "Blue"},
    {3, "Green"},
    {4, "Yellow"},
    {5, "Black"},
    {6, "White"}
};

像这样实现威尔士-鲍威尔图着色算法:

template<typename T>
auto welsh_powell_coloring(const Graph<T>& G)
{
    auto size = G.vertices();
    std::vector<std::pair<size_t, size_t>> degrees;
    // Collect the degrees of vertices as <vertex_ID, degree> pairs
    for (auto i = 1; i < size; i++)
        degrees.push_back(std::make_pair(i, G.outgoing_edges(i).size()));
    // Sort the vertices in decreasing order of degree
    std::sort(degrees.begin(),
        degrees.end(),
        [](const auto& a, const auto& b)
        { return a.second > b.second; });
    std::cout << "The vertices will be colored in the following order: " << std::endl;
    std::cout << "Vertex ID \t Degree" << std::endl;
    for (auto const i : degrees)
        std::cout << i.first << "\t\t" << i.second << std::endl;
    std::vector<size_t> assigned_colors(size);
    auto color_to_be_assigned = 1;
    while (true)
    {
        for (auto const i : degrees)
        {
            if (assigned_colors[i.first] != 0)
                continue;
            auto outgoing_edges = G.outgoing_edges(i.first);
            std::set<size_t> neighbour_colors;
            // We assume that the graph is bidirectional
            for (auto e : outgoing_edges)
            {
                auto dest_color = assigned_colors[e.dest];
                neighbour_colors.insert(dest_color);
            }
if (neighbour_colors.find(color_to_be_assigned) == neighbour_colors.end())
                assigned_colors[i.first] = color_to_be_assigned;
        }
        color_to_be_assigned++ ;
        // If there are no uncolored vertices left, exit
        if (std::find(assigned_colors.begin() + 1, assigned_colors.end(), 0) ==
            assigned_colors.end())
            break;
    }
    return assigned_colors;
}

以下函数输出颜色向量:

void print_colors(std::vector<size_t>& colors)
{
    for (auto i = 1; i < colors.size(); i++)
    {
        std::cout << i << ": " << color_map[colors[i]] << std::endl;
    }
}

最后，下面的驱动程序代码创建所需的图，运行顶点着色算法，并输出结果:

int main()
{
    using T = unsigned;
    Graph<T> G(9);
    std::map<unsigned, std::vector<std::pair<size_t, T>>> edges;
    edges[1] = { {2, 2}, {5, 3} };
    edges[2] = { {1, 2}, {5, 5}, {4, 1} };
    edges[3] = { {4, 2}, {7, 3} };
    edges[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
    edges[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
    edges[6] = { {4, 4}, {7, 4}, {8, 1} };
    edges[7] = { {3, 3}, {6, 4} };
    edges[8] = { {4, 5}, {5, 3}, {6, 1} };
    for (auto& i : edges)
        for (auto& j : i.second)
            G.add_edge(Edge<T>{ i.first, j.first, j.second });
    std::cout << "Original Graph" << std::endl;
    std::cout << G;
    auto colors = welsh_powell_coloring<T>(G);
    std::cout << "Vertex Colors: " << std::endl;
    print_colors(colors);
    return 0;
}

第六章:图算法一

活动 13:使用 DFS 找出一个图是否是二分图

在本练习中，我们将使用深度优先搜索遍历来检查一个图是否是二分图。按照以下步骤完成活动:

添加需要的头文件，声明要使用的图:

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <stack>
template<typename T> class Graph;

编写以下结构来定义我们的图中的一条边:

template<typename T>
struct Edge
{
    size_t src;
    size_t dest;
    T weight;
    // To compare edges, only compare their weights,
    // and not the source/destination vertices
    inline bool operator< (const Edge<T>& e) const
    {
        return this->weight < e.weight;
    }
    inline bool operator> (const Edge<T>& e) const
    {
        return this->weight > e.weight;
    }
};

使用以下功能重载图的<<运算符，以便将其写入标准输出:

template <typename T>
std::ostream& operator<<(std::ostream& os, const Graph<T>& G)
{
    for (auto i = 1; i < G.vertices(); i++)
    {
        os << i << ":\t";
        auto edges = G.outgoing_edges(i);
        for (auto& e : edges)
            os << "{" << e.dest << ": " << e.weight << "}, ";
        os << std::endl;
    }
    return os;
}

实现边列表图如下:

template<typename T>
class Graph
{
public:
    // Initialize the graph with N vertices
    Graph(size_t N) : V(N)
    {}
    // Return number of vertices in the graph
    auto vertices() const
    {
        return V;
    }
    // Return all edges in the graph
    auto& edges() const
    {
        return edge_list;
    }
    void add_edge(Edge<T>&& e)
    {
        // Check if the source and destination vertices are within range
        if (e.src >= 1 && e.src <= V &&
            e.dest >= 1 && e.dest <= V)
            edge_list.emplace_back(e);
        else
            std::cerr << "Vertex out of bounds" << std::endl;
    }
    // Returns all outgoing edges from vertex v
    auto outgoing_edges(size_t v) const
    {
        std::vector<Edge<T>> edges_from_v;
        for (auto& e : edge_list)
        {
            if (e.src == v)
                edges_from_v.emplace_back(e);
        }
        return edges_from_v;
    }
    // Overloads the << operator so a graph be written directly to a stream
    // Can be used as std::cout << obj << std::endl;
    template <typename T>
    friend std::ostream& operator<< <>(std::ostream& os, const Graph<T>& G);
private:
    size_t V;        // Stores number of vertices in graph
    std::vector<Edge<T>> edge_list;
};

创建图 6.17 所示的图，如下图:

template <typename T>
auto create_bipartite_reference_graph()
{
    Graph<T> G(10);
    std::map<unsigned, std::vector<std::pair<size_t, T>>> edges;
    edges[1] = { {2, 0} };
    edges[2] = { {1, 0}, {3, 0} , {8, 0} };
    edges[3] = { {2, 0}, {4, 0} };
    edges[4] = { {3, 0}, {6, 0} };
    edges[5] = { {7, 0}, {9, 0} };
    edges[6] = { {1, 0}, {4, 0} };
    edges[7] = { {5, 0} };
    edges[8] = { {2,0}, {9, 0} };
    edges[9] = { {5, 0} };
    for (auto& i : edges)
        for (auto& j : i.second)
            G.add_edge(Edge<T>{ i.first, j.first, j.second });
    return G;
}

现在，我们需要一个函数，以便实现我们的算法并检查该图是否是二分图。这样写函数:

template <typename T>
auto bipartite_check(const Graph<T>& G)
{
    std::stack<size_t> stack;
    std::set<size_t> visited;
    stack.push(1); // Assume that BFS always starts from vertex ID 1
    enum class colors {NONE, RED, BLUE};
    colors current_color{colors::BLUE}; // This variable tracks the color to be assigned to the next vertex that is visited.
    std::vector<colors> vertex_colors(G.vertices(), colors::NONE);
    while (!stack.empty())
    {
        auto current_vertex = stack.top();
        stack.pop();
        // If the current vertex hasn't been visited in the past
        if (visited.find(current_vertex) == visited.end())
        {
            visited.insert(current_vertex);
            vertex_colors[current_vertex] = current_color;
            if (current_color == colors::RED)
            {
std::cout << "Coloring vertex " << current_vertex << " RED" << std::endl;
                current_color = colors::BLUE;
            }
            else
            {
                std::cout << "Coloring vertex " 
<< current_vertex << " BLUE" << std::endl;
                current_color = colors::RED;
            }
            // Add unvisited adjacent vertices to the stack.
            for (auto e : G.outgoing_edges(current_vertex))
                if (visited.find(e.dest) == visited.end())
                    stack.push(e.dest);
        }
        // If the found vertex is already colored and 
        // has a color same as its parent's color, the graph is not bipartite
        else if (visited.find(current_vertex) != visited.end() && 
            ((vertex_colors[current_vertex] == colors::BLUE && 
                current_color == colors::RED) ||
            (vertex_colors[current_vertex] == colors::RED && 
                current_color == colors::BLUE)))
            return false;
    }
    // If all vertices have been colored, the graph is bipartite
    return true;
}

使用以下函数来实现测试和驱动程序代码，该代码测试我们的二分检查算法的实现:

template <typename T>
void test_bipartite()
{
    // Create an instance of and print the graph
    auto BG = create_bipartite_reference_graph<T>();
    std::cout << BG << std::endl;
    if (bipartite_check<T>(BG))
        std::cout << "The graph is bipartite" << std::endl;
    else
        std::cout << "The graph is not bipartite" << std::endl;
}
int main()
{
    using T = unsigned;
    test_bipartite<T>();
    return 0;
}

Run the program. You should see the following output:

图 6.34:活动 13 的输出

活动 14:纽约最短路径

在本练习中，我们将使用纽约市不同位置的图，并找到两个给定顶点之间的最短距离。按照以下步骤完成活动:

添加需要的头文件并声明图，如下图:

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <limits>
#include <queue>
#include <fstream>
#include <sstream>
template<typename T> class Graph;

实现将在图中使用的加权边:

template<typename T>
struct Edge
{
    size_t src;
    size_t dest;
    T weight;
    // To compare edges, only compare their weights,
    // and not the source/destination vertices
    inline bool operator< (const Edge<T>& e) const
    {
        return this->weight < e.weight;
    }
    inline bool operator> (const Edge<T>& e) const
    {
        return this->weight > e.weight;
    }
};

为Graph类重载<<操作符，以便它可以输出到 C++ 流:

template <typename T>
std::ostream& operator<<(std::ostream& os, const Graph<T>& G)
{
    for (auto i = 1; i < G.vertices(); i++)
    {
        os << i << ":\t";
        auto edges = G.outgoing_edges(i);
        for (auto& e : edges)
            os << "{" << e.dest << ": " << e.weight << "}, ";
        os << std::endl;
    }
    return os;
}

实现一个边列表图，如下图所示:

template<typename T>
class Graph
{
public:
    // Initialize the graph with N vertices
    Graph(size_t N) : V(N)
    {}
    // Return number of vertices in the graph
    auto vertices() const
    {
        return V;
    }
    // Return all edges in the graph
    auto& edges() const
    {
        return edge_list;
    }
    void add_edge(Edge<T>&& e)
    {
        // Check if the source and destination vertices are within range
        if (e.src >= 1 && e.src <= V &&
            e.dest >= 1 && e.dest <= V)
            edge_list.emplace_back(e);
        else
            std::cerr << "Vertex out of bounds" << std::endl;
    }
    // Returns all outgoing edges from vertex v
    auto outgoing_edges(size_t v) const
    {
        std::vector<Edge<T>> edges_from_v;
        for (auto& e : edge_list)
        {
            if (e.src == v)
                edges_from_v.emplace_back(e);
        }
        return edges_from_v;
    }
    // Overloads the << operator so a graph be written directly to a stream
    // Can be used as std::cout << obj << std::endl;
    template <typename T>
    friend std::ostream& operator<< <>(std::ostream& os, const Graph<T>& G);
private:
    size_t V;        // Stores number of vertices in graph
    std::vector<Edge<T>> edge_list;
};

编写以下函数，以便解析图文件并准备图:

template <typename T>
auto read_graph_from_file()
{
    std::ifstream infile("USA-road-d.NY.gr");
    size_t num_vertices, num_edges;
    std::string line;

    // Read the problem description line that starts with 'p' and looks like:
    // p <num_vertices> <num_edges>
    while (std::getline(infile, line))
    {
        if (line[0] == 'p')
        {
            std::istringstream iss(line);
            char p;
            std::string sp;
            iss >> p >>sp >> num_vertices >> num_edges; 
            std::cout << "Num vertices: " << num_vertices 
<< " Num edges: " << num_edges <<std::endl;
            break;
        }
    }
    Graph<T> G(num_vertices + 1);
    // Read the edges and edge weights, which look like:
    // a <source_vertex> <destination_vertex> <weight>
    while (std::getline(infile, line))
    {
        if (line[0] == 'a')
        {
            std::istringstream iss(line);
            char p;
            size_t source_vertex, dest_vertex;
            T weight;
            iss >> p >> source_vertex >> dest_vertex >> weight;
            G.add_edge(Edge<T>{source_vertex, dest_vertex, weight});
        }
    }
    infile.close();
    return G;
}

现在，我们需要一个实现Label结构的结构，当 Dijkstra 算法运行时，该结构将被分配给每个顶点。执行如下:

template<typename T>
struct Label
{
    size_t vertex_ID;
    T distance_from_source;
    Label(size_t _id, T _distance) :
        vertex_ID(_id),
        distance_from_source(_distance)
    {}
    // To compare labels, only compare their distances from source
    inline bool operator< (const Label<T>& l) const
    {
        return this->distance_from_source < l.distance_from_source;
    }
    inline bool operator> (const Label<T>& l) const
    {
        return this->distance_from_source > l.distance_from_source;
    }
    inline bool operator() (const Label<T>& l) const
    {
        return this > l;
    }
};

Dijkstra 的算法可以实现如下:

template <typename T>
auto dijkstra_shortest_path(const Graph<T>& G, size_t src, size_t dest)
{
    std::priority_queue<Label<T>, std::vector<Label<T>>, std::greater<Label<T>>> heap;
    std::set<int> visited;
    std::vector<size_t> parent(G.vertices());
    std::vector<T> distance(G.vertices(), std::numeric_limits<T>::max());
    std::vector<size_t> shortest_path;
    heap.emplace(src, 0);
    parent[src] = src;
    // Search for the destination vertex in the graph
    while (!heap.empty()) {
        auto current_vertex = heap.top();
        heap.pop();
        // If the search has reached the destination vertex
        if (current_vertex.vertex_ID == dest) {
            std::cout << "Destination " << 
current_vertex.vertex_ID << " reached." << std::endl;
            break;
        }
        if (visited.find(current_vertex.vertex_ID) == visited.end()) {
            std::cout << "Settling vertex " << 
current_vertex.vertex_ID << std::endl;
            // For each outgoing edge from the current vertex, 
            // create a label for the destination vertex and add it to the heap
            for (auto e : G.outgoing_edges(current_vertex.vertex_ID)) {
                auto neighbor_vertex_ID = e.dest;
                auto new_distance_to_dest=current_vertex.distance_from_source 
+ e.weight;
                // Check if the new path to the destination vertex 
// has a lower cost than any previous paths found to it, if // yes, then this path should be preferred 
                if (new_distance_to_dest < distance[neighbor_vertex_ID]) {
                    heap.emplace(neighbor_vertex_ID, new_distance_to_dest);
                    parent[e.dest] = current_vertex.vertex_ID;
                    distance[e.dest] = new_distance_to_dest;
                }
            }
            visited.insert(current_vertex.vertex_ID);
        }
    }
    // Construct the path from source to the destination by backtracking 
    // using the parent indexes
    auto current_vertex = dest;
    while (current_vertex != src) {
        shortest_path.push_back(current_vertex);
        current_vertex = parent[current_vertex];
    }
    shortest_path.push_back(src);
    std::reverse(shortest_path.begin(), shortest_path.end());
    return shortest_path;
}

最后实现测试和驱动代码，如下图:

template<typename T>
void test_dijkstra()
{
    auto G = read_graph_from_file<T>();
    //std::cout << G << std::endl;
    auto shortest_path = dijkstra_shortest_path<T>(G, 913, 542);
    std::cout << "The shortest path between 913 and 542 is:" << std::endl;
    for (auto v : shortest_path)
        std::cout << v << " ";
    std::cout << std::endl;
}
int main()
{
    using T = unsigned;
    test_dijkstra<T>();
    return 0;
}

运行程序。您的输出应该如下所示:

图 6.35:活动 14 的输出

第七章:图算法二

活动 15:贪婪机器人

我们可以使用练习 33 、*实施贝尔曼-福特算法(第二部分)*中的精确算法来解决此活动。这里的潜在陷阱与正确解释所需任务和在您实际试图解决的问题的上下文中表示图有关。让我们开始吧:

第一步与练习相同。我们将包含相同的头，并定义一个Edge结构和一个UNKNOWN常数:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
struct Edge
{
        int start;
        int end;   
        int weight;
        Edge(int s, int e, int w) : start(s), end(e), weight(w) {}
};
const int UNKNOWN = INT_MAX;
vector<Edge*> edges;

在main()中，我们将声明一个整数，N，它决定了网格的高度/宽度。然后，我们将在for循环中从 0 迭代到 N * N - 1，并读取输入中给出的邻接数据:

int main()
{
    int N;
    cin >> N;
    for(int i = 0; i < N * N - 1; i++)
    {
        string directions;
        int power;

        cin >> directions >> power;

        ……
    }
    return 0;
}

现在，我们必须面对第一个潜在的问题——准确地表示相邻关系。通常情况下，我们倾向于考虑二维网格，虽然这样解决问题肯定是可能的，但它不是解决这个特定问题的最佳方法。要在一个维度上重新解释网格和邻接，我们必须简单地观察一维索引i和相应的二维网格坐标之间的以下关系:
```
CURRENT CELL: (x, y) —> i
NORTH: (x, y - 1) —> i - N
SOUTH: (x, y + 1) —> i + N
EAST: (x + 1, y) —> i + 1
WEST: (x - 1, y) —> i - 1 
```

我们可以通过遍历directions的字符并在switch语句中包含逻辑来处理这些关系:

for(int i = 0; i < N * N - 1; i++)
{
    string directions;
    int power;
    cin >> directions >> power;
    int next;
    for(auto d : directions)
    {
        switch(d)
        {
            case 'N': next = i - N; break;
            case 'S': next = i + N; break;
            case 'E': next = i + 1; break;
            case 'W': next = i - 1; break;
        }
        ……
    }
}

这导致了该活动的第二个有问题的方面；也就是power值的解释。这些，当然，将是定义相邻单元之间的边缘权重的值，但是在这个问题的上下文中，输入可能相当误导。根据问题的描述，我们希望找到与基线相比能量最大的到达终点的路径。粗心地阅读问题陈述可能会导致我们得出power值与边缘权重完全对应的结论，但这实际上会产生与我们想要实现的相反的结果。“能量最大化”可以被视为等同于“能量损失最小化”，由于负值实际上代表每个细胞的能量消耗，正值代表获得的能量，我们必须反转每个power值的符号:
```
for(auto d : directions)
{
    switch(d)
    {
        ……
    }
    // Add edge with power variable's sign reversed 
    edges.push_back(new Edge(i, next, -power));
}
```

现在，我们可以实施BellmanFord()。这次，我们的函数将把N和edges作为参数，返回一个等于最大相对能量的整数。为了简化我们的代码，我们将通过N作为网格中的单元格总数(即N * N ):

int BellmanFord(int N, vector<Edge*> edges)
{
    vector<int> distance(N, UNKNOWN);

    // Starting node is always index 0
    distance[0] = 0;
    for(int i = 0; i < N - 1; i++)
    {
        for(auto edge : edges)
        {
            if(distance[edge->start] == UNKNOWN)
            {
                continue;
            }
            if(distance[edge->start] + edge->weight < distance[edge->end])
            {
                distance[edge->end] = distance[edge->start] + edge->weight;
            }
        }
    }
    ……
}

根据标准实施，我们还将执行负周期检查，以处理与机器人贪婪的能量消耗相关的情况。在发现负周期的情况下，我们将返回UNKNOWN :

// Check for negative cycles
for(auto edge : edges)
{
    if(distance[edge->start] == UNKNOWN)
    {
        continue;
    }
    if(distance[edge->start] + edge->weight < distance[edge->end])
    {
        return UNKNOWN;
    }
}
return distance[N];

现在，我们可以在main()中执行对BellmanFord()的调用，并相应地处理输出:

int result = BellmanFord(N * N, edges);
(result == UNKNOWN) ? cout << "ABORT TRAVERSAL" << endl 
               : cout << -1 * result << endl;
return 0;

活动 16:随机化图统计

在本活动中，我们将为面试测试生成随机图表，如活动简介中所述。按照以下步骤完成活动:

首先包含以下标题，并定义UNKNOWN常数和Edge结构:

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
const int UNKNOWN = 1e9;
struct Edge 
{
    int u;
    int v;
    int w;
    Edge(int u, int v, int w) 
        : u(u), v(v), w(w) {}
};

我们的首要任务是处理每个图的生成。对于这个活动，我们将把图数据封装在一个结构中:

struct Graph
{
    int V, E;
    int maxWeight = -1e9;
    vector<Edge> edges;
    vector<vector<int>> adj;
    vector<vector<int>> weight;
    Graph(int v, int e) : V(v), E(e) 
    {
        ...
    }
};

为了确保生成的边和结果图是有效的，我们将创建一个邻接矩阵，并在每次尝试创建另一条边时检查它。如果同一两个节点之间的边已经存在，我们将开始另一次迭代。为了确保每个节点都至少有一条入边或出边，我们还会将矩阵中的对角线单元格设置为 true，用于作为边的一部分的每个节点。如果在创建E边后，任何对角线单元格为假，图将无效。我们可以通过将V设置为-1 :

Graph(int v, int e) : V(v), E(e)
{
    vector<vector<bool>> used(V, vector<bool>(V, false));
    adj.resize(V);
    weight.resize(V, vector<int>(V, UNKNOWN));
    while(e)
    {
        // Generate edge values
        int u = rand() % V;
        int v = rand() % V;
        int w = rand() % 100;
        if(rand() % 3 == 0)
        {
            w = -w;
        }
        // Check if the edge is valid
        if(u == v || used[u][v])
        {
            continue;
        }
        // Add to edges and mark as used
        edges.push_back(Edge(u, v, w));
        adj[u].push_back(v);
        weight[u][v] = w;
        maxWeight = max(maxWeight, w);
        used[u][u] = used[v][v] = used[u][v] = used[v][u] = true;
        e--;
    }
    for(int i = 0; i < V; i++)
    {
        // Set V to -1 to indicate the graph is invalid
        if(!used[i][i])
        {
            V = -1;
            break;
        }
    }
}

来指示图无效

让我们定义一个名为RESULT的枚举，并为我们需要考虑的每种类型的图定义相应的值:
```
enum RESULT
{
    VALID,
    INVALID,
    INTERESTING
};
```

在main()中，我们将接收输入，并为每种类型的图声明计数器。然后，我们将循环给定的迭代次数，创建一个新的图，并调用一个TestGraph()函数，该函数将一个Graph对象作为输入并返回RESULT。根据返回的值，我们将相应地递增每个计数器:

int main()
{
    unsigned int seed;
    int iterations, V, E;

    cin >> seed;
    cin >> iterations;
    cin >> V >> E;
    int invalid = 0;
    int valid = 0;
    int interesting = 0;
    srand(seed);
    while(iterations--)
    {
        Graph G(V, E);

        switch(TestGraph(G))
        {
            case INVALID: invalid++ ; break;
            case VALID: valid++ ; break;
            case INTERESTING: 
            {
                valid++ ;
                interesting++ ;
                break;
            }
        }
    }

    return 0;
}

TestGraph()将首先检查每个图的V值是否等于-1，如果等于则返回INVALID。否则，它将执行约翰逊算法来检索最短距离。第一步是使用贝尔曼-福特算法检索重新加权数组:
```
RESULT TestGraph(Graph G)
{
    if(G.V == -1)
    {
        return INVALID;
    }

    vector<int> distance = BellmanFord(G);
    ……
}
```

此解决方案中使用的 Bellman-Ford 的实现与练习中的实现完全一致，只是它接收了一个单一的Graph结构作为参数:

vector<int> BellmanFord(Graph G)
{
    vector<int> distance(G.V + 1, UNKNOWN);
    int s = G.V;
    for(int i = 0; i < G.V; i++)
    {
        G.edges.push_back(Edge(s, i, 0));
    }

    distance[s] = 0;
    for(int i = 0; i < G.V; i++)
    {
        for(auto edge : G.edges)
        {
            if(distance[edge.u] == UNKNOWN)
            {
                continue;
            }
            if(distance[edge.u] + edge.w < distance[edge.v])
            {
                distance[edge.v] = distance[edge.u] + edge.w;
            }
        }
    }
    for(auto edge : G.edges)
    {
        if(distance[edge.u] == UNKNOWN)
        {
            continue;
        }
        if(distance[edge.u] + edge.w < distance[edge.v])
        {
            return {};
        }
    }
return distance;
}

正如我们在练习中所做的，我们将检查BellmanFord()返回的向量是否为空。如果是，我们返回VALID(图有效但没意思)。否则，我们将通过重新加权边并对每个顶点调用迪克斯特拉算法来完成剩余的约翰逊算法:

RESULT TestGraph(Graph G)
{
    if(G.V == -1)
    {
        return INVALID;
    }

    vector<int> distance = BellmanFord(G);
    if(distance.empty())
    {
        return VALID;
    }
    for(auto edge : G.edges)
    {
        G.weight[edge.u][edge.v] += (distance[edge.u] – distance[edge.v]);
    }
    double result = 0;
    for(int i = 0; i < G.V; i++)
    {
        vector<int> shortest = Dijkstra(i, G);
    }
}

对于这个解决方案，让我们使用一种更有效形式的 Dijkstra 算法，它使用最小优先级队列来确定遍历顺序。为此，添加到队列中的每个值都必须由两个值组成:节点的索引及其距离值。我们将使用std::pair<int, int>来实现这一点，它在这里被重新定义为State。将元素推送到队列时，第一个值必须对应于距离，因为这将是优先级队列内部排序逻辑考虑的第一个值。所有这些都可以由std::priority_queue处理，但是我们需要提供三个分别对应于数据类型、容器和比较谓词的模板参数:

vector<int> Dijkstra(int source, Graph G)
{
    typedef pair<int, int> State;
    priority_queue<State, vector<State>, greater<State>> Q;
    vector<bool> visited(G.V, false);
    vector<int> distance(G.V, UNKNOWN);
    Q.push({0, source});
    distance[source] = 0;
    while(!Q.empty())
    {
        State top = Q.top();
        Q.pop();
        int node = top.second;
        int dist = top.first;
        visited[node] = true;
        for(auto next : G.adj[node])
        {
            if(visited[next])
            {
                continue;
            }
            if(dist != UNKNOWN && distance[next] > dist + G.weight[node][next])
            {
                distance[next] = distance[node] + G.weight[node][next];

                Q.push({distance[next], next});
            }

        }
    }
    return distance;
}

现在，我们将计算每组路径的TestGraph()中的平均值。我们通过迭代Dijkstra()返回的数组并保持索引不等于起始节点索引的距离总和来实现这一点。对应的数值不等于UNKNOWN。每次找到有效距离时，计数器也会递增，这样我们就可以通过将总和除以计数来获得最终平均值。然后将这些平均值中的每一个加到总结果中，再除以图中顶点的总数。请记住，我们必须再次重新加权距离以获得正确的值:

```cpp
double result = 0;
for(int i = 0; i < G.V; i++)
{
    vector<int> shortest = Dijkstra(i, G);
    double average = 0;
    int count = 0;
    for(int j = 0; j < G.V; j++)
    {
        if(i == j || shortest[j] == UNKNOWN)
        {
            continue;
        }
        shortest[j] += (distance[j] – distance[i]);
        average += shortest[j];
        count++ ;
    }
    average = average / count;
    result += average;
}
result = result / G.V;
```

最后一步是计算结果和图中最大权重的比值。如果数值小于0.5，我们返回INTERESTING；否则，我们退回VALID :

```cpp
double ratio = result / G.maxWeight;
return (ratio < 0.5) ? INTERESTING : VALID;
```

我们现在可以返回main()并打印输出。第一行将等于invalid的值。第二行等于interesting / valid，乘以100，以百分比显示。根据您的操作方式，您可能必须将变量转换为浮点型，以防止该值被舍入为整数。打印输出时，可以使用cout << fixed << setprecision(2) :

```cpp
double percentInteresting = (double)interesting / valid * 100;
cout << "INVALID GRAPHS: " << invalid << endl;
cout << "PERCENT INTERESTING: " << fixed << setprecision(2) << percentInteresting << endl;
return 0;
```

轻松确保四舍五入到两位小数

活动 17:迷宫-传送游戏

整个活动非常符合我们在本章中讨论的算法的标准实现，但有一些细微的修改。

问题描述中使用的术语，即迷宫、房间、传送点和点当然也可以被称为图、顶点、边和边权重。玩家能够无限降低分数的情况可以重新定义为负体重周期。按照以下步骤完成活动:

让我们首先包含必要的标题，并为活动设置变量和输入:

#include <iostream>
#include <vector>
#include <stack>
#include <climits>
struct Edge
{
    int start;
    int end;
    int weight;
    Edge(int s, int e, int w) : start(s), end(e), weight(w) {}
}
const int UNKNOWN = INT_MAX;
vector<Edge*> edges; // Collection of edge pointers

我们将以与我们最初的 Bellman-Ford 实现相同的形式接收输入，但是我们也将为我们的图构建邻接表(这里表示为整数向量的向量，adj ):

int main()
{
    int V, E;
    cin >> V >> E;
    vector<Edge*> edges;
    vector<vector<int>> adj(V + 1);
    for(int i = 0; i < E; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back(new Edge(u, v, w));
        adj[u].push_back(v);
    }
    vector<int> results;

问题的第一部分可以通过使用贝尔曼-福特来解决，其方式与练习 32 、*实现贝尔曼-福特算法(第一部分)*中概述的方式相同。但是，我们不会打印距离数组中的所有值，而是将它的返回类型设置为int，并包含几行额外的代码，以便它只返回距源顶点的最短距离(或者如果检测到负周期，则返回UNKNOWN:

int BellmanFord(int V, int start, vector<Edge*> edges)
{
    // Standard Bellman-Ford implementation
    vector<int> distance(V, UNKNOWN);

    distance[start] = 0;
    for(int i = 0; i < V - 1; i++)
    {
        for(auto edge : edges)
        {
            if(distance[edge->start] == UNKNOWN)
            {
                continue;
            }
            if(distance[edge->start] + edge->weight < distance[edge->end])
            {
                distance[edge->end] = distance[edge->start] + edge->weight;
            }
        }
    }
    // Return UNKNOWN if a negative cycle is found
    if(HasNegativeCycle(distance, edges))
    {
        return UNKNOWN;
    }
    int result = UNKNOWN;
    for(int i = 0; i < V; i++)
    {
        if(i == start) continue;
        result = min(result, distance[i]);
    }
    return result;
}

我们现在可以在main()中调用这个函数，并为输出填充一个结果向量。如果BellmanFord()恰好返回UNKNOWN，我们输出INVALID MAZE并终止程序(按照第一个条件)。如果某个起始节点没有输出边，我们可以完全跳过对BellmanFord的调用，只需将UNKNOWN追加到向量中。如果我们通过每个顶点，我们可以输出结果中的值(或者如果值为UNKNOWN，则输出DEAD END):

vector<int> results;
for(int i = 0; i < V; i++)
{
    if(adj[i].empty())
    {
        results.push_back(UNKNOWN);
        continue;
    }
    int shortest = BellmanFord(V, i, edges);
    if(shortest == UNKNOWN)
    {
        cout << "INVALID MAZE" << endl;
        return 0;
    }
    results.push_back(shortest);
}
for(int i = 0; i < V; i++)
{
    cout << i << ": ";
    (results[i] == INVALID) ? cout << "DEAD END" << endl : cout << results[i] << endl;
}

Now, we've come to the final condition – finding rooms in which players can get "stuck." Considering this case in terms of graph connectivity, we can redefine it as follows: find the strongly connected components that have no outgoing edges to other components. There are many simple ways to do this once all the strongly connected components have been acquired, but let's try to maximize our program's efficiency and add the necessary logic directly into our existing Kosaraju implementation.

为此，我们将声明两个新的向量:一个类型为bool，名为isStuck，另一个类型为int，名为inComponent。inComponent将存储每个节点所属组件的索引，而isStuck将告诉我们索引为i的组件是否与图的其余部分断开。

为了简单起见，让我们全局声明新变量:
```
vector<bool> isStuck;
vector<int> inComponent;
int componentIndex;
```
在这里，我们可以真正开始理解图结构的封装和面向对象实现的好处。不得不在我们的函数之间传递如此大量的数据，这不仅很难在心理上进行跟踪，而且会使我们未来可能想要进行的任何类型的修改变得非常复杂(更不用说像GetComponent(node, adj, visited, component, isStuck, inComponent, componentIndex)这样的函数调用令人头痛的外观了)。出于示例和可读性的考虑，我们选择全局声明这些数据，但是强烈建议不要在实际的全尺寸应用中使用这种方法。

在我们的Kosaraju函数中，我们初始化新数据如下:

isStuck.resize(V, true);
inComponent.resize(V, UNKNOWN);
componentIndex = 0;

现在，我们将开始我们的while循环，通过跟踪在栈上执行的每个 DFS 遍历来增加componentIndex:

while(!stack.empty())
{
    int node = stack.top();
    stack.pop();
    if(!visited[node])
    {
        vector<int> component;
        GetComponent(node, transpose, visited, component);
        components.push_back(component);
        componentIndex++ ;
    }
}

Now, we can write the logic in GetComponent(), which will handle this case. We will begin by setting the value of each node's index in inComponent to componentIndex. Now, as we iterate through each node's neighbors, we will include another condition that occurs when the nodes have already been visited:
```
component.push_back(node);
visited[node] = true;
inComponent[node] = componentIndex;
for(auto next : adj[node])
{
    if(!visited[next])
    {
        GetComponent(next, visited, adj, component);
    }
    else if(inComponent[node] != inComponent[next])
    {
        isStuck[inComponent[next]] = false;
    }
}
```
本质上，我们正在检查每个先前访问过的邻居的组件是否与当前节点的组件匹配。如果它们各自的组件标识不同，我们可以得出结论，邻居的组件有一条路径延伸到图的其他部分。

您可能想知道，为什么在有向图中，当前节点的边的存在表明相邻节点有一条超出其自身组件的输出路径。这个逻辑看起来“落后”的原因是因为它确实如此。请记住，我们正在遍历原始图的变换，因此邻接之间的方向都是相反的！

完成 DFS 遍历后，我们现在可以返回components向量并打印结果:

auto components = Kosaraju(V, adj);
for(int i = 0; i < components.size(); i++)
{
    if(isStuck[i])
    {
        for(auto node : components[i])
        {
            cout << node << " ";
        }
        cout << endl;
    }
}
return 0;

第八章:动态规划一

活动 18:旅行行程

让我们首先考虑这个问题的基本情况和递归关系。与我们在本章中讨论的其他一些例子不同，这个特殊的问题只有一个基本情况——到达目的地的点。中间状态也很简单:给定一个位于索引i的位置，该位置的距离限制为x，我们可以到达索引i + 1和i + x之间的任何位置(包括这两个位置)。例如，让我们考虑以下两个城市:

城市 1: distance[1] = 2
城市 2: distance[2] = 1

假设我们想计算到达指数3城市的途径数。因为我们既可以从城市 1 又可以从城市 2 到达城市 3 ，到达城市 3 的途径数相当于到达城市 1 的途径数和到达城市 2 的途径数之和。这种递归与斐波那契数列非常相似，只是形成当前状态子结构的先前状态的数量根据distance的值是可变的。

假设我们有以下四个城市:

[1]: distance = 5
[2]: distance = 3
[3]: distance = 1
[4]: distance = 2

由此，我们要计算到城市 5 的旅行方式的数量。为此，我们可以将子结构表述如下:

Cities reachable from index [1] -> { 2 3 4 5 6 }
Cities reachable from index [2] -> { 3 4 5 }
Cities reachable from index [3] -> { 4 }
Cities reachable from index [4] -> { 5 6 }

我们现在可以颠倒这个逻辑，从中找到我们可以通过到达给定位置的城市*:*

Cities that connect to index [1] -> START
Cities that connect to index [2] -> { 1 }
Cities that connect to index [3] -> { 1 2 }
Cities that connect to index [4] -> { 1 2 3 }
Cities that connect to index [5] -> { 1 2 }

更进一步，我们现在可以设计出状态逻辑的轮廓:

Ways to reach City 1 = 1 (START)
Ways to reach City 2 = 1 
    1 " 2
Ways to reach City 3 = 2
    1 " 2 " 3
    1 " 3
Ways to reach City 4 = 4
    1 " 2 " 3 " 4
    1 " 2 " 4
    1 " 3 " 4
    1 " 4
Ways to reach City 5 = 6
    1 " 2 " 3 " 4 " 5
    1 " 2 " 4 " 5
    1 " 2 " 5
    1 " 3 " 4 " 5
    1 " 4 " 5
    1 " 5

因此，我们可以如下定义重现:

Base case:

F(1) = 1 (我们已经到达目的地)
重复:

图 8.22:定义循环的公式

换句话说，到达给定位置的方式数等于到达与其相连的每个位置的方式数之和。使用这个逻辑，解决这个问题的递归函数可能如下所示:

F(n) -> number of ways to reach n'th location
F(i) = 
    if i = N: 
         return 1 
        Otherwise:
            result = 0
            for j = 1 to distance[i]:
                result = result + F(i + j)
            return result

现在我们已经有了问题状态的功能定义，让我们开始用代码实现它。

对于这个问题，我们将包括以下头和std名称空间:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

因为这个问题的输出需要计算超过 32 位的数字，所以我们将使用long long int作为结果。为了避免重复写这个，我们将使用typedef语句将其缩写为:
```
typedef long long LL;
```

Finally, we will define the modulus value for outputting the results:

const LL MOD = 1000000007;

处理这个问题中的输入和输出可以非常简单地实现:

int main()
{
    int n;
    cin >> n;

vector<int> distance(n);
    for(int i = 0; i < n; i++)
    {
        cin >> distance[i];
    }
    LL result = TravelItinerary(n, distance);
    cout << result << endl;
    return 0;
}

我们现在将定义一个名为TravelItinerary()的函数，该函数以n和distance为参数，并返回一个长整数:
```
LL TravelItinerary(int n, vector<int> distance)
{
    ...
}
```

现在，我们必须将前面介绍的递归算法转换为自下而上的方法。在伪代码中，这可能如下所示:

DP -> Array of size N + 1
DP[0] = 1 (There is one way to reach the starting location)
for i = 0 to N-1:
    for j = 1 to distance[i]: 

        DP[i + j] += DP[i]
return DP[N]

要在 C++ 中对此进行编码，我们将首先声明一个大小为n + 1的一维 DP 表，并将其所有元素初始化为0。然后，我们将它的第一个元素设置为1来表示基本情况:
```
vector<LL> DP(n + 1, 0);
DP[0] = 1;
```
To implement the recurrence we described previously, we will first reverse the distance array so that we are essentially beginning our calculations from the destination index. There are several reasons for this, but the primary reason is so that our algorithm processes the current state by combining the results of earlier states, as opposed to calculating future states from the results of the current state. Though the logic described in the pseudocode will produce the correct result, it is generally preferable to formulate bottom-up logic in terms of how the solutions of the previous states form the result of the immediate state:
```
reverse(distance.begin(), distance.end());
DP[0] = 1;
for(int i = 1; i <= n; i++)
{
    int dist = distance[i-1];
    for(int j = 1; j <= dist; j++)
    {
        DP[i] = (DP[i] + DP[i – j]) % MOD;
    }
}
return DP[n];
```
这当然是一个可行的解决问题的办法，在绝大多数情况下是完全令人满意的。然而，由于动态编程首先是一种优化技术，我们仍然应该问自己是否存在更好的方法。

处理额外信用测试案例

随着n和最大distance值的增加，甚至前面的算法最终也会被证明效率相当低。如果n = 10000000和距离值可以在 1 到 10000 之间变化，那么在最坏的情况下，内部for循环将不得不执行近 10000000000 次迭代。谢天谢地，有一种非常简单的技术可以让我们完全去除内部循环，这意味着我们必须对任何输入进行精确的n迭代。

为了处理这种减少，我们将创建一个prefix sum array，它将允许我们计算以前由内部循环在恒定时间内处理的范围和。如果您不熟悉这种技术，基本概念如下:
- 创建一个名为sums的数组，其长度等于要求和的值的总数加 1，所有元素初始化为0。
- 对于从0到n的每个指标i，使用sum[i + 1] = sum[i] + distance[i]。
- 计算总和后，任何范围内所有元素的总和[L, R]将等于sum[R+1] – sum[L]。

看看下面的例子:

        0 1  2  3  4
A    =   { 3 1 10  2  5 } 
           0 1 2  3  4  5
sums  =  { 0 3 4 14 16 21 }
range(1, 3) = A[1] + A[2] + A[3]
         = 1 + 10 + 2
         = 13
sums[4]  – sums[1] = 13
range(3, 4) = A[3] + A[4]
        = 2 + 5
        = 7
sums[5] – sums[3] = 7

我们可以在函数中实现这种方法，如下所示:

LL TravelItinerary(int n, vector<int> distance)
{
    vector<LL> DP(n + 1, 0);
    vector<LL> sums(n + 2, 0);
    DP[0] = sums[1] = 1;
    reverse(distance.begin(), distance.end());
    for(int i = 1; i <= n; i++)
    {
        int dist = distance[i-1];
        LL sum = sums[i] – sums[i – dist];
        DP[i] = (DP[i] + sum) % MOD;
        sums[i + 1] = (sums[i] + DP[i]) % MOD;
    }
    return DP[n];
}

现在，您可能还会遇到一个问题，那就是前面的函数返回的结果将是负的。这是因为模运算导致sums中索引较高的值小于索引较低的值，这导致减法时的结果为负。这种问题在需要对非常大的数字进行频繁模运算的问题中非常常见，但是可以通过稍微修改 return 语句来轻松解决:
```
return (DP[n] < 0) ? DP[n] + MOD : DP[n];
```

通过这些细微的修改，我们现在有了一个优雅而高效的解决方案，可以在几分之一秒内处理大量输入数组！

活动 19:利用记忆寻找最长的公共子序列

就像我们处理子集和问题一样，我们将在同一个代码文件中包含每种新方法，这样我们就可以比较它们的相对性能。为此，让我们以与之前相同的方式定义我们的GetTime()函数:

vector<string> types =
{
    "BRUTE FORCE",
    "MEMOIZATION",
    "TABULATION"
};
const int UNKNOWN = INT_MAX;
void GetTime(clock_t &timer, string type)
{
    timer = clock() - timer;
    cout << "TIME TAKEN USING " << type << ": " << fixed << setprecision(5) << (float)timer / CLOCKS_PER_SEC << " SECONDS" << endl;
    timer = clock();
}

现在，让我们定义我们的新函数LCS_Memoization()，它将采用与LCS_BruteForce()相同的参数，除了subsequence将改为对二维整数向量的引用memo :
```
int LCS_Memoization(string A, string B, int i, int j, vector<vector<int>> &memo)
{
    ……
}
```

这个函数的代码也与LCS_BruteForce()非常相似，除了我们将递归遍历两个字符串的前缀(从完整的字符串开始)并将结果存储在我们的memo表中的每一步:

// Base case — LCS is always zero for empty strings
if(i == 0 || j == 0)
{
    return 0;
}
// Have we found a result for the prefixes of the two strings?
if(memo[i - 1][j - 1] != UNKNOWN)
{
    // If so, return it
    return memo[i - 1][j - 1];
}
// Are the last characters of A's prefix and B's prefix equal?
if(A[i-1] == B[j-1])
{
    // LCS for this state is equal to 1 plus the LCS of the prefixes of A and B, both reduced by one character
    memo[i-1][j-1] = 1 + LCS_Memoization(A, B, i-1, j-1, memo);
    // Return the cached result
    return memo[i-1][j-1];
}
// If the last characters are not equal, LCS for this state is equal to the maximum LCS of A's prefix reduced by one character and B's prefix, and B's prefix reduced by one character and A's prefix
memo[i-1][j-1] = max(LCS_Memoization(A, B, i-1, j, memo), 
                 LCS_Memoization(A, B, i, j-1, memo));
return memo[i-1][j-1];

现在，让我们重新定义我们的main()函数来执行这两种方法，并显示每种方法花费的时间:

int main()
{
    string A, B;
    cin >> A >> B;
    int tests = 2;
    clock_t timer = clock();
    for(int i = 0; i < tests; i++)
    {
        int LCS;
        switch(i)
        {
            case 0:
            {
                LCS = LCS_BruteForce(A, B, 0, 0, {});
            #if DEBUG
                PrintSubsequences(A, B);
            #endif
                break;
            }
            case 1:
            {
                vector<vector<int>> memo(A.size(), vector<int>(B.size(), UNKNOWN));
                LCS = LCS_Memoization(A, B, A.size(), B.size(), memo);
                break;
            }
        }
        cout << "Length of the longest common subsequence of " << A << " and " << B << " is: " << LCS << ends;
        GetTime(timer, types[i]);
        cout << endl;
    }
    return 0;
}

现在，让我们尝试在两个新字符串ABCABDBEFBA和ABCBEFBEAB上执行我们的两个算法。您的程序输出应该类似于以下内容:

SIZE = 3
    ABC________ ABC_______
SIZE = 4
    ABC_B______ ABCB______
    ABC_B______ ABC___B___
    ABC_B______ ABC______B
    ABC___B____ ABC______B
    ABC____E___ ABC____E__
    ABC______B_ ABC___B___
    ABC______B_ ABC______B
    ABC_______A ABC_____A_
SIZE = 5
    ABCAB______ ABC_____AB
    ABC_B_B____ ABCB_____B
    ABC_B__E___ ABCB___E__
    ABC_B____B_ ABCB__B___
    ABC_B____B_ ABCB_____B
    ABC_B_____A ABCB____A_
    ABC_B_B____ ABC___B__B
    ABC_B__E___ ABC___BE__
    ABC_B____B_ ABC___B__B
    ABC_B_____A ABC___B_A_
    ABC___BE___ ABC___BE__
    ABC____E_B_ ABC____E_B
    ABC____E__A ABC____EA_
    ABC_____FB_ ABC__FB___
    ABC______BA ABC___B_A_
SIZE = 6
    ABC_B_BE___ ABCB__BE__
    ABC_B__E_B_ ABCB___E_B
    ABC_B__E__A ABCB___EA_
    ABC_B___FB_ ABCB_FB___
    ABC_B____BA ABCB__B_A_
    ABC_B__E_B_ ABC___BE_B
    ABC_B__E__A ABC___BEA_
    ABC___BE_B_ ABC___BE_B
    ABC___BE__A ABC___BEA_
    ABC____EFB_ ABC_EFB___
    ABC_____FBA ABC__FB_A_
SIZE = 7
    ABC_B_BE_B_ ABCB__BE_B
    ABC_B_BE__A ABCB__BEA_
    ABC_B__EFB_ ABCBEFB___
    ABC_B___FBA ABCB_FB_A_
    ABC____EFBA ABC_EFB_A_
SIZE = 8
    ABC_B__EFBA ABCBEFB_A_
Length of the longest common subsequence of ABCABDBEFBA and ABCBEFBEAB is: 8
TIME TAKEN USING BRUTE FORCE: 0.00242 SECONDS
Length of the longest common subsequence of ABCABDBEFBA and ABCBEFBEAB is: 8
TIME TAKEN USING MEMOIZATION: 0.00003 SECONDS

当然，暴力方法所花费的时间会受到打印出子序列的额外步骤的影响。将DEBUG常量设置为0后，再次运行我们的代码，现在输出如下:

Length of the longest common subsequence of ABCABDBEFBA and ABCBEFBEAB is: 8
TIME TAKEN USING BRUTE FORCE: 0.00055 SECONDS
Length of the longest common subsequence of ABCABDBEFBA and ABCBEFBEAB is: 8
TIME TAKEN USING MEMOIZATION: 0.00002 SECONDS

Now, let's try pushing the limits of our algorithm using two much larger strings, ABZCYDABAZADAEA and YABAZADBBEAAECYACAZ. You should get an output something like this:

Length of the longest common subsequence of ABZCYDABAZADAEA and YABAZADBBEAAECYACAZ is: 10
TIME TAKEN USING BRUTE FORCE: 8.47842 SECONDS
Length of the longest common subsequence of ABZCYDABAZADAEA and YABAZADBBEAAECYACAZ is: 10
TIME TAKEN USING MEMOIZATION: 0.00008 SECONDS

注意

所用时间的实际值会因您的系统而异。请注意数值的差异。

我们可以清楚地看到，记忆化带来的性能提升非常显著！

活动 20:使用列表寻找最长的公共子序列

正如我们之前所做的，我们将向包含我们的强力和记忆化解决方案的同一个代码文件中添加一个新函数LCS_Tabulation()。

我们的LCS_Tabulation()函数接收两个参数——字符串A和B，并返回一个字符串:
```
string LCS_Tabulation(string A, string B)
{
    ……
} 
```
我们的第一步是定义我们的 DP 表，我们将它表示为一个二维整数向量，第一维的大小等于比字符串A大一个，第二维的大小等于比字符串B大一个:
```
vector<vector<int>> DP(A.size() + 1, vector<int>(B.size() + 1));
```
像子集和问题一样，我们算法的所有逻辑可以包含在两个嵌套循环中，第一个循环从0迭代到A的大小，第二个循环从0迭代到B的大小:
```
for(int i = 0; i <= A.size(); i++)
{
    for(int j = 0; j <= B.size(); j++)
    {
        ……
    }
}
```
与子集和问题不同，我们的基本情况不会在循环执行之前处理，而是在每个循环开始时处理。这是因为只要A或B的前缀为空(即i = 0或j = 0，我们的基本情况就会发生。这在我们的代码中表示如下:
```
if(i == 0 || j == 0)
{
    DP[i][j] = 0;
}
```
现在，我们必须处理 A 前缀和 B 前缀末尾的字符相等的情况。请记住，该州的 LCS 值始终等于1，加上该州的 LCS 值，其中两个前缀都比当前小一个字符。这可以表示如下:
```
else if(A[i-1] == B[j-1])
{
    DP[i][j] = DP[i-1][j-1] + 1;
}
```
对于最后一种情况，结尾字符是而不是相等。对于这种状态，我们知道 LCS 等于 A 的前一个前缀和 B 的当前前缀的 LCS，以及 B 的前一个前缀和 A 的当前前缀的 LCS 的最大值。就我们表的结构而言，这相当于说 LCS 等于表的同一列和前一行中包含的值的最大值，以及同一行和前一列中包含的值:
```
else
{
    DP[i][j] = max(DP[i-1][j], DP[i][j-1]);
}
```

When we are done, the length of the longest common subsequence will be contained in DP[A.size()][B.size()] – the value of the LCS when the prefixes of both A and B are equal to the entire strings. Therefore, our complete DP logic is written as follows:

string LCS_Tabulation(string A, string B)
{
    vector<vector<int>> DP(A.size() + 1, vector<int>(B.size() + 1));
    for(int i = 0; i <= A.size(); i++)
    {
        for(int j = 0; j <= B.size(); j++)
        {
            if(i == 0 || j == 0)
            {
                DP[i][j] = 0;
            }
            else if(A[i-1] == B[j-1])
            {
                DP[i][j] = DP[i-1][j-1] + 1;
            }
            else
            {
                DP[i][j] = max(DP[i-1][j], DP[i][j-1]);
            }
        }
    }
    int length = DP[A.size()][B.size()];
    ……
}

在这一点上，我们已经讨论了找到最长公共子序列长度的几种方法，但是如果我们也想输出它的实际字符呢？当然，我们的强力解决方案可以做到这一点，但效率非常低；但是，使用前面 DP 表中包含的结果，我们可以非常容易地使用回溯来重建 LCS。让我们在表格中突出显示实现这一目标需要遵循的路径:

图 8.23:活动 20 DP 表

通过收集与值增加的路径中的每一列相关联的字符，我们得到 LCS ABCBEFBA。

Let's define a function called ReconstructLCS() that takes A, B, i, j, and DP as arguments. Our backtracking logic can be defined as follows:

if i = 0 or j = 0:
    Return an empty string
If the characters at the end of A's prefix and B's prefix are equal:
    Return the LCS of the next smaller prefix of both A and B, plus the equal character
Otherwise:
    If the value of DP(i - 1, j) is greater than the value of DP(i, j - 1):
      – Return the LCS of A's next smaller prefix with B's current prefix
      – Otherwise:
          Return the LCS of B's next smaller prefix with A's current prefix

在 C++ 中，这可以编码如下:

string ReconstructLCS(vector<vector<int>> &DP, string &A, string &B, int i, int j)
{
    if(i == 0 || j == 0)
    {
        return "";
    }
    if(A[i-1] == B[j-1])
    {
        return ReconstructLCS(DP, A, B, i-1, j-1) + A[i-1];
    }
    else if(DP[i-1][j] > DP[i][j-1])
    {
        return ReconstructLCS(DP, A, B, i-1, j);
    }
    else
    {
        return ReconstructLCS(DP, A, B, i, j-1);
    }
}

现在，我们可以在LCS_Tabulation()的最后一行返回ReconstructLCS()的结果:

string LCS_Tabulation(string A, string B)
{
    ……
    string lcs = ReconstructLCS(DP, A, B, A.size(), B.size());
    return lcs; 
}

我们在main()中的代码现在应该被修改以适应LCS_Tabulation()的增加:

```cpp
int main()
{
    string A, B;
    cin >> A >> B;
    int tests = 3;
    clock_t timer = clock();
    for(int i = 0; i < tests; i++)
    {
        int LCS;
        switch(i)
        {
            ……
            case 2:
            {
                string lcs = LCS_Tabulation(A, B);
                LCS = lcs.size();
                cout << "The longest common subsequence of " << A << " and " << B << " is: " << lcs << endl;
                break; 
            }
        }
        cout << "Length of the longest common subsequence of " << A << " and " << B << " is: " << LCS << endl;
        GetTime(timer, types[i]);
    }
    return 0;
}
```

Using the strings ABCABDBEFBA and ABCBEFBEAB, your program's output should be similar to this:

```cpp
Length of the longest common subsequence of ABCABDBEFBA and ABCBEFBEAB is: 8
TIME TAKEN USING BRUTE FORCE: 0.00060 SECONDS
Length of the longest common subsequence of ABCABDBEFBA and ABCBEFBEAB is: 8
TIME TAKEN USING MEMOIZATION: 0.00005 SECONDS
The longest common subsequence of ABCABDBEFBA and ABCBEFBEAB is: ABCBEFBA
Length of the longest common subsequence of ABCABDBEFBA and ABCBEFBEAB is: 8
TIME TAKEN USING TABULATION: 0.00009 SECONDS
```

#### 注意

所用时间的实际值会因您的系统而异。请注意数值的差异。

现在，我们看了另一个详细的例子，说明如何使用不同的技术将相同的逻辑应用于相同的问题，以及这对算法执行时间的相应影响。

活动 21:旋律排列

首先要问自己的问题是:在这个问题中，什么构成了一个单一的状态？

基本案例->空集合:

考虑旋律中的每个音符。
对于之前遇到的每个笔记子集，要么追加当前笔记，要么什么都不做。
如果子集与目标匹配，将其添加到解决方案中。

考虑到我们的选择是要么在前一个子集上附加一个注释，要么保持原样，我们可以将逻辑重述如下:

对于旋律中的给定音符，包含该音符的大小为| n |的子集的计数等于不包含该音符的大小为| n - 1 |的所有子集的总计数。

所以，每个状态都可以用两个维度来表达:

维度 1 :到目前为止考虑的旋律长度。
次元 2 :取一个之前找到的子集，将位于旋律索引[length - 1]的音符附加到它上面，或者什么都不做，形成的结果子集。

在伪代码中，逻辑可以表达如下:

for i = 1 to length of melody (inclusive):
    for each subset previously found:
    DP(i, subset) = DP(i, subset) + DP(i - 1, subset)
    DP(i, subset ∪ melody[i - 1]) = DP(i, subset ∪ melody[i - 1]) + DP(i - 1, subset)

所以，现在的首要问题是，我们如何代表这些状态？

请记住，对于一个 n 元素集合，总共有 2 n 个子集组成，例如，一组 4 个元素可以分成总共 2 4 (或 16)个子集:

S = { A, B, C, D }
{ }            —>        { _ _ _ _ }
{ A }          —>        { # _ _ _ }
{ B }          —>        { _ # _ _ }
{ C }          —>        { _ _ #_  }
{ D }          —>        { _ _ _ # }
{ A, B }       —>        { # # _ _ }
{ A, C }       —>        { # _ #_  }
{ A, D }       —>        { # _ _ # }
{ B, C }       —>        { _ # #_  }
{ B, D }       —>        { _ # _ # }
{ C, D }       —>        { _ _ # # }
{ A, B, C }    —>        { # # # _ }
{ A, B, D }    —>        { # # _ # }
{ A, C, D }    —>        { # _ # # }
{ B, C, D }    —>        { _ # # # }
{ A, B, C, D } —>        { # # # # }

如果我们以二进制形式从 0 迭代到 (2 4 - 1) ，我们得到以下数字:

0     —>    0000    —>    { _ _ _ _ }
1     —>    0001    —>    { # _ _ _ }
2     —>    0010    —>    { _ # _ _ }
3     —>    0011    —>    { # # _ _ }
4     —>    0100    —>    { _ _ # _ }
5     —>    0101    —>    { # _ # _ }
6     —>    0110    —>    { _ # # _ }
7     —>    0111    —>    { # # # _ }
8     —>    1000    —>    { _ _ _ # }
9     —>    1001    —>    { # _ _ # }
10    —>    1010    —>    { _ # _ # }
11    —>    1011    —>    { # # _ # }
12    —>    1100    —>    { _ _ # # }
13    —>    1101    —>    { # _ # # }
14    —>    1110    —>    { _ # # # }
15    —>    1111    —>    { # # # # }

如我们所见，从 0 到 2 n 的每个二进制数的数字正好对应于 n 个元素的一个可能子集的索引。由于音阶中有 12 个音符，这意味着总共有 2 12 (或 4，096)个可能的音符子集。通过将音阶中的每个音符映射到 2 的幂，我们可以使用按位算术来表示每个状态中遇到的子集。

以下是解决此活动的步骤:

继续讨论代码，我们应该从包含以下标题开始:

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

让我们从处理main()功能中的输入开始:

int main()
{
    int melodyLength;
    int setLength;
    cin >> melodyLength;
    vector<string> melody(melodyLength);
    for(int i = 0; i < melodyLength; i++)
    {
        cin >> melody[i];
    }
    cin >> setLength;
    vector<string> set(setLength);
    for(int i = 0; i < setLength; i++)
    {
        cin >> set[i];
    }
    ……
}

现在，让我们编写一个名为ConvertNotes()的函数，该函数接收一个音符串向量作为输入，并返回它们对应整数值的向量。音阶中 12 个总音符中的每一个都需要被映射到一个特定的位(从A开始)，其中在声学上等同的音符被分配到相同的值。我们将使用std::map来处理转换:

vector<int> ConvertNotes(vector<string> notes)
{
    map<string, int> M = 
    {
        { "A",  0 }, 
        { "A#", 1 },
        { "Bb", 1 },
        { "B",  2 },
        { "Cb", 2 },
        { "B#", 3 },
        { "C",  3 },
        { "C#", 4 },
        { "Db", 4 },
        { "D",  5 },
        { "D#", 6 },
        { "Eb", 6 },
        { "E",  7 },
        { "Fb", 7 },
        { "E#", 8 },
        { "F",  8 },
        { "F#", 9 },
        { "Gb", 9 },
        { "G",  10 },
        { "G#", 11 },
        { "Ab", 11 }
    };
    vector<int> converted;
    for(auto note : notes)
    {
        // Map to powers of 2
        converted.push_back(1 << M[note]); 
    }
    return converted;
}

现在，我们将定义一个名为CountMelodicPermutations()的函数，该函数以两个整数向量melody和set作为参数，并返回一个整数:
```
int CountMelodicPermutations(vector<int> melody, vector<int> set)
{
    ……
}
```
我们的第一步是定义我们的目标子集。我们将使用按位或运算符
```
unsigned int target = 0;
for(auto note : set)
{
    target |= note;
}
```
来实现这一点

例如，如果我们的目标集是{ C, F#, A }，映射将如下所示:

C  = 3
F# = 9
A  = 0
converted = { 23, 29, 20 } = { 8, 512, 1 }
target = (8 | 512 | 1) = 521
    0000001000
  + 0000000001
  + 1000000000
  = 1000001001

我们现在将定义一个二维 DP 表，第一维初始化为melodyLength + 1，第二维初始化为大于最大子集值的一个值(即111111111111 = 2 12 - 1，因此第二维将包含 2 12 ，或 4，096 个元素):
```
vector<vector<int>> DP(melody.size() + 1, vector<int>(4096, 0));
```

Our DP formula can be defined as follows:

Base case:
    DP(0, 0) —> 1 
Recurrence:
    DP(i, subset) —> DP(i, subset) + DP(i - 1, subset)
    DP(i, subset ∪ note[i-1]) —> DP(i, subset ∪ note[i]) + DP(i - 1, subset)

这里i的范围从1到旋律的长度。我们可以这样用 C++ 编写前面的逻辑:

// Base case —> empty set
DP[0][0] = 1;
for(int i = 1; i <= melody.size(); i++)
{
    for(unsigned int subset = 0; subset < 4096; subset++)
    {
        // Keep results for previous values of i
        DP[i][subset] += DP[i-1][subset];
        // Add results for union of subset with melody[i-1]
        DP[i][subset | melody[i-1]] += DP[i-1][subset];
    }
}
// Solution
return DP[melody.size()][target];

现在，我们可以通过调用CountMelodicPermutations并输出结果:
```
int count = CountMelodicPermutations(ConvertNotes(melody), ConvertNotes(set));
cout << count << endl;
```
来完成我们的main()功能

第九章:动态规划二

活动 22:利润最大化

在这项活动中，我们将优化我们的库存以实现利润最大化。按照以下步骤完成活动:

让我们从包含以下标题开始:

#include <iostream>
#include <vector>
using namespace std;

首先，我们将定义一个结构Product，它封装了与每个项目相关的数据:

struct Product 
{
    int quantity;
    int price;
    int value;
    Product(int q, int p, int v) 
        : quantity(q), price(p), value(v) {}
};

接下来，我们将处理main()函数中的输入，并填充一个Product类型的数组:

int main()
{
    int N, budget, capacity;
    cin >> N >> budget >> capacity;
    vector<Product> products;
    for(int i = 0; i < N; i++)
    {
        int quantity, cost, value;
        cin >> quantity >> cost >> value;
        products.push_back(Product(quantity, cost, value));
    }
...
return 0;
}

As with any DP algorithm, we must now define the states and base cases. We know that the subset of items that form the final result must match the following criteria:

–子集中所有产品的cost之和不得超过budget。

–子集中所有产品的quantity之和不得超过capacity。

–子集内所有产品的value之和必须最大化。

给定这些标准，我们可以看到每个状态可以由以下参数定义:

–正在考虑的当前项目

–以前购买的单位数量

–购买项目的总成本

–以零售价值销售产品后获得的总利润

我们还可以得出结论，当出现以下情况时，搜索将终止:

–所有项目都已考虑

–总成本超出预算

–单元总数超过容量

和传统的 0-1 背包问题一样，我们会从0到N-1线性考虑每一项。对于索引i中的每个项目，我们的状态可以通过两种方式之一进行转换:要么包含当前项目，要么离开它。用伪代码编写递归逻辑可能如下所示:
```
F(i, count, cost, total): 
I        –> The index of the current item 
Cost     –> The total money spent 
count    –> The number of units purchased
total    –> The total profit value of the chosen items
Base cases: 
    if i = N: return total
    if cost > budget: return 0
    if count > capacity: return 0
Recurrence:
F(i, count, cost, total) = maximum of:
F(i + 1, count + quantity[i], cost + price[i], 
      total + value[i]) – Include the item
        AND
    F(i + 1, count, cost, total) – Leave as-is
```
如上图所示，递归关系是根据i、count、cost和total的值定义的。将这个逻辑从上到下转换为自下而上可以这样完成:
```
Base case:
    DP(0, 0, 0) = 0 [Nothing has been chosen yet]
For i = 1 to N:
    Product -> quantity, price, value
    For cost = 0 to budget:
        For count = 0 to capacity:
            If price is greater than cost OR 
           quantity is greater than count:
                DP(i, cost, count) = DP(i-1, cost, count)
            Otherwise:
                DP(i, cost, count) = maximum of:
                    DP(i-1, cost, count)
                        AND
                    DP(i-1, cost – price, count – quantity) + value
```
换句话说，每个状态都是根据当前索引、总成本和总计数来描述的。对于每对有效的cost和count值，索引i处项目的当前结果将等于在索引i – 1处cost和count的相同值中找到的最大子集和(即DP[i – 1][cost][count])或者当前项目的value与索引i – 1处的最大和(即cost和count之和等于包括该项目之前的值(即DP[i - 1][cost – price][count – quantity] + value)。

我们可以将前面的逻辑编码如下:

vector<vector<vector<int>>> DP(N + 1, vector<vector<int>>(budget + 1, vector<int>(capacity + 1, 0)));
for(int i = 1; i <= N; i++)
{
    Product product = products[i-1];

for(int cost = 0; cost <= budget; cost++)
{
        for(int count = 0; count <= capacity; count++)
        {
            if(cost < product.price || count < product.quantity)
            {
                DP[i][cost][count] = DP[i-1][cost][count];
            }
            else
            {
                DP[i][cost][count] = max
                (
                    DP[i-1][cost][count],
                    DP[i-1][cost – product.price][count – product.quantity] + product.value
                );
            }
        }
}
cout << DP[N][budget][capacity] << endl;
}

如您所见，该实现相当于 0-1 背包解决方案，增加了一个维度。

活动 23:住宅道路

如果你没有一些深谋远虑，这个活动有很多潜在的陷阱。它最困难的方面是它需要许多不同的步骤，任何一点的粗心错误都可能导致整个程序失败。因此，建议逐步接近实现。所需的主要步骤如下:

处理输入
构建图表(查找邻接关系和权重值)
寻找图节点之间的最短距离
用最短路径重建边
重新绘制输入网格

因为这比本章中的其他活动要长得多，所以让我们分别讨论这些步骤。

第 0 步:初步设置

在我们编写任何与输入相关的代码之前，我们应该提前决定如何表示我们的数据。我们将收到如下输入:

两个整数，H和W，代表网格的高度和宽度。
一个整数，N，表示该房产包含的房屋数量。
H宽度为W的字符串，表示属性的映射。我们可以将这些数据存储为字符串的H元素向量。
H行代表地形崎岖程度的W整数。我们可以将这些值存储在一个整数矩阵中。
N包含两个整数的线，x和y，代表每个房子的坐标。为此，我们可以创建一个名为Point的简单结构，它包含两个整数，x和y。

现在，让我们看看实现:

Include the required headers and define some global constants and variables that we will need later in this problem. We will declare most of our data globally for the sake of convenience, but it is worth reiterating the point that this is generally considered bad practice within the context of a full-scale application:

#include <iostream>
#include <vector>
using namespace std;
const int UNKNOWN = 1e9;
const char EMPTY_SPACE = '.';
const string roads = "-|/\\";
struct Point
{
    int x;
    int y;
    Point(){}
    Point(int x, int y) : x(x), y(y) {}
};
int N;
int H, W;
vector<string> grid;
vector<vector<int>> terrain;
vector<vector<int>> cost;
vector<Point> houses;

第一步:处理输入

Since there is a fair amount of input required for this problem, let's contain it all in its own function, Input(), which will return void:

void Input()
{
    cin >> H >> W;
    cin >> N;
    grid.resize(H);
    houses.resize(N);
    terrain.resize(H, vector<int>(W, UNKNOWN));    cost.resize(H, vector<int>(W, UNKNOWN));
    // Map of property
    for(auto &row : grid) cin >> row;
    // Terrain ruggedness
    for(int I = 0; i < H; i++)
    {
        for(int j = 0; j < W; j++)
        {
            cin >> terrain[i][j];
        }
    }
    // House coordinates
    for(int i = 0; i < N; i++)
    {
        cin >> houses[i].x >> house[i].y;
        // Set house labels in grid
        grid[houses[i].y][houses[i].x] = char(i + 'A');
    }
}

第二步:构建图表

问题描述如下:

当且仅当两个房子之间有一条直接的水平、垂直或对角线路径时，才能在两个房子之间修建道路。
道路可能不会跨越水体、山脉、森林等等。
在两栋房子之间修建一条道路的成本等于两栋房子之间道路的耐用度总和。

为了测试第一个条件，我们只需要比较两点的坐标，并确定以下三个条件中的任何一个是否成立:

A.x = B.x(它们之间有一条水平线)
A.y = B.y(它们之间有一条垂直线)
| A.x – B.x | = | A.y – B.y |(它们之间有一条对角线)

现在，让我们回到我们的代码。

为此，让我们编写一个函数DirectLine()，该函数以两点a和b作为参数，并返回一个布尔值:

bool DirectLine(Point a, Point b)
{
    return a.x == b.x || a.y == b.y || abs(a.x – b.x) == abs(a.y – b.y);
}

为了处理第二种和第三种情况，我们可以简单地执行从网格中的点a到点b的线性遍历。当我们考虑网格中的每个点时，我们可以累加地形矩阵中包含的值的总和。当我们这样做的时候，我们可以同时检查grid[a.y][a.x]中的角色，一旦遇到不等于EMPTY_SPACE的角色(即，‘.’)就终止它。如果在遍历点a的末端等于点b，我们将把我们获得的和存储在cost矩阵中；否则，我们已经确定a和b之间没有邻接，这种情况下我们返回UNKNOWN。我们可以使用GetCost()函数来实现，该函数使用两个整数start和end作为参数。分别代表a和b的索引，返回一个整数:

int GetCost(int start, int end)
{
    Point a = houses[start];
    Point b = houses[end];
    // The values by which the coordinates change on each iteration
    int x_dir = 0;
    int y_dir = 0;
    if(a.x != b.x)
    {
        x_dir = (a.x < b.x) ? 1 : -1;
    }
    if(a.y != b.y)
    {
        y_dir = (a.y < b.y) ? 1 : -1;
    }
    int cost = 0;

    do
    {
        a.x += x_dir;
        a.y += y_dir;
        cost += terrain[a.y][a.x];
    }
    while(grid[a.y][a.x] == '.');
    return (a != b) ? UNKNOWN : res;
}

最后一行要求我们在Point结构中定义operator !=:

struct Point
{
    ......
    bool operator !=(const Point &other) const { return x != other.x || y != other.y; }
}

Now, let's create the following GetAdjacencies() function:

void GetAdjacencies()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(DirectLine(houses[i], houses[j])
            {
                cost[i][j] = cost[j][i] = GetCost(i, j);
            }
        }
    }
}

第三步:寻找节点间的最短距离

问题是，两栋房子应该通过一条道路连接起来，这条道路可以最大限度地降低到达出口点的成本。对于这个实现，我们将使用弗洛伊德-沃肖尔算法。让我们回到我们的代码:

让我们定义一个函数GetShortestPaths()，它将处理弗洛伊德-沃肖尔的实现以及路径的重建。为了处理后一种情况，我们将维护一个名为next的 N x N 整数矩阵，该矩阵将存储从节点a和b到最短路径上的下一点的索引。最初，它的值将被设置为图中现有的边:

void GetShortestPaths()
{
    vector<vector<int>> dist(N, vector<int>(N, UNKNOWN));
    vector<vector<int>> next(N, vector<int>(N, UNKNOWN));
for(int i = 0; i < N; i++)
{
    for(int j = 0; j < N; j++)
    {
        dist[i][j] = cost[i][j]
        if(dist[i][j] != UNKNOWN)
        {
            next[i][j] = j;
        }
    }
    dist[i][j] = 0;
    next[i][i] = i;
}
...
}

We will then perform the standard implementation of Floyd-Warshall, with one additional line in the innermost loop setting next[start][end] to next[start][mid] every time we find a shorter distance between start and end:

for(int mid = 0; mid < N; mid++)
{
    for(int start = 0; start < N; start++)
    {
        for(int end = 0; end < N; end++)
        {
            if(dist[start][end] > dist[start][mid] + dist[mid][end])
            {
                dist[start][end] = dist[start][mid] + dist[mid][end];
                next[start][end] = next[start][mid];
            }
        }
    }
}

第四步:重构路径

利用我们在next矩阵中获得的数据，我们可以以类似于 LCS 或 0-1 背包问题的重建方法的方式容易地重建每条路径上的点。为此，我们将定义另一个函数GetPath()，它有三个参数，两个整数start和end，以及对next矩阵的引用，并返回一个包含路径节点索引的整数向量:

vector<int> GetPath(int start, int end, vector<vector<int>> &next)
{
    vector<int> path = { start };
    do
    {
        start = next[start][end];
        path.push_back(start);
    }
    while(next[start][end] != end);
    return path;
}

Returning to GetShortestPaths(), we will now add a loop underneath our implementation of Floyd-Warshall that calls GetPath() and then draws lines in the grid corresponding to each pair of points in the path:

for(int i = 0; i < N; i++)
{
    auto path = GetPath(i, N – 1, next);

    int curr = i;
    for(auto neighbor : path)
    {
        DrawPath(curr, neighbor);
        curr = neighbor;
    }
}

第五步:重绘网格

现在，我们必须在网格中绘制道路。我们将在另一个函数DrawPath()中执行此操作，该函数具有start和end参数:

void DrawPath(int start, int end)
{
    Point a = houses[start];
    Point b = houses[end];
    int x_dir = 0;
    int y_dir = 0;
    if(a.x != b.x)
    {
        x_dir = (a.x < b.x) 1 : -1;
    }
    if(a.y != b.y)
    {
        y_dir = (a.y < b.y) 1 : -1;
    }

    ……
}

我们需要根据每条道路的方向选择正确的字符。为此，我们将定义一个函数GetDirection()，该函数返回一个整数，该整数对应于我们在开始定义的roads字符串(“-|/\”:

int GetDirection(int x_dir, int y_dir)
{
    if(y_dir == 0) return 0;
    if(x_dir == 0) return 1;
    if(x_dir == -1)
    {
        return (y_dir == 1) ? 2 : 3;
    }
    return (y_dir == 1) ? 3 : 2;
}
void DrawPath(int start, int end)
{
    ……
    int direction = GetDirection(x_dir, y_dir);
    char mark = roads[direction];
        ……
}

中的一个索引

我们现在可以执行从a到b的线性遍历，如果网格中的每个单元格的值为EMPTY_SPACE，则将它设置为mark。否则，我们必须检查单元格中的字符是否是不同方向的道路字符，在这种情况下，我们将其设置为+ :

```cpp
do
{
    a.x += x_dir;
    a.y += y_dir;

    if(grid[a.y][a.x] == EMPTY_SPACE)
    {
        grid[a.y][a.x] = mark;
    }
    else if(!isalpha(grid[a.y][a.x]))
    {
            // If two roads of differing orientations intersect, replace symbol with '+'
            grid[a.y][a.x] = (mark != grid[a.y][a.x]) ? '+' : mark;
    }
}
while(a != b);
```

剩下的就是在main()中调用我们的函数并打印输出:

```cpp
int main()
{
        Input();
        BuildGraph();
        GetShortestPaths();

        for(auto it : grid)
        {
            cout << it << endl;
        }
        return 0;
}
```

Files

10.md

Latest commit

History