图形的定义。

图由有限的一组顶点和顶点之间的一组边组成，通常表示为G(V，E)，其中G代表一个图，V是图G中的顶点集，E是图G中的边集。

有向图

有向边：如果顶点VI到VJ的边有方向，那么这条边称为有向边，也称为圆弧，由有序对Vi和Vj表示，其中Vi称为弧尾，Vj称为弧头。

无序图

无向边：如果顶点Vi和Vj之间的边没有方向，称为无向边，用无序对(Vi，Vj)表示。

简单图形

简单图：在图结构中，如果从顶点到自身没有边，同一条边不重复出现，那么这样的图称为简单图。

图形类

代表一个顶点。

创建图形类的第一步是创建顶点类来保存顶点和边。该类的功能与链表和二叉查找树的Node类相同。顶点类有两个数据成员：一个用于标识顶点，另一个是布尔值，指示它是否被访问过。他们分别被命名为标签和被访问。

复制代码如下：函数顶点(标签){this。标签=标签；}

我们保存数组中的所有顶点，在graph类中，我们可以通过它们在数组中的位置来引用它们。

代表一条边。

图的实际信息保存在“边”上，因为它们描述了图的结构。二叉树的父节点只能有两个子节点，但是图的结构要灵活得多。一个顶点可以有一条边或多条边与之相连。

我们称表示图的边的方法为邻接表或邻接表数组。它存储一个由顶点列表和相邻顶点组成的数组。

结构图

定义了如下Graph类：复制代码如下：函数graph (v) {this。顶点=v；//顶点到最高点this . edges=0；this . adj=[]；for(var I=0；Ithis .顶点；I){ this . adj[I]=[]；这个。push(' ')；} this.addEdge=addEdgethis.toString=toString}这个类记录一个图代表多少条边，并使用图的长度和顶点数记录顶点数。复制代码如下：函数添加了ge () {this。可调的。push(w)；这个。push(v)；边缘；}

这里，我们使用for循环为数组中的每个元素添加一个子数组来存储所有相邻的顶点，并将所有元素初始化为空字符串。

图的遍历。

深度优先遍历a

DepthFirstSearch也称为深度优先搜索，简称DFS。

比如在一个房间里找钥匙，不管从哪个房间开始，找房间的角落，床头柜，床，床，衣柜，电视柜等。一个接一个，以免错过任何死角。当所有抽屉和储藏柜都找遍了，再找下一个房间。

深度优先搜索：

深度优先搜索是访问一个未访问的顶点，将其标记为已访问，然后递归访问初始顶点的邻居列表中的其他未访问的顶点。

为Graph类添加数组：复制代码如下： this . marked=[]；//保存(var i=0)的访问顶点；ithis .顶点；I){ this . mark[I]=false；//初始化为false}

深度优先搜索功能：复制代码如下：功能DFS (v) {this。标记为[v]=true；//if语句在这里没有必要if(this.adj[v]！=未定义){ print(' Visited vertex : ' v)；对于每个(var w in this.adj[v]){ if(！this . mark[w]){ this . DFS(w)；} } }}

广度优先搜索

广度优先搜索(BFS)是一种盲搜索方法，旨在系统地扩展和检查图中的所有节点以找到结果。换句话说，它不考虑结果的可能位置，彻底搜索整个图片，直到找到结果。

广度优先搜索从第一个顶点开始，并尝试尽可能接近地访问该顶点，如下图所示：

其工作原理是：

1.首先，搜索与当前顶点相邻的未访问顶点，并将其添加到访问顶点列表和队列中；2.然后从图中取出下一个顶点V，并将其添加到访问顶点列表中。3.最后，将所有与V相邻的未访问顶点添加到队列中。以下是广度优先搜索函数的定义：复制代码如下：函数BFS(s){ var queue=[]；this.marked=truequeue.push//添加到队列末尾while(queue . length 0){ var v=queue . shift()；//从组长处移除if (v==undefined) {print('受访顶点3360 ' v)；}对于每个(var w in this.adj[v]){ if(！this . marked[w]){ this . edge to[w]=v；this . marked[w]=true；queue . push(w)；} } }}

最短道路

当执行广度优先搜索时，自动找到从一个顶点到另一个连通顶点的最短路径。

确定路径

为了找到最短路径，我们需要修改广度优先搜索算法来记录从一个顶点到另一个顶点的路径。我们需要一个数组来保存从一个顶点到下一个顶点的所有边。我们将这个数组命名为edgeTo。

复制代码如下： this . edge to=[]；//将此行添加到Graph类。

//bfs函数函数bfs(s){ var queue=[]；this.marked=truequeue.push//添加到队列末尾while(queue . length 0){ var v=queue . shift()；//从组长处移除if (v==undefined) {print('受访顶点3360 ' v)；}对于每个(var w in this.adj[v]){ if(！this . marked[w]){ this . edge to[w]=v；this . marked[w]=true；queue . push(w)；} } }}

拓扑排序算法

拓扑排序对有向图的所有顶点进行排序，使有向边从前一个顶点指向后一个顶点。拓扑排序算法与BFS相似，但不同的是，拓扑排序算法不会立即输出访问过的顶点，而是访问当前顶点邻接表中的所有相邻顶点，直到列表耗尽才会将当前顶点推入堆栈。

拓扑排序算法分为两个功能。第一个函数是topSort()，用于设置排序过程并调用辅助函数topSortHelper()，然后显示排序后的顶点列表。

拓扑排序算法的主要工作在递归函数topSortHelper()中完成，该函数将当前顶点标记为已访问，然后递归访问当前顶点邻接表中的每个顶点，并将这些顶点标记为已访问。最后，将当前顶点压入堆栈。

复制的代码如下：///topSort()函数topSort(){ var stack=[]；var visited=[]；for(var I=0；ithis .顶点；I){ visited[I]=false；} for(var I=0；ithis .顶点；I){ if(visited[I]==false){ this . topworthhelper(I，visited，stack)；} } for(var I=0；istack.lengthi ){ if(stack[i]！=未定义的堆栈[i]！=false){ print(this . vertexlist[stack[I]])；} }}

//toporthelper()函数函数toporthelper(v，visited，stack){ visited[v]=true；对于每个(var w in this.adj[v]){ if(！已访问[w]){ this . topworthelper(已访问[w]，已访问，stack)；} } stack . push(v)；}