引子老王踏入万物互联的新世界还记得那位陪我们打穿了整个查找之王江湖的老王吗从二叉树到哈希表老王把怎么存数据、怎么找数据摸得门儿清。可这天他接了个新活儿却被难得抓耳挠腮我这回要做个’社交关系’的功能——比如有6个用户张三和李四是好友、李四和王五是好友、王五又和赵六是好友……他们的关系乱七八糟、纵横交错像一张网!这跟我以前见的’树’完全不一样啊!树是有’上下级’的——有根、有枝、有叶,规规矩矩。可这’好友关系’,谁跟谁都可能有联系,没大没小、没上没下,就是一张铺开的’关系网’!这种’网状’的东西,我该咋在电脑里存下来啊?总不能一句句写’张三和李四是好友、李四和王五是好友’吧?那查起来不得乱成一锅粥?老王这一脚踏进了数据结构里最广阔、也最迷人的新世界——图Graph。什么是图树有上下级的层级结构有根、有父子、有先后像家族族谱、像公司组织架构。图没有上下级的网状结构任何两个点之间都可能有联系像社交关系网、像城市地图、像地铁线路图。而老王的困惑——“这张乱糟糟的关系网到底怎么存进电脑”——正是研究图的第一个、也是最根本的问题。今天我们就来认识存储图的第一种、也是最直观的办法——邻接矩阵。老王搓搓手“网状的东西也能存还是个’矩阵’听着就高级快说说这’关系网’到底咋装进电脑”第一章先理清——图到底由什么组成要存图得先看清图是由哪些零件拼起来的。其实特别简单就两样东西一张图,就两种零件: ① 顶点(Vertex):图里的点,代表一个个体 → 比如:张三、李四、王五...这些人 ② 边(Edge):连接两个点的线,代表它们有联系 → 比如:张三——李四 这条线,代表他俩是好友我们把老王的6个用户画成一张图老王的社交关系图(6个人): 张三 ●────────● 李四 ╲ │ ╲ │ 赵六 ●──╲──● 王五 ╲ │ ╲ │ 钱七 ●──● 孙八 ● 顶点(一个人) ── 边(两人是好友)看清了图就是一堆点顶点 “连接它们的线边”。现在问题来了这一堆点和线画在纸上一目了然可电脑里没有画的概念它只认数字、只认表格。我们怎么把这张画翻译成电脑能存、能查的东西这就轮到邻接矩阵闪亮登场了。它的思路朴素得让人会心一笑——做一张关系表格把谁和谁有联系一格一格填进去第二章核心思想——做一张谁连谁的大表格邻接矩阵的想法特别像我们小时候填的同学关系表核心思想假设有 n 个顶点就画一张n 行 n 列的大表格。第 i 行、第 j 列那一格就用来回答一个问题——“第 i 个点和第 j 个点到底有没有连线”有连线是好友→ 这一格填1没连线不是好友→ 这一格填0。我们拿老王那6个人来填这张表。先给6个人编上号张三0、李四1、王五2、赵六3、钱七4、孙八5。假设他们的好友关系是张三(0) — 李四(1)李四(1) — 王五(2)王五(2) — 赵六(3)王五(2) — 孙八(5)钱七(4) — 孙八(5)那么这张邻接矩阵表格就填成这样张三 李四 王五 赵六 钱七 孙八 (0) (1) (2) (3) (4) (5) 张三(0) [ 0 1 0 0 0 0 ] ← 张三只和李四(1)是好友 李四(1) [ 1 0 1 0 0 0 ] ← 李四和张三(0)、王五(2)是好友 王五(2) [ 0 1 0 1 0 1 ] ← 王五和李四(1)、赵六(3)、孙八(5)是好友 赵六(3) [ 0 0 1 0 0 0 ] ← 赵六只和王五(2)是好友 钱七(4) [ 0 0 0 0 0 1 ] ← 钱七只和孙八(5)是好友 孙八(5) [ 0 0 1 0 1 0 ] ← 孙八和王五(2)、钱七(4)是好友怎么读这张表太简单了比如你想知道张三和王五是不是好友——找到张三那一行第0行、王五那一列第2列交叉那一格是0→不是好友再比如李四和王五是不是好友——第1行、第2列交叉格是1→是好友老王眼睛一亮“妙啊这不就是个’打勾表’嘛把谁和谁有没有联系全用0和1填进一张方格表里——一目了然”第三章邻接矩阵的两个小特点藏着大智慧老王盯着这张表看出了两个有趣的规律而这两个规律恰恰藏着邻接矩阵的门道。特点一沿对角线对称——因为好友是相互的老王发现咦?这张表怎么……沿着对角线对称啊?你看,第0行第1列是1,第1行第0列也是1!像照镜子一样!(0) (1) (2) (3) (4) (5) (0) [ 1 0 0 0 0 ] (1) [ 1 1 0 0 0 ] (2) [ 0 1 1 0 1 ] 沿着这条对角线, (3) [ 0 0 1 0 0 ] 上下完全对称! (4) [ 0 0 0 0 1 ] (5) [ 0 0 1 0 1 ]道理很简单因为好友关系是相互的——张三是李四的好友那李四必然也是张三的好友所以第0行第1列和第1行第0列记的是同一件事自然都是1。这种双向、相互的图叫无向图边没有方向。它的邻接矩阵必然沿对角线对称。但是如果关系是单向的呢比如微博的关注——张三关注了大V李四但李四不一定关注张三。这种单向的图叫有向图它的边带箭头张三→李四那么矩阵就不对称了第0行第1列是1张三关注李四但第1行第0列可能是0李四没关注张三。小智慧一看一眼邻接矩阵对不对称就能瞬间判断这是双向的无向图还是单向的有向图特点二对角线上全是0——自己和自己不算好友老王又发现“还有,这条对角线上,怎么全是0(我用标了)?”道理也简单对角线上的格子第0行第0列、第1行第1列……问的是自己和自己有没有连线。一般来说自己是不是自己的好友这种问题没意义所以通常填0。老王点点头“原来这张表里的每一处,都有讲究!对称不对称,看的是关系’单向还是双向’;对角线,管的是’自己和自己’。这小小的0和1,信息量不小啊!”第四章邻接矩阵的超能力与大软肋老王学会了填表又较起了真“那这张表,到底好不好用?有啥优点、又有啥毛病?”我们来盘盘邻接矩阵的超能力和大软肋。超能力查两点有没有连线快如闪电 这是邻接矩阵最大的王牌——想知道任意两个点A和B之间有没有边直接去查第A行第B列那一格就行一步到位这跟我们上一篇讲的哈希表的算位置异曲同工——直接定位到那一格O(1)瞬间出答案与图里有多少个点、多少条边毫无关系┌────────────────────────────────────────────────┐ │ 邻接矩阵的超能力: │ │ 问张三和王五是不是好友? │ │ → 直接看 第0行第2列 → 一步到位! ⚡ │ │ 不管图里有6个人还是600万人,查这一格,都是一瞬间! │ └────────────────────────────────────────────────┘大软肋太费空间尤其当关系稀疏时可老王转念一想就发现了大问题等等!我这表是 6×6,要存36个格子。可要是我有100万个用户呢?那这张表就是 100万 × 100万 ……这得存多少个格子啊?!老王这一惊正中要害┌────────────────────────────────────────────────┐ │ 邻接矩阵的大软肋:空间是点数的平方! │ │ │ │ n个顶点 → 表格大小 n × n 个格子! │ │ │ │ · 100个点 → 1万个格子 (还行) │ │ · 1万个点 → 1亿个格子 (吃力) │ │ · 100万个点 → 1万亿个格子 (彻底崩溃!) │ └────────────────────────────────────────────────┘更扎心的是现实中的社交网络每个人的好友通常就几百个可总用户却有几百万、几千万。这意味着——这张巨大的表格里绝大多数格子都是0不是好友你花了100万×100万的天价空间绝大部分却用来存0没关系——这就好比为了记录班里几对同桌却造了一张能记录全校每两人关系的巨型表格99.99%的格子都空着浪费到了极点这种点很多、但边很少的图专业上叫稀疏图。邻接矩阵在稀疏图面前浪费空间浪费得令人心痛。老王恍然也有点失落“我懂了。这张表’查关系’是真快,可它’胃口’也太大了——不管你俩到底是不是好友,它都先吭哧吭哧给你预留好一个格子!点一多、关系一稀疏,绝大多数格子全空着,白白浪费!”正是这个大软肋逼着人们发明了另一种更省空间的存图办法——邻接表这是下一篇的主角了。但这丝毫不影响邻接矩阵在稠密图、且要频繁查两点关系时的王者地位。第五章终极总结——邻接矩阵到底妙在哪、短在哪老王把邻接矩阵的特点浓缩成一张表贴在了图家族新开的那一页上┌────────────────┬──────────────────────────────────┐ │ 邻接矩阵 │ 说明 │ ├────────────────┼──────────────────────────────────┤ │ 核心思想 │ 做n×n表格,第i行j列填i和j连不连 │ │ 怎么填 │ 有边填1,无边填0 │ │ 无向图特点 │ 沿对角线对称(关系是相互的) │ │ 有向图特点 │ 不对称(关系是单向的) │ │ 超能力(优点) │ 查两点连不连一步到位,O(1)飞快! │ │ 大软肋(缺点) │ 占空间n²,稀疏图下浪费到崩溃 │ │ 最佳战场 │ 点不多、边很密(稠密图)、常查两点关系│ │ 一句话 │ 用一张方格表,记下谁和谁有联系! │ └────────────────┴──────────────────────────────────┘老王摸着这张表悟出了邻接矩阵的题眼也为踏入图的世界开了个好头我算是把这第一种存图法摸透了——它的思路朴素得可爱:无非是把’谁和谁有没有联系’,用0和1,一格一格填进一张大方格表里。它的好,是’查两点关系’快如闪电——伸手指到那一格,答案立现;它的赖,是’胃口’太大——n个点就要n²个格子,点一多、关系一稀疏,就浪费得让人心疼。说到底,它就是一种’用空间,换查询速度’的存法——舍得花地方,就换来查得快。值不值,得看你的图,到底是’人多关系密’,还是’人多关系疏’!尾声一张关系表格的智慧亦是人生的智慧老王这场踏入图世界的初探从乱糟糟的社交网怎么存的困惑出发看清了图就是点和边的本质学会了用一张方格表把谁连谁记下来也掂量清了它查得快、却费地方的得与失——终于为这趟全新的图之旅开了个漂亮的头。但当我们合上书会发现这张关系表格背后竟也舒展着几分耐人寻味的人生哲理。第一复杂的关系网也能用最朴素的方式去厘清。老王面对那张乱糟糟、纵横交错的社交网一开始手足无措可邻接矩阵告诉他——再复杂的关系也能拆解成最简单的一问一答“这两个到底连不连”一格一格地填乱网就成了清表。这何尝不是一种面对复杂的智慧生活与工作里我们也常被千头万绪、剪不断理还乱的复杂局面吓住——一个盘根错节的项目、一团纠缠不清的人际关系。可越是复杂越要学会把它’拆解成一个个最简单的小问题’一个一个去问、去答、去厘清。别被’整张网’的复杂吓退盯住’每两点之间连不连’的简单——化整为零、逐格填写再乱的网也能理出头绪。第二“关系是相互的”——你怎么对人那一格也怎么记着你。无向图的邻接矩阵沿对角线完美对称——因为你是我的好友和我是你的好友本就是同一件事会被同时记下。这是一个温暖的隐喻。人与人之间许多关系也是这样相互、对称的你真心待人那份真心会在对方心里留下同样的一格你冷漠相向那份冷漠也会被对称地记着。你付出的善意、你给予的信任、你投入的关怀最终都会在那张关系矩阵里对称地、如实地回到你身上。想要别人那一格填1先把自己这一格认真地填好。相互是关系最朴素的法则。第三“留有余地是慷慨但过度预留是浪费——凡事要讲究适配”。邻接矩阵的软肋在于它不管你俩到底连不连都先给每一对都预留好一个格子——在稀疏的世界里这份周全的预留反而成了巨大的浪费。这给我们一个微妙的提醒做足准备、留有余地固然是美德可一旦脱离了实际需求、为’几乎用不到’的可能性付出了高昂的代价‘周全’就异化成了’浪费’。为偶尔一次的聚会买下全套豪华餐具、为渺茫的可能性囤积大量物资、为极小概率的风险投入过度的精力……真正的智慧不是’凡事都备到极致’,而是看清自己’到底是稠密还是稀疏’——按真实的需求来,不多不少,恰到好处。适配才是最高级的周全。下次当你打开社交软件看到你和TA有3个共同好友你可能认识的人时请记得——在那看不见的深处或许就有一张关系表格般的邻接矩阵它把人与人之间纵横交错的联系化作一格格朴素的0与1对称地、清晰地记录着谁与谁曾经相连于是你轻轻一点它便能瞬间告诉你这茫茫人海里谁和谁原来早已有了交集。“邻接矩阵”就是这门关于化繁为简厘清关系、相互对称善待彼此、按需适配不滥预留的、朴素而深刻的智慧。它告诉我们再复杂的关系网也能拆成连不连的简单一问关系是相互的你怎么填那一格它就怎么记着你而真正的周全不是过度预留而是看清稀疏还是稠密、恰到好处地适配。它像一句朴素的箴言提醒着我们——别被整张网的复杂吓退盯住每两点连不连的简单化整为零再乱也能理清想要别人那一格填1先认真填好自己这一格——相互是关系最朴素的法则别为几乎用不到的可能过度预留看清自己是稀疏还是稠密恰到好处才是真周全——一个懂得化繁为简、以心换心、按需适配的人才能像那张清晰的关系表格纵使身处纵横交错的茫茫人海也总能厘清那一段段联系对称地、坦荡地记住每一个与自己真心相连的人。这就是藏在邻接矩阵背后那张关系表格最深、也最美的浪漫。