JavaScript数据结构和算法之图和图算法

图的定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

有向图

有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。

无序图

无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示。

简单图

简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。

图类

表示顶点

创建图类的第一步就是要创建一个Vertex类来保存顶点和边。这个类的作用和链表、二叉搜索树的Node类一样。Vertex类有两个数据成员:一个用于标识顶点,另一个表明是否被访问过的布尔值。分别被命名为label和wasVisited。

代码如下:

function Vertex(label){
    this.label = label;
}

我们将所有顶点保存在数组中,在图类里,可以通过他们在数组中的位置引用他们

表示边

图的实际信息都保存在“边”上面,因为他们描述了图的结构。二叉树的一个父节点只能有两个子节点,而图的结构却要灵活得多,一个顶点既可以有一条边,也可以有多条边和它相连。

我们将表示图的边的方法成为邻接表或者邻接表数组。它将存储由顶点的相邻顶点列表构成的数组

构建图

定义如下一个Graph类:

代码如下:

function Graph(v){
    this.vertices = v;//vertices至高点
    this.edges = 0;
    this.adj = [];
    for(var i =0;I<this.vertices;++i){
        this.adj[i] = [];
        this.adj[i].push('');
    }
    this.addEdge = addEdge;
    this.toString = toString;
}

这个类会记录一个图表示了多少条边,并使用一个长度与图的顶点数来记录顶点的数量。

代码如下:

function addEdge(){
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.edges++;
}

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

图的遍历

深度优先遍历

深度优先遍历(DepthFirstSearch),也有称为深度优先搜索,简称为DFS。

比如在一个房间内寻找一把钥匙,无论从哪一间房间开始都可以,将房间内的墙角、床头柜、床上、床下、衣柜、电视柜等挨个寻找,做到不放过任何一个死角,当所有的抽屉、储藏柜中全部都找遍后,接着再寻找下一个房间。

深度优先搜索:

深度优先搜索就是访问一个没有访问过的顶点,将他标记为已访问,再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点

为Graph类添加一个数组:

代码如下:

this.marked = [];//保存已访问过的顶点
for(var i=0;i<this.vertices;++i){
    this.marked[i] = false;//初始化为false
}

深度优先搜索函数:

代码如下:

function dfs(v){
    this.marked[v] = true;
    //if语句在这里不是必须的
    if(this.adj[v] != undefined){
        print("Visited vertex: " + v );
        for each(var w in this.adj[v]){
            if(!this.marked[w]){
                this.dfs(w);
            }
        }
    }
}

广度优先搜索

广度优先搜索(BFS)属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

广度优先搜索从第一个顶点开始,尝试访问尽可能靠近它的顶点,如下图所示:

其工作原理为:

1. 首先查找与当前顶点相邻的未访问的顶点,将其添加到已访问顶点列表及队列中;
 2. 然后从图中取出下一个顶点v,添加到已访问的顶点列表
 3. 最后将所有与v相邻的未访问顶点添加到队列中
下面是广度优先搜索函数的定义:

代码如下:

function bfs(s){
    var queue = [];
    this.marked = true;
    queue.push(s);//添加到队尾
    while(queue.length>0){
        var v = queue.shift();//从队首移除
        if(v == undefined){
            print("Visited vertex: " + v);
        }
        for each(var w in this.adj[v]){
            if(!this.marked[w]){
                this.edgeTo[w] = v;
                this.marked[w] = true;
                queue.push(w);
            }
        }
    }
}

最短路径

在执行广度优先搜索时,会自动查找从一个顶点到另一个相连顶点的最短路径

确定路径

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

代码如下:

this.edgeTo = [];//将这行添加到Graph类中

//bfs函数
function bfs(s){
    var queue = [];
    this.marked = true;
    queue.push(s);//添加到队尾
    while(queue.length>0){
        var v = queue.shift();//从队首移除
        if(v == undefined){
            print("Visited vertex: " + v);
        }
        for each(var w in this.adj[v]){
            if(!this.marked[w]){
                this.edgeTo[w] = v;
                this.marked[w] = true;
                queue.push(w);
            }
        }
    }
}

拓扑排序算法

拓扑排序会对有向图的所有顶点进行排序,使有向边从前面的顶点指向后面的顶点。
拓扑排序算法与BFS类似,不同的是,拓扑排序算法不会立即输出已访问的顶点,而是访问当前顶点邻接表中的所有相邻顶点,直到这个列表穷尽时,才会将当前顶点压入栈中。

