从七桥问题开始：全面介绍图论及其应用

bool HasWasher(AirbnbHome* h)
{
  return h->amenities[2];
}

const int KITCHEN = 0;
const int HEATING = 1;
const int WASHER = 2;
//...
bool HasWasher(AirbnbHome* h)
{
  return (h != nullptr) && h->amenities[WASHER];
}

bool HasWasherAndKitchen(AirbnbHome* h)
{
  return (h != nullptr) && h->amenities[WASHER] && h->amenities[KITCHEN];
}

bool HasAllAmenities(AirbnbHome* h, const std::vector& amenities)
{
  bool has = (h != nullptr);
  for (const auto a : amenities) {
    has &= h->amenities[a];
  }
  return has;
}

// Note the comments
struct AirbnbHome
{
  wstring name; // 200 bytes
  uint price; // 4 bytes
  uchar rating; // 1 byte
  uint rating_count; // 4 bytes
  vector photos; // 100 bytes
  string host_id; // 20 bytes
  uchar adults_number; // 1 byte
  uchar children_number; // 1 byte
  uchar infants_number; // 1 byte
  bitset<3> home_type; // 4 bytes
  uchar beds_number; // 1 byte
  uchar bedrooms_number; // 1 byte
  uchar bathrooms_number; // 1 byte
  bitset<21> accessibility; // 4 bytes
  bool superhost; // 1 byte
  bitset<20> amenities; // 4 bytes
  bitset<6> facilities; // 4 bytes
  bitset<34> property_types; // 8 bytes
  bitset<32> host_languages; // 4 bytes, correct me if I'm wrong
  bitset<3> house_rules; // 4 bytes
  ushort country_code; // 2 bytes
  string city; // 50 bytes
};

struct NTreeNode
{
  T value;
  vector children;
};

// almost pseudocode
class NTree
{
public:
  void Insert(const T&);
  void Remove(const T&);
  // lines of omitted code
private:
  NTreeNode* root_;
};

这是图吗？我认为，是的。但这幅图与前面的 N-ary 相同，只不过稍微旋转了一下。只要你看到一棵树，无论它是苹果树、柠檬树，还是二叉搜索树，你都可以确定它也是一张图。因此，通过设计图节点（图节点）结构，我们能够提出同样的结构：

struct GraphNode
{
  T value;
  vector adjacent_nodes;
};

如果图中任意两点都是连通的，那么该图被称作连通图。

class ConnectedGraph
{
public:
  // API

private:
  GraphNode* root_;
};

class DisconnectedGraphOrJustAGraph
{
public:
  // API

private:
  std::vector all_roots_;
};

// A representation of a graph with both vertex and edge tables
// Vertex table is a hashtable of edges (mapped by label)
// Edge table is a structure with 4 fields
// VELO = Vertex Edge Label Only (e.g. no vertex payloads)

class ConnectedVELOGraph {
public:
    struct Edge {
        Edge(const std::string& f, const std::string& t)
            : from(f)
            , to(t)
            , used(false)
            , next(nullptr)
        {}
        std::string ToString() {
            return (from + " - " + to + " [used:" + (used ? "true" : "false") + "]");
        }

        std::string from;
        std::string to;
        bool used;
        Edge* next;
    };

    ConnectedVELOGraph() {}
    ~ConnectedVELOGraph() {
        vertices_.clear();
        for (std::size_t ix = 0; ix < edges_.size(); ++ix) {
            delete edges_[ix];
        }
    }

public:
    void InsertEdge(const std::string& from, const std::string& to) {
        Edge* e = new Edge(from, to);
        InsertVertexEdge_(from, e);
        InsertVertexEdge_(to, e);
        edges_.push_back(e);
    }

public:
    void Print() {
        for (auto elem : edges_) {
            std::cout << elem->ToString() << std::endl;
        }
    }

