什么是图?
图是一种复杂的非线性表结构.由若干给定的点一级任意两点间的连线所构成.图通常用来描述事物之间的特定关系, 代表的就是事物, 线就是事物之间所具有的关系.例如社交网络就是一种典型的图关系, 每一个用户都是一个顶点,任意两个用户加了好友, 他们之间就有了一条边.
简单总结下, 图就是由顶点(vertex)和边(edge)组成.
除此而外, 图中还有度的概念, 和顶点相连的边数就称为度. 如果用微信来类比的话, 我们自己本身就是一个顶点, 我们微信中的好友个数, 就是度.
在有向图中, 度又被分为入度(In-degree)和出度(Out-degree). 入度指的是有多少个边指向这个顶点, 而出度指的是有多少个边以此顶点为起点指向其他的顶点.这种情况可以用微博来类比下, 你被多少人关注了就是入度, 你关注了多少人就是出度.
还有一种带权图,每条边都会被分配一个权重(weight), 权重可以用来表示边之间的比较关系.比如时间更短, 道路状况更加良好等等.
图的存储
邻接矩阵存储邻接矩阵的存储, 实际上使用的是一个二维数组. 在无向图的存储中, 如果顶点 i 和 j 之间有一条边, 那么我们就将 Array [ i ] [ j ] 和 Array [ j ] [ i ] 都标记为 1. 如果是有向图, i → j, 则 Array [ i ] [ j ] 标记为 1, 反之亦然. 带权图中, 数组存储对应的权重.
邻接矩阵存储图虽然很直观, 但是浪费空间. 在无向图中, 如果 Array [ i ] [ j ] 被标记为 1, 那么 Array [ j ] [ i ] 也必然为 1.这样我们就有一半的空间浪费掉了. 而对于顶点多, 边少的稀疏图来说, 浪费则可能更加严重.
但它也有自己的优点, 因为是基于数组的, 所以查找两条边的关系时非高效, 还有可以将很多图的运算转换成矩阵之间的运算.邻接表存储
邻接表其实有点像散列表.
图中的每一个顶点都存储一条链表, 链表中存储的是所有与它相连的顶点.
邻接表虽然在存储上节省了空间, 但在查找上却比邻接矩阵耗时.
深度优先搜索
图的搜索算法, 最直接的理解就是从某个顶点出发, 到另一个顶点的最短路径. 深度优先搜索和广度优先搜索是其中最简单最暴力的两种.
理解深度优先搜索算法最简单就是把它想象成是在走迷宫,我们从入口开始出发, 每遇到一个岔口, 就选择其中一个, 如果有路就一直走, 直到到达目的地. 如果没有路了, 就返回上一个岔路, 重新选择一条路.
深度优先搜索使用的就是回溯思想.
class Graph {constructor(v) {this.adj = new Map()this.v = vfor (let i = 0; i < v; i++) {this.adj.set(i, [])}}addEdge(s, t) {this.adj.get(s).push(t)this.adj.get(t).push(s)}getAdj() {return this.adj}}
这里我们使用邻接表来存储图. 用深度递归来寻找 s 到 t 的最短路径.
class Graph {......DFS(s, t) {const prev = new Array(this.v).fill(-1) // 存储访问过的路径const visited = new Array(this.v) // 存储已经访问过的节点, 避免重复访问let isFound = false // 是不是已经找到visited[s] = truethis.recurse(s, t, prev, visited, isFound)printPrev(prev, s, t)}recurse(s, t, prev, visited, isFound) {if (isFound) {return}visited[s] = trueif (s === t) {isFound = truereturn}let curr = this.adj.get(s)for (let i = 0; i < curr.length; i++) {let q = curr[i]if (!visited[q]) {visited[q] = truethis.recurse(q, t, prev, visited, isFound)}}}}
广度优先搜索
广度优先搜索是一种像水波一样的从中心向外扩散的策略. 从起点开始先寻找离它最近的点(可能是多个), 然后是次近的, 直到找到为止.
class Graph{......BFS(s, t) {if (s === t) {return}const prev = new Array(this.v).fill(-1) // 存储访问路径const queue = [] // 存储已经访问, 但相邻顶点还没有被访问的顶点. 只有访问完 k 层的所有顶点, 才能访问第 k+1 层的.const visited = [] // 用来存储已经被访问过的顶点, 避免重复访问let isFinised = falsequeue.push(s)visited[s] = truewhile (queue.length !== 0 && !isFinised) {let w = queue.shift()let curr = this.adj.get(w)for (let i = 0; i < curr.length; i++) {let q = curr[i]if (!visited[q]) {prev[q] = wif (q === t) {isFinised = truebreak}visited[q] = truequeue.push(q)}}}if (isFinised) {printPrev(prev, s, t) //打印路径} else {console.log('not found')}}}
