数据结构教程系列04:在JavaScript中引入图

作者 : IT 大叔 本文共7105个字,预计阅读时间需要18分钟 发布时间: 2020-09-9

数据结构教程系列

数据结构教程系列01:JavaScript数组教程

数据结构教程系列02:使用Java深入研究树

数据结构教程系列03:如何在Java中使用链接列表

数据结构教程系列04:在JavaScript中引入图

数据结构教程系列05:在JavaScript中实现哈希表

数据结构教程系列06:如何在Java中使用堆栈和队列

在计算机编程中,数据结构用于组织数据并将算法(或命令)应用于代码。对数据结构和算法有很好的了解对于解决问题非常有用,并且对于破解编码面试至关重要。实际上,与数据结构有关的问题是入门级访谈中最常见的一些问题。

今天,我们将研究图形数据结构,它是在计算,数学和其他相关领域中应用最广泛的数据结构之一。我们将介绍:

  • 什么是图?
  • 图的类型
  • 如何在JavaScript中实现图形
  • 图的实际用途
  • 包装和资源

什么是图?

当我们谈论图时,首先想到的是用于建模数据的常规图。在计算机科学中,该术语具有完全不同的含义。

在编程中,图是一种常见的数据结构,它由节点(或顶点)和的有限集合组成。边连接顶点以形成网络。边缘可以是单向或双向的。边在有向图中也称为箭头,并且可能包含显示从一个顶点到另一个顶点所需的成本的值。

顶点类似于链接列表节点。一对(x,y)称为边。这表明x顶点连接到y顶点。

数据结构教程系列04:在JavaScript中引入图插图

图的术语

让我们探讨在使用图形时会遇到的一些常见术语。为了成功使用图表,理解关键术语以掌握不同属性之间如何相互影响非常重要。让我们来看看。

数据结构教程系列04:在JavaScript中引入图插图(2)

顶点度:连接到顶点的边总数。学位分为两种:

  • 程度内:连接到顶点的总数。
  • 外度:连接到顶点的外沿总数。

邻接:两个顶点被认为是相邻的,如果有其直接连接的边缘。

平行边:如果两个无向边具有相同的最终顶点,则它们是平行的。如果两个有向边的起点和终点相同,则它们是平行的。

自环:当边在同一顶点上开始和结束时发生。

孤立的顶点:零度的顶点,表示它不是边的端点。

图的类型

有两种常见的图形类型。在无向图中,默认情况下,边是双向的。例如,对(0,1)表示在顶点0和1之间存在一条没有特定方向的边。您可以从顶点0到1,反之亦然。

假设我们要计算无向图的最大可能边。具有n个顶点的图形的最大可能边将是所有可能的顶点对。有C(n,2)根据组合学,可能的一对顶点。通过二项式系数求和\ frac {n(n-1)} {2},所以有 \ frac {n(n-1)} {2} 无向图中的最大可能边。

在有向图中,边是单向的。例如,对(0,1)表示存在从顶点0到顶点1的边,并且遍历的唯一方法是从0到1。

这将更改图形中可以存在的边数。对于有向图ñ 顶点,可以将一个顶点与其他每个顶点连接的边的最小数量为 n-1。因此,如果您有n个顶点,则可能的边为n *(n-1)

 

数据结构教程系列04:在JavaScript中引入图插图(4)

图形表示的类型

在尝试解决系统中的问题时,我们可以用不同的方式表示图。在本节中,我们将介绍两种最常用的表示形式:邻接表邻接矩阵

邻接矩阵

邻接矩阵是一个二维矩阵,其中每个单元格可以包含0或1.行和列标题分别代表源顶点和目标顶点。如果单元格包含1,则表示在相应的顶点之间有一条边。边缘操作是在恒定时间内执行的,因为我们只需要操纵特定单元格中的值即可。

数据结构教程系列04:在JavaScript中引入图插图(6)

主数据结构用于编码采访。

邻接表

在邻接列表中,链接列表数组用于存储两个顶点之间的边。数组的大小等于顶点数。此数组中的每个索引代表图中的特定顶点。如果将新顶点添加到图形中,则也将其简单地添加到数组中。

