概念
图是一种非线性结构，是由一组由顶点和边连接而成的。相对于二叉树更复杂些。图在日常生活中和编程中很常见，比如我们坐飞机的航班信息，导航中路径分析与计算等都是由图的数据结构组成的。如下所示就是一个图的数据结构图：
图.png
顶点
顶点是图形组成的基本元素，如图所示，A,B,C,D,E,F,G都表示顶点。
边
顶点与顶点之前的连线叫作边，由一条边连接在一起的顶点称为相邻顶点，一个顶点的度是其相邻顶点的数量，比如C和其他5个顶点相连，C的度为5。
路径
路径是指从点到点连续序列，如图所示，A到E的路径为ABE。
有向图和无向图
图可以分为有向图和无向图，如上图所示的图形为无向图，如果包含方向的前头就为有向图，如下所示：
有向图.png
图的表示
在数据结构中，我们有很多种表示图形的方法，最常见的主要包括邻接矩阵、邻接表。
邻接矩阵
邻接矩阵是通过使用一个二维数组来表示顶点之间的连接，如果索引为i的顶点与索引为j的顶点邻，则array[i][j]=1,如果不相邻，则array[i][j]=0。邻接矩阵如下所示：
邻接矩阵.png
邻接表
邻接表是由图中每个顶点的相信顶点列表所组成，可以通过数组、链表、字典等数据结构来表示，下图展示了邻接表的数据结构：
邻接表.png
根据每一个顶点，可以找到相邻的顶点。
代码展示
下面通过代码展示来创建图形类，添加顶点和边，该示例的代码主要使用邻接来来展示，通过一个数组 vertices来保存顶点，通过一个字典adjList来保存边如下所示：
function Graph() {
var vertices = [];//用于保存顶点
var adjList = [];//用于保存边，以顶点作为Key
/*
* 添加顶点
* */
this.addVertex = function (v) {
vertices.push(v);
adjList[v] = [];
}
this.addEdge = function (v,w) {
//无向图
adjList[v].push(w);
adjList[w].push(v);
}
this.print = function () {
var result = '';
for (var i = 0;i<vertices.length;i++){
var v = vertices[i];
var edges = adjList[v];
result += v
result += "-->"
if(edges){
for (var j = 0;j<edges.length;j++){
result += edges[j];
result += " ";
}
}
result += "\n";
}
console.log(result);
}
}
图的遍历
图的遍历比遍历链表、二叉树要复杂很多，这里主要介绍两种方法，广度优先搜索（BFS）和深度优先搜索（DFS）。图的遍历主要要包括查找特点的顶点，查找两个顶点之前的路径，检查图是否有环等。要进行图的遍历，首先要了解这两种搜索算法的遍历算法，其核心思想是首先要找到一个初次访问的点，然后找到与该点相邻的顶点，再对每个顶点进行搜索。在搜索时，通过对顶点进行标记来记录是否搜索过，主要通过白色，灰色、红色来标记：
白色：表示该顶点还没被访问过。
灰色：表示该顶点被访问过，但没有被探索过。
红色：表示该顶点被访问过，且被完全搜索过。
广度优先
广度优先搜索是指从第一个顶点开始遍历图结构，先访问相邻的顶点，然后再一层一层的往下访问。将最上层的顶点作为V来实现广度优先算法。
1.首先创建一个队列Q
2.将V压入队列Q中。并将所有的顶点默认设置为白色
3.判断队列是否为空。
a.将U从队列中取出
b.将U的颜色设置为灰色
c.将U的邻接点入队
d.将U设置为黑色
具体代码如下所示：
/*
* 初始化颜色
* */
var initColor = function () {
var color = [];
for(var i = 0;i<vertices.length;i++){
var key = vertices[i];
color[key] = 'white';
}
return color;
}
/*
* 广度优先搜索
* */
this.bfs = function (v,callback) {
var color = initColor();
var queue = new Queue();
queue.enqueue(v);
while (!queue.isEmpty()) {//一直判断队列是否为空
var u = queue.dequeue();
var edges = adjList[u];
color[u] = 'gray';//访问过了
if(edges && edges.length > 0){
for(var i = 0;i<edges.length;i++){//遍历所有的邻接点
var value = edges[i];
if(color[value] === 'white'){
queue.enqueue(value);
color[value] = 'gray';//未被访问过的顶点在入除后时标记为灰色
}
}
color[u] = 'black';
if(callback){
callback(u);
}
}
}
}
深度优先
深度优先搜索算法是从第一个指定的顶点开始遍历图，沿着路径直到最后一个顶点被访问了，再按着原路回退并搜索下一条路径。深度优先搜索算法不需要指定一个源顶点，只要出现未访问的顶点，则开始访问该顶点，搜索步骤如下所示：
1.标注顶点v是被发现的，并标记为灰色
2.将邻接点记为w,再访问顶点w
3.标记v为已被探索过的
/*
* 深度优先搜索
* */
this.dfs = function (v,callback){
var color = initColor();
for(var i = 0;i<vertices.length;i++){
var value = vertices[i];
if(color[value] === 'white'){
dfsVisit(value,color,callback)
}
}
};
var dfsVisit = function (v,color,callback) {
color[v] = 'gray';
if(callback){
callback(v);
}
var edgs = adjList[v];
for(var i = 0;i<edgs.length;i++){
var w = edgs[i];
if(color[w] === 'white'){
dfsVisit(w,color,callback);
}
}
color[v] = 'black';
}
网友评论