2024-12-13 日报 Day15

今日的鸡汤

少欲则心静，心静则事简，只有这样方能够挣脱繁华虚妄的羁绊，拥抱明确而简单的生活。

今日学习内容

1、《JavaScript数据结构与算法》 P161-166

今日笔记

1、非线形数据结构-图。图是由一组由边连接的节点(或顶点)。
图由G=(V,E)组成，其中V是顶点的集合，E是边的集合。
由一条边连接在一起的顶点称为相邻顶点。
一个顶点的度是其相邻顶点的数量。
路径是顶点v1,v2,…,vk的一个连续序列，其中vi和vi+1是相邻的。
简单路径要求不包含重复的顶点。
图分为有向图和无向图。图还可以是加权的或非加权的。
2、图的表示: 从数据结构上来说可以用多种方式来表示图，不存在绝对的正确表示方法，取决于待解决的问题和图的类型。

• 邻接矩阵: 二维数组，其中的元素表示两个顶点之间是否有一条边。如果索引为i的节点和索引为j的节点相邻，则matrix[i][j]为1，否则为0。
• 邻接表: 用列表(数组)、链表，甚至是散列表或是字典来表示相邻顶点列表。
• 关联矩阵: 二维数组，其中的元素表示顶点和边的关系。行表示顶点，列表示边，元素表示顶点和边的关系。可以使用二维数组来表示两者之间的连通性，
  如果顶点v是边e的入射点，则array[v][e]为1，否则为0。关联矩阵通常用于边的数量比顶点多的情况下，以节省空间和内存。
  3、创建Graph类

  function Graph(){
    var vertices = [];
    var adjList = new Dictionary();
  }

  其中vertices数组用来存储图中所有顶点的名字，adjList用来存储邻接表。图类需要实现三个方法:
• addVertex: 向图中添加一个新的顶点。

  this.addVertex = function(v){
    vertices.push(v);
    adjList.set(v, []);
  };

• addEdge: 添加一条边。

  this.addEdge = function(v, w){
    adjList.get(v).push(w);
    adjList.get(w).push(v);
  };

• toString: 输出图的顶点和邻接表。

this.toString = function(){
  var s = '';
  for(var i=0; i<vertices.length; i++){
    s += vertices[i] + ' -> ';
    var neighbors = adjList.get(vertices[i]);
    for(var j=0; j<neighbors.length; j++){
      s += neighbors[j] + ' ';
    }
    s += '\n';
  }
}