向邻接表添加边和顶点也是时间恒定的操作。去除边缘O(E)时间,因为在最坏的情况下,所有边缘都可能在单个顶点上。因此,我们将遍历所有E边以到达最后一条。移除顶点O(V + E) 时间,因为我们必须删除其所有边缘,然后将列表的其余部分重新索引一步。

数据结构教程系列04:在JavaScript中引入图插图(8)

用例:两种表示形式都适合不同的情况。如果您的模型经常操纵顶点,则邻接表是一个更好的选择。如果您主要处理边缘,则邻接矩阵是更有效的方法。

如何在JavaScript中实现图形

我们从理论的角度看了图。现在,让我们尝试在代码中实现图形。毕竟,学习数据结构的最好方法是将它们与实际数据一起使用。以下实现使用JavaScript,并将基于邻接列表表示形式。

众所周知,Graph该类包含两个数据成员:

  • 图中的顶点总数
  • 一组链接列表,用于存储相邻的顶点
class Graph{
  constructor(vertices){
    //Total number of vertices in the graph
    this.vertices=vertices;
    //Defining an array which can hold LinkedLists equal to the number of vertices in the graph
    this.list=[];
    //Creating a new LinkedList for each vertex/index of the list
    for(i=0; i<vertices.length; i++){
      let temp=new LinkedList();
      this.list.push(temp);
    }
  }
}

在这里,我们奠定了Graph班级的基础。变量vertices包含一个整数,用于指定顶点总数。第二个组件是array,它将用作我们的邻接表。我们只需要运行一个循环并为每个顶点创建一个链表。现在,我们将添加两个方法来使该类起作用:

  • printGraph():这将打印图形的内容
  • addEdge():这将源与目标连接起来

index.js

"use strict";
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');

class Graph {
  constructor(vertices) {
    //Total number of vertices in the graph
    this.vertices = vertices;
    //Array that holds linked lists equal to the number of vertices in the graph
    this.list = [];
    //Creating a new linked list for each vertice of the graph
    var it;
    for (it = 0; it < vertices; it++) {
      let temp = new LinkedList();
      this.list.push(temp);
    }
  }

  addEdge(source, destination) {
    if (source < this.vertices && destination < this.vertices)
    //Since we are implementing a directed list, (0,1) is not the same as (1,0)
    this.list[source].insertAtHead(destination);
    //If we were to implement an undirected graph where (0,1)==(1,0), 
    //we would create an additional edge from destination to source too:
    //this.list[destination].insertAtHead(source);
  }

  printGraph() {
    console.log(">>Adjacency List of Directed Graph<<");
    var i;
    for (i = 0; i < this.list.length; i++) {
      process.stdout.write("|" + String(i) + "| => ");
      let temp = this.list[i].getHead();
      while (temp != null) {
        process.stdout.write("[" + String(temp.data) + "] -> ");
        temp = temp.nextElement;
      }
      console.log("null ");
    }
  }
}

let g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.printGraph();

node.js

"use strict";
module.exports = class Node {
  constructor(data) {
    this.data = data;
    this.nextElement = null;
  }
}

LinkedList.js

"use strict";
const Node = require('./Node.js');

