关于数据结构和算法:数据结构与算法学习图论

什么是图？

在计算机程序设计中，图构造也是一种十分常见的数据结构
然而图论其实是一个十分大的话题
图构造是一种与树结构有些类似的数据结构
图论是数学的一个分支，并且在数学概念上，树是图的一种
它以图为钻研对象，钻研顶点和边组成的图形的数学实践和办法
次要钻研的目标是事务之间的关系，定点代表事务，边代表两个事物间的关系

图的事实案例

人与人之间的关系网
甚至科学家们在察看人与人之间的关系网时，还发现了六度空间实践

六度空间实践

实践上认为世界任何不意识的两个人只须要很少的中间人就能够建设起分割。
并非肯定通过六步，只是须要很少的步骤

图通常有什么特点？

一组顶点：通常用 V(Vertex)示意顶点的汇合
一组边：通常用 E(Edge)示意边的汇合
边是顶点和顶点之间的连线
边能够是有向的，也能够是无向的
比方 A —-B，通常示意无向
A—->B，通常示意有向

七桥问题

图形一笔画完的条件：有 0 个奇点或有 2 个奇点
咱们来看一下口这个字有 4 个偶点 0 个奇点所以一笔可能画完（由单数的边连贯的都是偶点，由复数的边连贯的都是奇点）

田字不能一笔画成，因为它的奇点有四个（红色）违反了规定。

图的术语

顶点

顶点方才咱们曾经介绍过了，示意图中的一个节点
比方下图中的数字

边

边方才咱们也介绍过了，示意顶点和顶点之间的连线
比方地铁站中两个站点之间的间接连线，就是一个边
留神：这里的边不要叫做门路，门路有其余的概念，待会儿咱们会介绍
下图中 0 – 1 有一条边，1 – 2 有一条边，0 – 2 没有边

相邻顶点

由一条边连贯在一起的顶点称为相邻顶点

度

一个顶点的度是相邻顶点的数量
比方 0 顶点和其余两个顶点相连，0 顶点的度是 2
比方 1 顶点和其余四个顶点相连，1 顶点的度是 4

门路

门路是顶点 v1,v2…,vn 的一个间断序列，比方下图中 0 1 5 9 就是一条门路
简略门路：简略门路要求不蕴含反复的顶点，比方 0 1 5 9 是一条简略门路
回路：第一个顶点和最初一个顶点雷同的门路称为回路 比方 0 1 5 6 3 0

无向图：

下图图就是一张无向图，因为所有的边都没有方向
比方 0 – 1 之间有边，那么阐明这条边能够保障 0 ->1，也能够保障 1 ->0

无权图:

下图就是一张无权图（边没有携带权重），图中的边是没有任何意义的。
不能说 4 - 9 的边比 0 - 1 的边更远或者更长。

有向图

有向图示意的图中的边是有方向的
比方 0 ->1, 不能保障肯定能够 1 ->0, 要依据方向来定，比方下图就是一张有向图

带权图

带权图示意边有肯定的权重
这里的权重能够是任意你心愿示意的数据
比方间隔或者破费的工夫或者票价

图的示意

怎么在程序中示意图呢？
咱们晓得一个图蕴含很多顶点，另外蕴含顶点和顶点之间的连线（边）
这两个都是十分重要的图信息，因而都须要在程序中提现进去
顶点的示意绝对简略，咱们先探讨顶点的示意
下面的顶点，咱们形象成 1 2 3 4，也能够形象成 A B C D
在前面的案例中，咱们应用 A B C D
那么这些 A B C D 咱们能够应用一个数组来存储起来（存储所有的顶点）
当然 A B C D 有可能还示意其余含意的数据（比方村庄的名字）
那么边如何示意呢？
因为边是两个顶点之间的关系，所以示意起来会略微麻烦一些

邻接表

邻接表由图中每个顶点以及和顶点相邻的顶点列表组成
这个列表有很多种形式来存储：数组 / 链表 / 哈希表都能够

