第16页Graph drawing内容两幅图标注为“同一个图的两种绘制方式”文字说明“Caveat. Intuition can be misleading.”物理事实图的定义只包含两个集合顶点集合和边集合。每条边是一对顶点编号0-1、2-5 等。绘制drawing是指把顶点放在二维平面上的某个坐标位置把边画成连接这两个坐标的线段或曲线。两幅图绘制的是同一个图。顶点编号相同边集相同。唯一不同的是各顶点在平面上的物理坐标被重新摆放了。视觉效果线条是否交叉、顶点是否聚在一起是绘制坐标的函数不是图本身的属性。同一个图可以画成交叉很多的图也可以画成无交叉的平面图只要顶点可以重新放置。该页的技术结论是不要依赖绘制来判断图的结构。判断路径、连通性、环是否存在只能通过遍历边集来完成而不是看画出来的线条是否碰在一起。第17页Graph representation内容顶点用整数编号 0 到 V-1具体应用时通过符号表Symbol Table把名字如“Princeton”映射成整数。物理事实图数据结构的输入和输出使用整数作为顶点标识因为整数可以直接用作数组索引数组索引是 O(1) 随机访问的物理基础。现实应用中的数据如域名、人名、基因名称需要先通过符号表转换成整数。转换过程由第三章的符号表实现完成图本身只处理整数数组。这种设计把“命名映射”和“图结构”解耦图的邻接表只存整数不存字符串避免在遍历过程中反复做字符串比较。第18页Graph API内容显示了 Graph 类的方法Graph(int V)创建 V 个顶点、0 条边的空图。int V()返回顶点数。int E()返回边数。void addEdge(int v, int w)在 v 和 w 之间添加一条边。IterableInteger adj(int v)返回与 v 相邻的所有顶点用于遍历。String toString()字符串表示便于调试。物理事实addEdge在无向图中必须把 v 加入 w 的邻接表同时把 w 加入 v 的邻接表。一次调用产生两条有向记录但逻辑上算一条无向边。adj(v)返回的是一个可迭代对象不复制底层数据。调用者通过 for (int w : G.adj(v)) 遍历时每次迭代从邻接表的当前节点取出一个整数地址移动到链表下一个节点。这个遍历不创建新数组不复制数据。API 不指定底层数据结构。它只定义客户端可以执行的操作。具体实现可以是边列表、邻接矩阵或邻接表由构造函数决定。第19页Graph input format内容输入格式为第一行是顶点数 V第二行是边数 E之后每行是“v w”表示一条边。示例文件tinyG.txt的内容是text13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3下方代码展示了如何用In读入并构造图然后遍历所有顶点的邻接表打印所有边。物理事实读入流程构造In对象读第一整数作为 V第二整数作为 E。然后循环 E 次每次读两个整数调用addEdge(v, w)。输出时for (int v 0; v G.V(); v) 外层按顶点编号顺序遍历内层 for (int w : G.adj(v)) 按邻接表中存储的顺序遍历。因为每条无向边被存了两次v→w 和 w→v所以输出时每条边会被打印两次一次从 v 出发一次从 w 出发除非你在打印时加条件过滤。这种输入格式的约定是固定的第一行必须是 V第二行必须是 E。如果文件顺序不符In不会报错但后续读取会读到错误的数值导致图结构错误。第20页Graph client example内容列出了四个静态方法degree(G, v)遍历 v 的邻接表计数并返回度数。maxDegree(G)遍历所有顶点对每个顶点调用 degree返回最大值。averageDegree(G)返回 2 * E / V。numberOfSelfLoops(G)遍历所有边如果 v w 则计数最后除以 2。在无向图中一个顶点的度数是与该顶点直接相连的边的总数。例如如果一个顶点有三条边与之相连那么这个顶点的度数就是3。物理事实degree(G, v)的遍历次数等于该顶点的邻接表长度即该顶点的度数。每次迭代只是从链表节点读取一个整数做一次自增。复杂度 O(degree(v))。maxDegree对所有顶点各调用一次degree总遍历次数等于所有顶点度数之和 2E因此复杂度 O(E)。averageDegree用公式计算不遍历图。公式 2E/V 来自握手引理Handshaking Lemma无向图中所有顶点的度数之和等于 2 倍边数。numberOfSelfLoops中每条自环在邻接表中被存了两次因为 addEdge(v, v) 会把 v 加入自己的邻接表两次。遍历所有顶点时每条自环会被发现两次。所以最后结果要除以 2。public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); E; }第22页Adjacency matrix representation内容用 V × V 的布尔矩阵。adj[v][w] true表示 v-w 之间有边。物理事实内存布局一个二维布尔数组V 行每行 V 个布尔值。在 Java 中布尔数组每个元素占 1 字节实际 JVM 实现可能用 byte 数组加上数组对象头总空间约 V^2 字节。addEdge设置adj[v][w] true和adj[w][v] true。O(1)。adj(v)需要遍历第 v 行的所有 V 个布尔值检查哪些为 true。O(V)。edge between v and w直接读adj[v][w]。O(1)。空间复杂度 O(V^2)。V10^4 时矩阵有 10^8 个布尔值约 100 MBV10^5 时则 10^10 个值不可行。适用于稠密图边数接近 V^2不适用于稀疏图。第23页Adjacency list representation内容用顶点索引的数组每个数组元素是一个链表存储与该顶点相邻的顶点。物理事实内存布局一个长度为 V 的数组每个槽位存一个链表的头指针8字节。每个边对象或节点存一个整数相邻顶点编号和一个指向下一个节点的指针8字节。无向图中每条边产生两个节点v→w 和 w→v。addEdge把 w 加入 v 的链表头部把 v 加入 w 的链表头部。O(1)。adj(v)直接返回数组第 v 个槽位指向的链表头不复制O(1) 返回引用。edge between v and w遍历 v 的链表检查是否存在 w。O(degree(v))。空间V 个数组槽位 2E 个链表节点。每个节点存整数4字节 指针8字节 对象头16字节如果使用对象实际占 28 字节左右。空间 O(V E)。适用于稀疏图。第24页Adjacency-list graph representation: Java implementation内容Graph类的完整代码内部用BagInteger[] adj存储邻接表。代码关键点textprivate final int V; private int E; private BagInteger[] adj;构造函数textadj (BagInteger[]) new Bag[V]; for (int v 0; v V; v) adj[v] new BagInteger();addEdgetextadj[v].add(w); adj[w].add(v); E;adj(v)textreturn adj[v];物理事实BagInteger[] adj是一个引用数组每个槽位存一个 Bag 对象的地址。new Bag[V]只创建了 V 个空引用初始为 null不创建 Bag 对象。循环中再为每个槽位 new 一个 Bag。Bag内部用链表实现add操作插入到链表头部不检查重复。所以重复添加同一条边例如客户端调用了两次addEdge(0,1)会导致邻接表中出现重复整数图的语义变成多重边multigraph。标准实现不处理重复由客户端负责避免。强制转换(BagInteger[]) new Bag[V]是因为 Java 数组不能直接创建泛型数组。运行时adj实际类型是Bag[]每个槽位存的是 Bag 对象的地址。类型擦除后泛型检查只在编译期生效。第25页Sparse graphs内容展示两个 V50 的图说明现实图通常稀疏顶点多平均度数小。物理事实稀疏图指 E 远小于 V^2或者说平均度数 2E/V 是常数比如 3 或 10。邻接矩阵需要 V^2 个槽位即使只有少数边空槽位也占满整个 V×V 矩阵。V10^6 时 V^2 超过内存不可行。邻接表只存储实际存在的边空间 O(VE)可以处理 V10^6、E10^7 规模的图。遍历邻接表时每次只访问实际存在的邻居不扫描空槽位。图算法DFS、BFS的总复杂度取决于遍历的边数而不是 V^2。第26页Summary of representations内容表格比较三种表示在空间、添加边、判断边存在、遍历邻居上的复杂度。表示空间添加边边是否存在 (v,w)遍历 v 的邻居边列表E1EE邻接矩阵V^211V邻接表VE1degree(v)degree(v)物理事实边列表的“判断边是否存在”和“遍历邻居”都是 O(E)因为必须扫描所有边。适合边数极少且只做添加和全量遍历的场景如 Kruskal 算法初始的边集合排序。邻接矩阵的“判断边是否存在”是 O(1)因为直接数组下标访问。但“遍历邻居”是 O(V)必须扫描整行。邻接表的“判断边是否存在”是 O(degree(v))因为要遍历该顶点的链表。但“遍历邻居”正好是 O(degree(v))没有额外开销。图算法DFS、BFS的核心操作是“遍历邻居”所以邻接表是最常用的表示。①edge list应该是指用链表存储每个边然后逐个边检查。②adjacent matrix③adjacent list一、IterableQIterableInteger adj(int v)我想知道P18这个是啥Aadj(int v)是 Graph API 中定义的一个方法。输入顶点编号vint值。输出一个类型为IterableInteger的对象。物理事实Iterable是一个 Java 接口。这个接口只规定了一件事实现它的类必须提供一个iterator()方法。iterator()返回一个Iterator对象调用者通过反复执行next()可以逐个取出里面的Integer值。在具体的邻接表实现第 24 页中adj是一个数组数组的长度是V。数组的每个槽位存放一个Bag对象的引用地址。当你调用adj(v)时方法内部只有一行javareturn adj[v];它从数组的第v个槽位取出那个Bag对象的引用地址8 字节直接返回给调用者。这个过程没有复制邻接表中的任何数据没有新建任何Integer对象没有遍历链表。它只是把数组槽位里存的那个地址传出去。Bag类实现了Iterable接口所以adj(v)的返回值类型可以写成IterableInteger。把返回类型声明为接口类型而不是具体的Bag类是为了隐藏底层数据结构。调用者只知道它可以被遍历不知道它里面是链表、数组还是其他结构。调用者用for (int w : G.adj(v))遍历时编译器把for-each循环翻译成迭代器操作调用adj(v)拿到Iterable对象的地址。调用它的iterator()方法拿到Iterator对象的地址。每次循环调用Iterator.next()。next()从链表节点中取出存储的Integer对象引用然后 JVM 执行拆箱intValue把Integer转换成int赋值给w。这个方法的物理代价是 O(1) 时间O(1) 额外空间只传递一个地址。你不调用迭代器它就不遍历。二、bag-抽象数据类型QGraph 类的完整代码内部用 BagInteger[] adj 存储邻接表。为什么是bag的存储方式bag不是放入后不管顺序吗给我重新介绍一下bag呗ABag是这门课在第一章1.3 节定义的抽象数据类型。Bag 的 APIPPT 第 50 页add(Item item)向集合中添加一个元素。isEmpty()判断是否为空。size()返回元素个数。IterableItem支持遍历所有元素。Bag 的特点是只支持“添加”和“遍历”不支持“删除”。添加时没有位置指定遍历时没有顺序保证。你插入的顺序和遍历出来的顺序不一定一致具体取决于底层实现链表实现时遍历顺序是插入顺序的反向。为什么 Graph 的邻接表用 Bag 而不是 Stack 或 Queue物理上构建图的过程只需要两个操作addEdge(v, w)把w加入v的邻居集合把v加入w的邻居集合。adj(v)遍历v的所有邻居。这个需求不需要删除元素不需要“最近添加”或“最旧添加”的语义。如果使用StackAPI 里会有pop()意味着你可以从邻居集合中弹出一个元素——这在图结构中没有意义而且会破坏图的完整性。如果使用QueueAPI 里有dequeue()同样是多余的。Bag只提供“添加”和“遍历”两个操作正好是图邻接表所需的最小操作集。用Bag可以防止客户端代码意外调用pop()或dequeue()来修改邻接表。底层物理实现在algs4库中Bag通常用链表实现。每个Bag对象包含一个指向链表头节点的指针。add(item)在链表头部插入一个新节点O(1) 时间。iterator()返回一个迭代器对象它从链表头开始逐个节点访问直到尾部。所以Graph类的adj数组里每个槽位存的是一个Bag对象的地址。addEdge(v, w)会在adj[v]指向的Bag链表头部插入一个值为w的节点同时在adj[w]指向的Bag链表头部插入一个值为v的节点。顺序无关紧要因为图算法的正确性如 DFS 遍历路径、连通性检测不依赖邻居的排列顺序。任何顺序都不影响最终结果。Q那这个其实是我的思维没有转变过来因为我还在考虑那种存储一个东西不是存在数组就是存在链表里面的结构但是我没有往它向上一层的建设也就是栈、队列还有包的角度来想。那么我想我应该补一补这个方向的视角我们在存储的时候似乎有很多选择啊既可以选择用单纯的数组跟链表也可以用链表的变式例如二叉树红黑树等。同时你还可以选择用队列和包这一类的方式存储但是栈和队列以及数组链表还有二叉树红黑树我感觉他们不是同一层级的而像是三类。A第一层物理存储结构连续 vs 链式这一层决定元素在内存中的排列方式。数组Array在堆上分配一块连续的内存空间。每个元素的地址可以通过“首地址 索引 × 元素大小”直接计算出来因此支持 O(1) 随机访问。缺点是扩容时需要整体搬移且中间插入/删除需要移动后续元素。链表Linked List元素分散在堆中各处。每个节点除了存储数据外还存储一个指针8字节指向下一个节点的内存地址。访问第 k 个元素需要从头节点开始沿着指针一步步跳转不支持随机访问。优点是插入/删除只需修改相邻节点的指针不涉及整体搬移。这是最底层的物理存储手段无论上层是什么数据结构最终都要落在“连续内存块”或“分散节点指针”的范畴内。第二层抽象数据类型ADT, Abstract Data Type这一层只定义操作语义不规定底层物理实现。它回答的问题是我允许用户执行哪些操作以及这些操作的逻辑含义是什么栈Stack操作语义是 LIFO后进先出。提供 push、pop、peek。用户只关心“最后放进去的那个最先出来”不关心元素在内存中如何排列。队列Queue操作语义是 FIFO先进先出。提供 enqueue、dequeue。包Bag操作语义是“无序收集并遍历”。只提供 add 和 iterator。没有删除操作没有取出顺序的保证。你在 Graph API 中看到BagInteger[] adj就是使用了这一层的抽象。图的结构只需要“向 v 的集合中添加一个邻居 w”和“遍历 v 的所有邻居”这两个操作Bag正好提供了这两个操作且不引入多余的操作比如 pop防止客户端误用。第三层实现策略基于特定算法的组织方式这一层回答的问题是我用什么样的物理结构和算法来支持第二层定义的操作以达到最优的时间/空间性能栈可以用数组实现push在尾部添加pop从尾部移除指针后移/前移。访问快但容量有限需要扩容。栈也可以用链表实现push在头部插入pop从头部移除。容量无限受限于堆但每个节点有额外指针开销。队列可以用数组实现循环队列用两个指针 head 和 tail 在数组上滑动。队列也可以用链表实现head 指向队首tail 指向队尾enqueue在尾部插入dequeue在头部移除。当你提到“二叉树、红黑树”时它们属于第三层但通常用于实现另一种抽象数据类型——“符号表Symbol Table”也就是查找结构。符号表的操作是put(key, value)和get(key)。你可以用无序链表实现O(N)也可以用二叉搜索树实现平均 O(log N)还可以用红黑树实现保证 O(log N)或者用哈希表实现均摊 O(1)。三者之间的包含关系第一层数组/链表是底层结构。第三层数组实现的栈、链表实现的队列、二叉搜索树、红黑树是具体的搭建方案它规定了操作函数内部的指针动作和内存布局。第二层栈/队列/包/符号表是对外提供的接口契约。同一个契约如栈可以有多种搭建方案数组版栈、链表版栈只要它们都满足 LIFO 语义客户端就可以互换使用。所以你在思考“用哪种方式存储”时应该先确认你需要什么操作第二层再根据操作特征选择合适的实现策略第三层最后基于物理存储第一层评估内存和时间的代价。你现在习惯的“数组或链表”是停在第一层看问题而课程后续的代码DFS、BFS、并查集、符号表会不断要求你在第二层和第三层之间切换视角。Q那么也就是说当我要想存储的时候我应该先思考它的抽象数据类型也就是到底是用数组实现的栈链表实现的队列或包二叉树红黑树或者哈希码实现的符号表而后或许我再去知道这些抽象层面是怎么被实现的或许也不需要知道取决于是不是自己构建抽象层面我想大多数人都是直接用自带的结构和API。A正确并且符合实践。针对“大多数人”的场景客户端程序员调用库的人只需要知道抽象数据类型Abstract Data Type, ADT的契约put存什么、get取什么、push和pop的语义是什么。底层的数组扩容、链表指针重连、红黑树旋转、哈希表的拉链法处理碰撞——这些细节对客户端是完全隐藏的。库开发者保证了操作的正确性和性能承诺客户端只需信任 API 文档不需要关心物理内存里发生了哪些地址跳转。针对你这门课普林斯顿算法的场景你是“构建者”不是“大多数客户端”。这门课的训练目标恰恰是让你看透那些被隐藏的物理细节。因为性能预测依赖底层实现Bag用链表实现时add是 O(1)遍历是 O(N)但如果某天有人用数组实现Bagadd可能需要摊还 O(1)内存布局从分散变为连续对缓存cache的利用率完全不同。不看实现无法计算成本模型cost model。正确性证明依赖指针操作红黑树为什么是平衡的证明基于“红色链接永远向左倾斜”和“黑色高度一致”这些是显式的指针赋值和颜色位翻转不是抽象概念。后续章节图算法、字符串算法会不断要求你混用这些结构比如用Stack深度优先搜索、Queue广度优先搜索、MinPQ优先队列做 Dijkstra。如果你只把Stack当作“黑盒 LIFO”而不清楚它底层是数组还是链表你就无法解释为什么 DFS 在稀疏图上的内存占用是可接受的——链表栈每个节点多一个指针8字节数组栈可能有空余容量浪费摊还 1.5~2 倍内存。所以你的思维方式需要维持一种“双视角切换”的能力设计接口时站到第二层ADT只定义操作不暴露实现。分析性能时必须钻进第三层实现策略和第一层物理存储追踪每一条指针路径和每一次内存访问。三、P24页代码Q老实讲这儿的东西我没太看懂。他的内部本来就有一个不可更改的int V和bag类型下的Integer们为什么在Graph中还有这两个adj (BagInteger[]) new Bag[V];adj[v] new BagInteger();这看起来像是bag里面又装了bagA你的困惑集中在两点为什么需要这两个字段以及这段代码到底在分配什么。第一个困惑为什么需要private final int V和private BagInteger[] adj这两个东西V存储顶点总数。它是final因为图的顶点数量在构造时确定之后不改变。这个值用于构造adj数组时指定数组长度。adj()方法返回顶点数。后续遍历时如for (int v 0; v V; v)确定循环边界。这是一个整数值直接在Graph对象的堆内存里占 4 字节。adj存储所有顶点的邻接表集合。它是一个数组数组的长度是V每个槽位存一个BagInteger对象的引用8 字节。adj本身是一个对象引用变量位于Graph对象的实例数据区指向堆上的数组对象。这两个字段共同定义了图的状态有多少个顶点V以及每个顶点连到哪些其他顶点adj。缺任何一个图的完整信息都不成立。第二个困惑adj (BagInteger[]) new Bag[V];和adj[v] new BagInteger();在物理上做了什么这是“Bag 里面又装了 Bag”吗不是。“Bag 里面又装了 Bag”这个描述是错误的。我们把物理动作拆成两步第一步分配数组本身javaadj (BagInteger[]) new Bag[V];new Bag[V]在堆上分配一块连续的内存区域大小为V个槽位每个槽位 8 字节用于存引用。此时这个数组里每个槽位都存的是null空引用。数组本身是空的容器里面还没有任何Bag对象。强制转换(BagInteger[])是 Java 泛型数组创建的语法要求。运行时这个数组的真实类型是Bag[]不保留Integer这个泛型参数。把这行执行完adj指向了一个长度为V的引用数组。第二步为每个顶点创建一个独立的 Bag 对象填入数组槽位javafor (int v 0; v V; v) adj[v] new BagInteger();每执行一次new BagInteger()就在堆上新分配一个Bag对象的内存对象头 16 字节 实例数据可能包含一个指向链表头节点的指针。循环执行V次创建了V个完全独立的Bag对象。它们各自在堆内存中占据不同的地址。adj[v] ...把这V个Bag对象的引用地址分别填入数组的V个槽位中。物理结构图景adj指向数组对象 A。数组对象 A 的索引 0 槽位存着Bag对象 B0 的地址。数组对象 A 的索引 1 槽位存着Bag对象 B1 的地址。...Bag对象 B0 内部链表结构存的是Integer值比如 1、2、3而不是Bag。所以关系是数组套 Bag而非 Bag 套 Bag。adj是数组不是Bag。数组的每个元素是Bag。你现在对Bag的认识可能还没完全适应它的“容器”身份。BagInteger这个类型你可以把它理解成一个“链表头”。它本身不存储邻居数据它内部通过链表节点存储一系列Integer引用。adj[v]是一个Bag代表“顶点 v 的邻居集合”。Graph类管理了V个这样的集合每个集合对应一个顶点。