拓扑排序算法被拆分为两个函数,第一个函数是topSort(),用来设置排序进程并调用一个辅助函数topSortHelper(),然后显示排序好的顶点列表

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

代码如下:

//topSort()函数
function topSort(){
    var stack = [];
    var visited = [];
    for(var i =0;i<this.vertices;i++){
        visited[i] = false;
    }
    for(var i = 0;i<this.vertices;i++){
        if(visited[i] == false){
            this.topSortHelper(i,visited,stack);
        }
    }
    for(var i = 0;i<stack.length;i++){
        if(stack[i] !=undefined && stack[i] != false){
            print(this.vertexList[stack[i]]);
        }
    }
}

//topSortHelper()函数
function topSortHelper(v,visited,stack){
    visited[v] = true;
    for each(var w in this.adj[v]){
        if(!visited[w]){
            this.topSortHelper(visited[w],visited,stack);
        }
    }
    stack.push(v);
}

(0)

相关推荐

  • JavaScript数据结构和算法之二叉树详解

    二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct

  • JavaScript实现链表插入排序和链表归并排序

    本篇文章详细的介绍了JavaScript实现链表插入排序和链表归并排序,链表的归并排序就是对每个部分都进行归并排序,然后合并在一起. 1.链表 1.1链表的存储表示 //链表的存储表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; 1.2基本操作 创建链表: /* * 创建链表. * 形参num为链表的长度,函数返回链表的头指针. */ Link

  • JavaScript实现的链表数据结构实例

    此例是javascript来建立链表.. 并对此进行了排序.. 还可以在GenericList一般链表上进行扩展. 实现各种排序及增,删,改结点.. 复制代码 代码如下: function Node(){   this.data=null;   this.next=null; } function GenericList(){   this.head=null;   this.current=null;   //打出所有的链表结点   this.print= function(){   this

  • js实现双向链表互联网机顶盒实战应用实现

    上实战代码: linkedlistnode.js 节点类 复制代码 代码如下: /* * 链表节点 */ Dare.LinkedListNode = function () { this.data = null;//数据域 this.prev = null;//前驱 this.next = null;//后驱 }; Dare.extend(Dare.LinkedListNode, Dare); Dare.LinkedListNode.prototype.getValue = function (

  • Node.js环境下JavaScript实现单链表与双链表结构

    单链表(LinkedList)的javascript实现 npmjs相关库: complex-list.smart-list.singly-linked-list 编程思路: add方法用于将元素追加到链表尾部,借由insert方法来实现: 注意各个函数的边界条件处理. 自己的实现: SingleNode.js (function(){ "use strict"; function Node(element){ this.element = element; this.next = n

  • javascript数据结构之双链表插入排序实例详解

    本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

  • JavaScript数据结构之链表的实现

    前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

  • JavaScript数据结构之双向链表定义与使用方法示例

    本文实例讲述了JavaScript数据结构之双向链表定义与使用方法.分享给大家供大家参考,具体如下: 双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素. 双向链表提供了两种迭代列表的方法:从头到尾,或者反过来.我们也可以访问一个特定节点的下一个或前一个元素.在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代.这是双向链表的一个优点. function DoubleLink(

  • 使用JavaScript实现链表的数据结构的代码

    链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)   - 维基百科 上面是维基百科对 链表 的解读.下面我们用 JavaScript 代码对链表的数据结构进行实现 实现Node类表示节点 /** * Node 类用来表示节点 * element 用来保存节点上的数据 * next 用来保存指向下一个节点的链接 */ function Node(element) { this.elemen

  • JavaScript数组实现数据结构中的队列与堆栈

    一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

  • javascript循环链表之约瑟夫环的实现方法

    前言 传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围.犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案.他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人.约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存.写一段程序将n 个人围成一圈,并且第m个人会被杀掉,计算一圈人中哪两个人最后会存活.使用循环链表解决该问题. 看到这个问题首先想到的是要用到循环链表,还有就是要计算

  • js单向链表的具体实现实例

    复制代码 代码如下: function linkNode(_key, _value){    /// <summary>    /// 链表类的节点类    /// </summary>    this.Key = _key;    this.Value = _value;    this.next = null;}function Link(){    /// <summary>    /// 创建一个链表类    /// </summary>    th

随机推荐