图片解析
比方咱们要示意和 A 顶点有关联的顶点（边），A 和 B /C/ D 有边
那么咱们能够通过 A 找到对应的数组 / 链表 / 哈希表，再取出其中的内容即可

邻接表的问题：

邻接表计算出度是比较简单的（出度：指向他人的数量，入度: 指向本人的数量）
邻接表如果须要计算有向图的入度，那么是十分麻烦的事件
它必须结构一个逆邻接表，能力无效的计算入度，然而在开发中出度绝对用的比拟少

图的遍历思维

图的遍历思维和树的遍历思维是一样的
图的遍历意味着须要将图中每个顶点都拜访一遍，并且不能有反复的拜访
有两种算法能够对图进行遍历
广度优先搜寻（Breadth-first Search, 简称 BFS）
深度优先搜寻（Depth-First Search, 简称 DFS）
两种遍历算法都须要明确指定第一个被拜访的顶点

遍历的思维

两种算法的思维：
BFS：基于队列，入队列的顶点先被摸索
DFS: 基于栈或应用递归，通过将顶点存入栈中，顶点是沿着门路被摸索的，存在新的相邻顶点就去拜访

为了记录顶点是否被拜访过，咱们同时应用三种色彩来反映他们的状态：
红色：示意该顶点还没有被拜访过
灰色：示意该顶点被拜访过，但未被摸索过
彩色：示意该顶点被拜访过且被齐全摸索过

广度优先搜寻

广度优先搜索算法思路：
广度优先算法会从指定的第一个顶点开始遍历图，先拜访其所有的相邻节点，就像一次拜访图的一层，换句话说，就是先宽后深的拜访顶点

深度优先搜寻思路：

深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着门路晓得这条路经最初被拜访了。
接着原路回退并摸索下一条门路

代码实现

class Graph {constructor() {this.vertexes = [];
    this.edges = [];}
  // 增加顶点
 addVertex(v) {this.vertexes.push(v);
    this.edges[v] = [];}
  // 增加边
 addEdge(v1, v2) {this.edges[v1].push(v2);
    this.edges[v2].push(v1);
  }
  //  toString
 toString() {
    let resString = '';
    for (let i = 0; i < this.vertexes.length; i++) {let v = this.vertexes[i];
      resString += v + '->';
      for (let j = 0; j < this.edges[v].length; j++) {resString += this.edges[v][j]
      }
      resString += 'n'
 }
    return resString;
  }
  // 初始化色彩
 initColors() {let colors = [];
    for (let i = 0; i < this.vertexes.length; i++) {let v = this.vertexes[i];
      for (let j = 0; j < this.edges[v].length; j++) {colors[this.edges[v][j]] = 'white'
 }
    }
    return colors;
  }
  // 广度遍历 bfs bfs(v, handler) {let colors = this.initColors();
    let items = [];
    items.push(v);
    colors[v] = 'gray';
    while (items.length > 0) {let headData = items.shift();
      for (let i = 0; i < this.edges[headData].length; i++) {let e = this.edges[headData][i];
        if (colors[e] == 'white') {colors[e] = 'gray';
          items.push(e)
        }
      }
      handler(headData)
      colors[v] = 'black';
    }
  }
  //  dfs 深度遍历
 dfs(v, handler) {let colors = this.initColors();
    this.dfsSearch(v, handler, colors)
  }
  dfsSearch(v, handler, colors) {colors[v] = 'gray';
    handler(v);
    colors[v] = 'black';
    for (let i = 0; i < this.edges[v].length; i++) {let e = this.edges[v][i];
      if (colors[e] == 'white') {this.dfsSearch(e, handler, colors)
      }
    }
  }
}

代码测试

let graph = new Graph();
// 增加顶点操作
let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
myVertexes.forEach(v => graph.addVertex(v));
// 增加边操作
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('E', 'I');
//toString 办法测试
alert(graph.toString());
 // 深度遍历测试
let resString = '';
graph.dfs(myVertexes[0], function (key) {resString += key + ' '})
alert(resString)
// 广度遍历测试
let resString1 = '';
graph.bfs(myVertexes[0], function (key) {resString1 += key + ' '})
alert(resString1)