【第二十天 - Graph 介绍】

Q1. Graph 是什麽

  • Graph 定义:一个 graph 由 数个点( vertex )与数个边( edge ) 组成
  • 图形的表示有两种方法:相邻矩阵 (Adjacency Matrix) 、相邻串列 (Adjacency List)
    • 相邻矩阵 (Adjacency Matrix) 使用二维阵列实作的优点:

      • 适合储存 edge 很多的图形,若 vertex 很多但是 edge 很少,容易造成稀疏矩阵,浪费记忆体空间
      • 适合需要经常判断 edge 是否存在的问题
        https://ithelp.ithome.com.tw/upload/images/20210920/20140592t3kjAQtfZx.png
    • 相邻串列 (Adjacency List) 使用 Linked list 实作的优点:

      • 适合储存 vertex 很多,但是 edge 很少的图形
      • 能够弹性使用记忆体
      # 与 1 相邻的点有 2, 5
      Adj[1] = [2, 5]
      # 与 2 相邻的点有 1, 3, 4, 5
      Adj[2] = [1, 3, 4, 5]
      Adj[3] = [2, 4]
      Adj[4] = [2, 3, 5]
      Adj[5] = [1, 2, 4]
      

      https://ithelp.ithome.com.tw/upload/images/20210920/20140592lfNh298X5w.png

图片来源:https://kopu.chat/2017/09/22/实作graph与dfs、bfs走访/

Q2. 学会 Graph 概念可以做什麽 ?

  • 生活中的 Graph 问题
    • 例如 路线规划问题
  • 图论着名题目,一笔画问题

参考资料:https://zh.wikipedia.org/wiki/图论

Lab. 明天要解的题目:997. Find the Town Judge

  • 题目连结:https://leetcode.com/problems/find-the-town-judge/

  • 题目叙述:

    • 一个小镇中有编号 1 ~ n 的人,谣传这些人之中,有一个人是秘密的小镇法官。
    • 如果真的有法官,则法官会满足这几个条件:
      • 这位法官不会相信任何人。
      • 法官以外的所有人,都相信法官。
      • 整个小镇只会恰有一个人满足这些条件。
    • 给定镇民之间的信任关系,要找出法官是谁。
      https://ithelp.ithome.com.tw/upload/images/20210920/20140592BFCJT7cZZ2.png
  • 测资的 Input/Output

    • input 为 小镇上有 n 个人 与 纪录了信任关系的二维阵列 trust
    • output 需要回传谁是小镇的法官,若无则回传 -1
      https://ithelp.ithome.com.tw/upload/images/20210920/20140592Qd19FayoBz.png
  • 题目的条件

    • 小镇上的人有 1~1000人

    • 小镇上的 trust 长度为 1~10000 间

    • trust 的 column 数量为 2
      https://ithelp.ithome.com.tw/upload/images/20210920/201405922zyKTMazMq.png

    • trust 中的纪录不会重复

    • 镇民不会信任自己

    • trust 中的镇民一定在 1 ~ n 之间
      https://ithelp.ithome.com.tw/upload/images/20210920/20140592Ly6Aqond8L.png


<<:  selenium爬虫:使用xpath

>>:  Day-05 JavaScript阵列

8. STM32-PWM(上)

我手上的板子是L476RG,在当中一共有11个定时器: 其中分为基本、通用、高阶三种 基本定时器:T...

每个专案的程序码都该这样开始

(今天这篇文章好鸡肋阿!) 比起决定要不要使用最新观念、最新套件,以下几件事情务必要注意: 1.实作...

Swift纯Code之旅 Day25. 「各个TableViewHeader下的Cell显示(2)」

前言 我们已经将第一个Section下的Cell设置完毕了,接下来马上来实作第二个Section的C...

DAY12 - 使用 angular fire 操作firebase

firebase sdk 是什麽 firebase sdk 是 firebase 官方推出和 fir...

DAY24-JAVA的抛出例外

昨天跟大家介绍trycatch-finally,今天就来跟大家说说抛出例外(throw)吧!!! 抛...