    std::vector Trace(const std::string& v) {
        std::vector path;
        Edge* e = vertices_[v];
        while (e != nullptr) {
            if (e->used) {
                e = e->next;
            } else {
                e->used = true;
                path.push_back(e->from + ":-:" + e->to);
                e = vertices_[e->to];
            }
        }
        return path;
    }

private:
    void InsertVertexEdge_(const std::string& label, Edge* e) {
        if (vertices_.count(label) == 0) {
            vertices_[label] = e;
        } else {
            vertices_[label]->next = e;
        }
    }

private:
    std::unordered_map vertices_;
    std::vector edges_;
};

// 'author' represents the User object, at this point we are interested only in author.id
//
// 'tw' is a Tweet object, at this point we are interested only in 'tw.id' 

void DeliverATweet(User* author, Tweet* tw)
{
  // we assume that 'tw' object is already stored in a database

  // 1. Get the list of user's followers (author of the tweet)
  vector user_followers = GetUserFollowers(author->id);

  // 2. insert tweet into each timeline
  for (auto follower : user_followers) {
    InsertTweetIntoUserTimeline(follower->id, tw->id);
  }
}

// Warning: a bunch of pseudocode ahead

void RangeInsertIntoTimelines(vector user_ids, long tweet_id)
{
  for (auto id : user_ids) {
    InsertIntoUserTimeline(id, tweet_id);
  }
}

void DeliverATweet(User* author, Tweet* tw)
{
  // we assume that 'tw' object is already stored in a database

  // 1. Get the list of user's (tweet author's) followers's ids
  vector user_followers = GetUserFollowers(author->id);

  // 2. Insert tweet into each timeline in parallel
  const int CHUNK_SIZE = 4000; // saw this somewhere
  for (each CHUNK_SIZE elements in user_followers) {
    Thread t = ThreadPool.GetAvailableThread(); // somehow
    t.Run(RangeInsertIntoTimelines, current_chunk, tw->id);
  }
}

house_type: "entire_place",
adults_number: 2,
price_range_start: 56,
price_range_end: 80,
beds_number: 2,
amenities: ["tv", "wifi", "laptop friendly workspace"],
facilities: ["gym"]

• Coloring

• Hopcroft–Karp

• Hungarian

• Prüfer coding

• Tarjan's off-line least common ancestors

• Topological sort

给定一个 Airbnb 房源（H）的偶图和过滤器（F），其中 H 的每个节点可以多于 F 的一个相邻节点（共享一个公共边）。寻找 H 的由节点构成的子集，该子集和 F 的子集的节点相邻。

// struct ListNode {
//   ListNode* next;
//   T item;
// };

void TraverseRecursive(ListNode* node) // starting node, most commonly the list 'head'
{
  if (!node) return; // stop
  std::cout << node->item;
  TraverseRecursive(node->next); // recursive call
}

void TraverseIterative(ListNode* node)
{
  while (node) {
    std::cout << node->item;
    node = node->next;
  }
}

• 输出节点值，然后到达左节点，再到达右节点。

• 到达左节点，然后输出节点值，再到达右节点。

• 到达左节点，然后到达右节点，再输出节点值。

// struct TreeNode {
//   T item;
//   TreeNode* left;
//   TreeNode* right;
// }

// you cann pass a callback function to do whatever you want to do with the node's value
// in this particular example we are just printing its value.

// node is the "starting point", basically the first call is done with the "root" node
void PreOrderTraverse(TreeNode* node)
{
  if (!node) return; // stop
  std::cout << node->item;
  PreOrderTraverse(node->left); // do the same for the left sub-tree
  PreOrderTraverse(node->right); // do the same for the right sub-tree
}

void InOrderTraverse(TreeNode* node)
{
  if (!node) return; // stop
  InOrderTraverse(node->left);
  std::cout << node->item;
  InOrderTraverse(node->right);
}

void PostOrderTraverse(TreeNode* node)
{
  if (!node) return; // stop
  PostOrderTraverse(node->left);
  PostOrderTraverse(node->right);
  std::cout << node->item;
}

// Cached representation of an Item
// Full Item object (with title, description, comments etc.)
// could be fetched from the database
struct Item
{
  // ID_TYPE is the type of Item's unique id, might be an integer, or a string
  ID_TYPE id;
  int rating;
};

