图的类型和结构图是由边连接的节点组成的。由一条线连接的两个节点称为相邻顶点。同时，我们可以称一个节点度的连接数。边缘也可以被加权。路径是相邻节点的序列。一种可以回到原点的路径是循环图。没有返回原点路径的图称为无环图。如果图之间的边是有向的，则称为有向图。反之，如果图之间的边没有方向，则称为无向图。如果一个图是有向无环的，则称为我们上一讲提到的有向无环图（DAG，directedacyclicgraph）。一种存储图的方法是通过邻接矩阵（adjacencymatrix），它适用于稠密图（densegraph）。另一种存储图的方法是通过邻接表（adjacencylist）。这种数据结构可以用数组、链表、哈希或字典来表示，因此可以有效地补充邻接矩阵。图的遍历有两种经典的方式，一种是广度优先搜索（BFS，breathfirstsearch），一种是深度优先搜索（DFS，depthfirstsearch）。广度优先搜索最经典的使用场景就是寻找最短路径（shortestpath）的场景。深度优先搜索是一种遍历方法，可以用在我们前面提到的拓扑排序中。如何在选择中找到最短路径如图所示，假设我们要计算从A到B、C、D、E和Z的最短距离。Dijkstra算法首先将所有距离初始化为无穷大dist[i]=INF;visited数组未visited[i]=false，然后将源到自身的距离设置为零dist[src]=0。接下来，为了找到最短距离，我们在没有处理过的节点中寻找最短的minDist(dist,visited)，然后标记为visited[u]=true;当我们找到并设置最短距离dist[u]+graphu时，将返回一个包含所有路径的数组。这是简化的代码：constdijkstra=(graph,src)=>{for(leti=0;i