module.exports = class LinkedList {
  constructor() {
    this.head = null;
  }

  //Insertion At Head  
  insertAtHead(newData) {
    let tempNode = new Node(newData);
    tempNode.nextElement = this.head;
    this.head = tempNode;
    return this; //returning the updated list
  }

  isEmpty() {
    return (this.head == null);
  }

  //function to print the linked list
  printList() {
    if (this.isEmpty()) {
      console.log("Empty List");
      return false;
    } else {
      let temp = this.head;
      while (temp != null) {
        process.stdout.write(String(temp.data));
        process.stdout.write(" -> ");
        temp = temp.nextElement;
      }
      console.log("null");
      return true;
    }
  }

  getHead() {
    return this.head;
  }
  setHead(newHead) {
    this.head = newHead;
    return this;
  }
  getListStr() {
    if (this.isEmpty()) {
      console.log("Empty List");
      return "null";
    } else {
      let st = "";
      let temp = this.head
      while (temp != null) {
        st += String(temp.data);
        st += " -> ";
        temp = temp.nextElement;
      }
      st += "null";
      return st;
    }
  }
  insertAtTail(newData) {
    //Creating a new Node with data as newData
    let node = new Node(newData);

    //check for case when list is empty
    if (this.isEmpty()) {
      //Needs to Insert the new node at Head
      this.head = node;
      return this;
    }

    //Start from head
    let currentNode = this.head;

    //Iterate to the last element
    while (currentNode.nextElement != null) {
      currentNode = currentNode.nextElement;
    }

    //Make new node the nextElement of last node of list
    currentNode.nextElement = node;
    return this;
  }
  search(value) {
    //Start from the first element
    let currentNode = this.head;

    //Traverse the list until you find the value or reach the end
    while (currentNode != null) {
      if (currentNode.data == value) {
        return true; //value found
      }
      currentNode = currentNode.nextElement
    }
    return false; //value not found
  }
  deleteAtHead() {
    //if list is empty, do nothing
    if (this.isEmpty()) {
      return this;
    }
    //Get the head and first element of the list
    let firstElement = this.head;

    //If list is not empty, link head to the nextElement of firstElement
    this.head = firstElement.nextElement;

    return this;
  }
  deleteVal(value) {
    let deleted = null; //True or False
    //Write code here

    //if list is empty return false
    if (this.isEmpty()) {
      return false;
    }

    //else get pointer to head
    let currentNode = this.head;
    // if first node's is the node to be deleted, delete it and return true
    if (currentNode.data == value) {
      this.head = currentNode.nextElement;
      return true;
    }

    // else traverse the list
    while (currentNode.nextElement != null) {
      // if a node whose next node has the value as data, is found, delete it from the list and return true
      if (currentNode.nextElement.data == value) {
        currentNode.nextElement = currentNode.nextElement.nextElement;
        return true;
      }
      currentNode = currentNode.nextElement;
    }
    //else node was not found, return false
    deleted = false;
    return deleted;
  }
  deleteAtTail() {
    // check for the case when linked list is empty
    if (this.isEmpty()) {
      return this;
    }
    //if linked list is not empty, get the pointer to first node
    let firstNode = this.head;
    //check for the corner case when linked list has only one element
    if (firstNode.nextElement == null) {
      this.deleteAtHead();
      return this;
    }
    //otherwise traverse to reach second last node
    while (firstNode.nextElement.nextElement != null) {
      firstNode = firstNode.nextElement;
    }
    //since you have reached second last node, just update its nextElement pointer to point at null, skipping the last node
    firstNode.nextElement = null;
    return this;
  }
}

addEdge(源,目标)

源和目标已经存储为数组的索引。此函数使用以下代码行将目标顶点插入源顶点的邻接链表中:

this.list[source].insertAtHead(destination)

我们实现了有向图,所以addEdge(0, 1)不等于addEdge(1, 0)

printGraph()

此函数使用嵌套循环迭代邻接表。每个链表都被遍历。

那么无向图呢?

到目前为止,我们已经介绍了有向图的实现。

对于无向图,我们创建了一条从源到目标以及从目标到源的边。这使其成为双向边缘。

图遍历算法

如前所述,当我们浏览图形时,我们正在遍历数据。这是指访问图的顶点的过程。遍历过程按访问顶点的顺序分类。这类似于遍历树。让我们进入图遍历的基本逻辑,看看如何使用算法来做到这一点。

在遍历图形时,我们使用级别的概念。以顶点为起点;这是最低的水平。下一层是所有相邻的顶点。更高的水平将是与这些节点相邻的顶点。

图遍历的两种基本技术是:

  • 广度优先搜索(BFS): BFS算法沿广度增长。遍历某个级别的所有节点,然后再继续下一个级别。这种逐级扩展可确保对于任何起始顶点,您一次都可以达到所有其他顶点。
  • 深度优先搜索(DFS):该算法与BFS相反。它在深度方向增长。从任何节点开始,我们移至相邻节点,直到达到最远的高度。然后,我们移回起点并选择另一个相邻节点。再次,我们探测到最远的水平并返回。该过程一直持续到访问所有节点为止。

图的实际用途

图形用于解决实际问题,这些问题涉及将问题空间表示为网络。任何与网络相关的应用程序(路径,查找关系,路由等)都应用图的概念。因此,图形数据结构在几种应用程序中起着基本作用:

  • 全球定位系统
  • 神经网络
  • 对等网络
  • 搜索引擎爬虫
  • 垃圾收集
  • 社交网站
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 数据结构教程系列04:在JavaScript中引入图

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论