Graphs 简单学习

最近学习数据结构的时候，发现一个有意思的规律，那就是复杂的数据结构一定是对简单数据结构的封装和抽象。因此，今天学习一个稍微复杂的数据结构，那就是Graphs。

require("@fatso83/mini-mocha").install();
const { expect } = require('chai');
class Node {
  constructor(data) {
    this.data = data;
    this.nextElement = null;
  }
}

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() {
    const arrStr = [];
    if (this.isEmpty()) {
      arrStr.push('Empty List');
      console.log(arrStr.join(''));
      return false;
    } else {
      let temp = this.head;
      while (temp != null) {
        arrStr.push(temp.data);
        arrStr.push('->');
        temp = temp.nextElement;
      }
      arrStr.push('null');
      console.log(arrStr.join(''));
      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 += (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;
  }
}
//定义一个Graphs
class Graph {
  constructor(vertices){
    //存储顶点数目
    this.vertices = vertices;
    //Defining an array which can 
    //hold LinkedLists equal to the number of vertices in the graph
    //存储顶点对应的边的邻接表
    this.list = [];
    for (let i = 0 ; i < this.vertices ;i++) {
      const temp = new LinkedList();
      this.list.push(temp);
    }
  }

  printGraph() {
    console.log(">>Adjacency List of Directed Graph<<");
    var i;
    for (i = 0; i < this.list.length; i++) {
      console.log("|" + (i) + "| => ");
      let temp = this.list[i].getHead();
      while (temp != null) {
        console.log("[" + (temp.data) + "] -> ");
        temp = temp.nextElement;
      }
      console.log("end ");
    }
  }
  addEdge(source,destination) {
    if (source < this.vertices && destination < this.vertices)
      this.list[source].insertAtHead(destination);
  }
}

describe('LinkedList test',()=>{
  it('LinkedList insertAtHead test',()=>{
    const list = new LinkedList();
    expect(list.head).to.equal(null);
    list.insertAtHead(10);
    expect(list.head.data).to.equal(10);
    list.insertAtHead(20);
    expect(list.head.data).to.equal(20);
  });

  it('LinkedList isEmpty test',()=>{
    const list = new LinkedList();
    expect(list.isEmpty()).to.equal(true);
    list.insertAtHead(10);
    expect(list.isEmpty()).to.equal(false);
  });
  it('LinkedList printList test',()=>{
    const list = new LinkedList();
    expect(list.printList()).to.equal(false);
    list.insertAtHead(10).insertAtHead(20).insertAtHead(30);
    expect(list.printList()).to.equal(true);
  });
});

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

从以上代码可以看出，我们在Graph中使用了LinkedList数据结构，因此，如果熟练掌握了基础的数据结构,使用起来还是比较容易理解的；

我们为这个Graph添加了两个重要方法，

addEdge和printGraph一个用于构建整个Graph,另一个用于查看我们构建的情况是否正确。

我们以后再在这个类的基础上学习Graph的Breadth-First Search(BFS)和Depth-First Search (DFS)。

本文水平有限，如果发现有啥问题，希望能提出来一起讨论。