程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23346 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?

黄申 2019-01-11
你好,我是黄申。
上一节,我们探讨了如何在树的结构里进行深度优先搜索。说到这里,有一个问题,不知道你有没有思考过,树既然是两维的,我们为什么一定要朝着纵向去进行深度优先搜索呢?是不是也可以朝着横向来进行搜索呢?今天我们就来看另一种搜索机制,广度优先搜索。

社交网络中的好友问题

LinkedIn、Facebook、微信、QQ 这些社交网络平台都有大量的用户。在这些社交网络中,非常重要的一部分就是人与人之间的“好友”关系。
在数学里,为了表示这种好友关系,我们通常使用图中的结点来表示一个人,而用图中的边来表示人和人之间的相识关系,那么社交网络就可以用图论来表示。而“相识关系”又可以分为单向和双向。
单向表示,两个人 a 和 b,a 认识 b,但是 b 不认识 a。如果是单向关系,我们就需要使用有向边来区分是 a 认识 b,还是 b 认识 a。如果是双向关系,双方相互认识,因此直接用无向边就够了。在今天的内容里,我们假设相识关系都是双向的,所以我们今天讨论的都是无向图。
从上面的例图可以看出,人与人之间的相识关系,可以有多条路径。比如,张三可以直接连接赵六,也可以通过王五来连接赵六。比较这两条通路,最短的通路长度是 1,因此张三和赵六是一度好友。也就是说,这里我用两人之间最短通路的长度,来定义他们是几度好友。照此定义,在之前的社交关系示意图中,张三、王五和赵六互为一度好友,而李四和赵六、王五为二度好友。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(9)

  • qinggeouye
    # 思考题 python
    import getpass
    import os
    import queue


    def bfs_dir(path):
        """
        广度优先搜索:在给定路径下,搜索文件或子目录,
        子目录需要进一步搜索其下的文件和子目录,直到没有更多的子目录
        :param path: 给定目录的路径
        :return:
        """
        # 给出的路径是否是一个目录
        if not os.path.isdir(path):
            return
        que = queue.Queue()
        visited = set()
        for p in os.listdir(path):
            bfs_path = path + os.sep + p
            if os.path.isdir(bfs_path):
                que.put(bfs_path)
                visited.add(bfs_path)
                print('文件夹\t', bfs_path)
            else:
                print('文件\t', bfs_path)
        while not que.empty():
            cur_path = que.get()
            if len(os.listdir(cur_path)) == 0:
                continue
            for p in os.listdir(cur_path):
                bfs_path = cur_path + os.sep + p
                if bfs_path in visited:
                    continue
                if os.path.isdir(bfs_path):
                    que.put(bfs_path)
                    visited.add(bfs_path)
                    print("文件夹\t", bfs_path)
                else:
                    print("文件\t", bfs_path)


    if __name__ == "__main__":
        dir_path = ''
        user = getpass.getuser() # 计算机当前登陆用户
        if os.name == "posix": # Unix 或 OS X 操作系统
            dir_path = '/Users/' + user + '/Desktop/GeekTime/MathematicProgrammer'
        elif os.name == "nt": # Win 操作系统
            dir_path = '\\Users\\' + user + '\\Desktop\\GeekTime\\MathematicProgrammer'
        bfs_dir(dir_path)
    2019-02-24
    3
  • Joe
    C++实现DFS显示ubuntu指定目录下所有的文件,请老师指点。
    #include <dirent.h>
    #include <stdlib.h>
    #include <string.h>
    #include <unistd.h>
    #include <iostream>
    #include <regex>
    #include <stack>
    using namespace std;

    class FileSearch {
      private:
      stack<string> path; // 路径栈

      public:
      /**
       * Detail: DFS显示ubuntu指定目录下文件
       * basePath- 文件路径
       * return: null
       */
      void DfsFile(char *basePath) {
        DIR *dir;
        struct dirent *ptr;
        char base[1000];
        char temp[1000];
        // 路径入栈
        path.push(basePath);
        // 遍历开始
        while (!path.empty()) {
          // 打开当前目录
          strcpy(temp, path.top().c_str());
          path.pop();
          cout << "Current path: " << temp << endl;
          if ((dir = opendir(temp)) == NULL) {
            perror("Open dir error, please input the right path");
            exit(1);
          }
          // 显示当前路径下的文件
          while ((ptr = readdir(dir)) != NULL) {
            // 忽略隐藏文件和路径: .and..
            if (regex_match(ptr->d_name, regex("\\.(.*)"))) {
              continue;
            }
            if (ptr->d_type == 8) {
              // A regular file
              //cout << "file: " << basePath << "/" << ptr->d_name << endl;
              cout << ptr->d_name << endl;
            } else if (ptr->d_type == 4) {
              // 检测为文件夹
              memset(base, '\0', sizeof(base));
              strcpy(base, temp);
              strcat(base, "/");
              strcat(base, ptr->d_name);
              path.push(base);
              continue;
            }
          }
        }
        // 关闭文件
        closedir(dir);
      }
    };
    int main(void) {
      FileSearch test;
      // 需要遍历的文件夹目录
      char basePath[] = {"/home/joe/Desktop/leetcode"};
      test.DfsFile(basePath);
      return 0;
    }
    // 大致输出结果为:
    Current path: /home/joe/Desktop/leetcode
    leetcodePractice.cpp
    a.out
    README.md
    Current path: /home/joe/Desktop/leetcode/math_fundamental_algorithms
    recursion.cpp
    tree_depth_first_search.cpp
    recursion_integer.cpp
    permutation.cpp
    dynamic_programming.md
    iteration_way.cpp
    tree_breadth_first_search.md
    a.out
    tree_breadth_first_search.cpp
    math_induction.cpp
    byte_operation.cpp
    ......

    作者回复: 注意到了隐藏路径和文件的处理,很棒

    2019-01-20
    2
  • strentchRise
    自己代码功力不行,尽力写一个python版本的

    class Node:
        def __init__(self, number):
            self.num = number
            self.nodes = []

        def setNode(self, num):
            if(self.nodes.__contains__(num) == False):
                node = Node(num)
                self.nodes.append(node)
                return node
            else:
                return None

        def setNodeUnder(self, num, base):
            if (self.num == num):
                return self.setNode(num)

            baseNode = self.get(base, self.nodes)
            if baseNode == None:
                return None
            else:
                return baseNode.setNode(num)

        def get(self, num, nodes=None):
            if(self.nodes == None or len(nodes) == 0):
                return None
            else:
                someNodes = []
                for node in nodes:
                    if node.num == num:
                        return node
                    for n in node.nodes:
                        someNodes.append(n)
                return self.get(num, someNodes)
        
        def search(self):
            print(self.num)
            self.printNodes(self.nodes)

        def printNodes(self, nodes=None):
            if nodes == None or len(nodes) == 0:
                return
            else:
                someNodes = []
                for node in nodes:
                    print(node.num)
                    for n in node.nodes:
                        someNodes.append(n)
                return self.printNodes(someNodes)

    root = Node(110)
    root.setNode(123)
    root.setNode(879)
    root.setNode(945)
    root.setNode(131)
    root.setNodeUnder(162, 123)
    root.setNodeUnder(587, 123)
    root.setNodeUnder(580, 945)
    root.setNodeUnder(762, 945)
    root.setNodeUnder(906, 131)
    root.setNodeUnder(681, 587)

    root.search()

    output:
    110
    123
    879
    945
    131
    162
    587
    580
    762
    906
    681
    finish...

    作者回复: 很好的还原了原文的示例👍

    2019-01-11
    1
  • Paul Shan
    树的广度优先是从根开始,从上到下,按层遍历,每一层,按照从左到右遍历,如果把结果排出来,也就是按两个维度排序,层次是第一优先级,左右是第二优先级。实现中用队列。

    二叉树的深度遍历有两个顺序,一个顺序是节点被发现的顺序,另外一个是节点完成的顺序。被发现的顺序和树的前序遍历一致,中左右递归进行。完成的顺序和树的后序遍历一致,左右中递归进行。实现中用栈。
    2019-08-23
  • 恬毅
    package package13;

    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;

    public class File {
    public String name;
    public HashSet<File> children;
    public String parent;

    public String getPath() {
    if (name == null)
    return null;
    if (parent == null) {
    return this.name;
    }
    return this.parent.concat("/").concat(this.name);
    }

    public File(String name, String parent) {
    this.name = name;
    this.parent = parent;
    this.children = new HashSet<File>();
    }

    public static void addFile(File file, String path) {
    String[] arr = path.split("/");
    boolean exist = false;
    File newFile = null;
    for (File files : file.children) {
    if (files.name.equals(arr[0])) {
    exist = true;
    newFile = files;
    }
    }
    if (!exist) {
    newFile = new File(arr[0], file.getPath());
    file.children.add(newFile);
    }
    if (arr.length > 1) {
    addFile(newFile, path.substring(path.indexOf("/") + 1));
    }
    }

    public static void guangdu(File file) {
    Queue<File> queue = new LinkedList<File>();
    queue.offer(file);
    while(!queue.isEmpty()) {
    File iterator = queue.poll();
    System.out.println(iterator.getPath());
    for (File child : iterator.children) {
    queue.offer(child);
    }
    }
    }

    public static void shendu(File file) {
    Stack<File> stack = new Stack<File>();
    stack.push(file);
    while(!stack.isEmpty()) {
    File iterator = stack.pop();
    System.out.println(iterator.getPath());
    for (File child : iterator.children) {
    stack.push(child);
    }
    }
    }

    public static void main(String[] args) {
    File file = new File(null, null);
    addFile(file, "d:/a/b/c");
    addFile(file, "d:/a/b/c");
    addFile(file, "d:/a/b/d");
    addFile(file, "d:/a/b2/d");
    addFile(file, "d:/a/b3/d");
    addFile(file, "d:/b/b3/d");
    // shendu(file);
    guangdu(file);
    }
    }
    2019-08-22
  • 蜉蝣
    老师你好。请问这句话是什么意思:“这时,我们就需要换一个还没有被访问过的起始点,继续深度优先遍历另一个子图。” 为什么换了一个起始点之后就要用深度优先遍历呢?

    作者回复: 这里是一个笔误,应该是继续“广度”优先。我稍后改一下

    2019-01-28
  • 菩提
    我好好检查了一下我的代码逻辑,您的逻辑是正确的。

    我这边visited集合没有把user_id加入,导致的问题。

    控制台的输出日志。我查询的是user_id是 0, 而控制台打印了一行记录是 2度好友:0 。 出现这个打印的原因是遍历0的好友。该好友的friends包含了0,在for循环中算了user_id=0的情况。

    谢谢老师指正!

    作者回复: 找到问题就好👍

    2019-01-16
  • 菩提
    广度优先搜索那块有2个小瑕疵,您看一下。
    1. 防止数组越界的异常,user_id 等于数组长度也会越界。
    2.遍历子节点的时候,如果子节点friends中存在需要查询的user_id,则出现错误的打印输出。如果是查询的user_id应该continue。

    控制台打印
    0:[3]:0
    1:[3]:0
    2:[3]:0
    3:[0, 1, 2, 4]:0
    4:[3]:0
    1 度好友:3
    2 度好友:0
    2 度好友:1
    2 度好友:2
    2 度好友:4

    代码如下,
    public static Node[] init(int user_num, int relation_num) {
    Random rand = new Random();

    Node[] user_nodes = new Node[user_num];

    // 生成所有表示用户的节点
    for (int i = 0; i < user_num; i++) {
    user_nodes[i] = new Node(i);
    }

    // 生成所有表示好友关系的边
    for (int i = 0; i < relation_num; i++) {
    int friend_a_id = rand.nextInt(user_num);
    int friend_b_id = rand.nextInt(user_num);
    if (friend_a_id == friend_b_id)
    continue;
    Node friend_a = user_nodes[friend_a_id];
    Node friend_b = user_nodes[friend_b_id];
    friend_a.friends.add(friend_b_id);
    friend_b.friends.add(friend_a_id);
    }

    return user_nodes;
    }

    public static void bfs(Node[] user_nodes, int user_id) {
    // 防止数组越界异常
    if (user_id >= user_nodes.length)
    return;

    // 用于广度优先搜索的队列
    Queue<Integer> queue = new LinkedList<>();

    // 放入初始节点
    queue.offer(user_id);

    // 存放已经被访问过的节点,防止回路
    HashSet<Integer> visited = new HashSet<>();

    while (!queue.isEmpty()) {
    // 取出队列头部的第一个节点
    int current_user_id = queue.poll();
    if (user_nodes[current_user_id] == null)
    continue;

    // 遍历刚刚拿到的这个节点的所有直接连接节点,并加入队列尾部
    for (int friend_id : user_nodes[current_user_id].friends) {
    if (user_nodes[current_user_id] == null)
    continue;
    if (visited.contains(friend_id))
    continue;
    queue.offer(friend_id);
    // 记录已经访问过的节点
    visited.add(friend_id);
    // 好友度数是当前节点的好友度数再加1
    user_nodes[friend_id].degree = user_nodes[current_user_id].degree + 1;
    System.out.println(String.format("\t%d 度好友:%d", user_nodes[friend_id].degree, friend_id));
    }
    }
    }

    public static void main(String[] args) {
    Node[] user_nodes = init(5, 8);
    for (Node d : user_nodes) {
    System.out.println(d.user_id + ":" + d.friends + ":" + d.degree);
    }
    bfs(user_nodes, 0);
    }

    作者回复: 第一点是很好的发现,我稍后加一下。
    第二点没有看太明白,能否补充说明一下?

    2019-01-15
  • Being
    使用C++的双端队列deque实现的BFS和DFS
    namespace FilePathOperator {
    struct St_FilePathNode;
    typedef std::set<St_FilePathNode*> SetterFilePathNode;
    typedef void(*FilPathOperator)(const St_FilePathNode& rStFilePathNode);
    typedef struct St_FilePathNode {
    int m_nLevel;
    std::string m_strFilePath;
    SetterFilePathNode m_setChildernPathNodes;
    }StFilePathNode;
    };
    void FilePathOperator::BFSFilePathNodes(StFilePathNode * pRoot, FilPathOperator nodeOperator, int nMaxLevel)
    {
    if (NULL == pRoot)
    return;

    std::deque<StFilePathNode*> queNode;
    queNode.push_front(pRoot);

    pRoot->m_nLevel = 0; // Root Level is first one

    while (!queNode.empty())
    {
    StFilePathNode* pNode = queNode.back();
    queNode.pop_back();
    if (NULL == pNode) continue;

    int nNodeLevel = pNode->m_nLevel;
    nodeOperator(*pNode);

    if (nNodeLevel + 1 > nMaxLevel) continue; // childern beyond MaxLevel

    SetterFilePathNode::iterator ChildItr = pNode->m_setChildernPathNodes.begin();
    for (; ChildItr != pNode->m_setChildernPathNodes.end(); ChildItr++) {
    if (NULL == *ChildItr)
    continue;

    (*ChildItr)->m_nLevel = nNodeLevel + 1;
    queNode.push_front(*ChildItr);
    }
    }
    }
    void FilePathOperator::DFSFilePathNodes(StFilePathNode * pRoot, FilPathOperator nodeOperator, int nMaxLevel)
    {
    if (NULL == pRoot)
    return;

    std::deque<StFilePathNode*> deqNode;
    deqNode.push_front(pRoot);

    pRoot->m_nLevel = 0; // Root Level is first one

    while (!deqNode.empty())
    {
    StFilePathNode* pNode = deqNode.front();
    deqNode.pop_front();
    if (NULL == pNode) continue;

    int nNodeLevel = pNode->m_nLevel;
    nodeOperator(*pNode);

    if (nNodeLevel + 1 > nMaxLevel) continue; // childern beyond MaxLevel

    SetterFilePathNode::iterator ChildItr = pNode->m_setChildernPathNodes.cbegin();
    for (; ChildItr != pNode->m_setChildernPathNodes.cend(); ChildItr++) {
    if (NULL == *ChildItr)
    continue;

    (*ChildItr)->m_nLevel = nNodeLevel + 1;
    deqNode.push_front(*ChildItr);
    }
    }
    }
    (其他的Create、Destroy、Print就暂时不贴出来了)

    作者回复: Deque确实是个好东西,只是名字有时让人联想不到stack :)

    2019-01-11
收起评论
9
返回
顶部