// this is a pseudocode, that's why I didn't bother with "const&"'s and "std::"'s
// though it could have look better, forgive me C++ fellows

vector GetItemsByKeywordInSortedOrder(string keyword)
{
  // assuming IndexTable is a big hashtable mapping keywords to Item BSTs
  BST items = IndexTable[keyword];

  // suppose BST has a function InOrderProduceVector(), which creates a vector and 
  // inserts into it items fetched via in-order traversing the tree
  vector sorted_result = items.InOrderProduceVector();
  return sorted_result;
}

template 
class BST
{
public:
  // other code ...
  vector InOrderProduceVector()
  {
    vector result;
    result.reserve(1000); // magic number, reserving a space to avoid reallocation on inserts
    InOrderProduceVectorHelper_(root_, result); // passing vector by reference
    return result;
  }

protected:
  // takes a reference to vector
  void InOrderProduceVectorHelper_(BSTNode* node, vector& destination)
  {
    if (!node) return;
    InOrderProduceVectorHelper_(node->left, destination);
    destination.push_back(node->item);
    InOrderProduceVectorHelper_(node->right, destination);
  }

private:
  BSTNode* root_;
};

// Reminder: this is pseudocode, no bother with "const&", "std::" or others
// forgive me C++ fellows

template 
class BST
{
public:
  // other code ...

  vector ReverseInOrderProduceVector(int offset, int limit)
  {
    vector result;
    result.reserve(limit);
    // passing result vector by reference
    // and passing offset and limit
    ReverseInOrderProduceVectorHelper_(root_, result, offset, limit);
    return result;
  }

protected:
  // takes a reference to vector
  // skips 'offset' nodes and inserts up to 'limit' nodes
  void ReverseInOrderProduceVectorHelper_(BSTNode* node, vector& destination, int offset, int limit)
  {
    if (!node) return;
    if (limit == 0) return;
    --offset; // skipping current element
    ReverseInOrderProduceVectorHelper_(node->right, destination, offset, limit);
    if (offset <= 0) { // if skipped enough, insert
      destination.push_back(node->value);
      --limit; // keep the count of insertions
    }
    ReverseInOrderProduceVectorHelper_(node->left, destination, offset, limit);
  }

private:
  BSTNode* root_;
};

// ... other possibly useful code

// this is a pseudocode, that's why I didn't bother with "const&"'s and "std::"'s
// though it could have look better, forgive me C++ fellows

vector GetItemsByKeywordInSortedOrder(string keyword, offset, limit) // pagination using offset and limit
{
  // assuming IndexTable is a big hashtable mapping keywords to Item BSTs
  BST items = IndexTable[keyword];

  // suppose BST has a function InOrderProduceVector(), which creates a vector and 
  // inserts into it items fetched via reverse in-order traversing the tree
  // to get items in descending order (starting from the highest rated item)
  vector sorted_result = items.ReverseInOrderProduceVector(offset, limit);
  return sorted_result;
}

• 深度优先搜索——更多动作，更少思考。

• 广度优先搜索——在进一步行动之前先仔细观察四周。

// Assuming graph is connected
// and a graph node is defined by this structure
// struct GraphNode {
//   T item;
//   vector children;
// }

// WARNING: untested code
void BreadthFirstSearch(GraphNode* node) // start node
{
  if (!node) return;
  queue q;
  q.push(node);
  while (!q.empty()) {
    GraphNode* cur = q.front(); // doesn't pop
    q.pop();
    for (auto child : cur->children) {
      q.push(child);
    }

    // do what you want with current node
    cout << cur->item;
  }
}

☞数学传奇——代数几何的白马王子肖刚

☞吴军：数学，为人生之题解出漂亮的答案

☞82岁江泽民在2008年发表论文指出：发展智能化，机器学习将有所作为……

☞机器学习中需要了解的 5 种采样方法

☞北大读博手记：怎样完成自己的博士生涯？非常具有指导性！

☞图论的各种基本算法

点赞

评论

收藏

分享

手机扫一扫分享

分享

举报

点赞

评论

收藏

分享

手机扫一扫分享

分享

举报