数据结构图类graph()
前言:利用图类数据结构,可以运用到GPS,google地图等需要计算最短路径的算fa中。
1,一个图G = (V, E)由以下元素组成。
V:一组顶点
E:一组边,连接V中的顶点
2,图的表示:邻接矩阵,邻接表,关联矩阵。
邻接矩阵: array[A][B]==1,两点相邻为1;
邻接表:列出所有的点,和每个点相邻的写在这个点旁边;
关联矩阵:行表示顶点,列表示边。
3,创建图类:使用数组(点)和字典(邻接表【顶点(键),邻接点(值)】)
function Graph(){
var vertices=[ ];
var adjList=new dictionary();
}
添加顶点和带键邻接表:
this.addVertax=function(v){
vertices.push(v);
adjList.set(v, [ ]);
}
添加邻接表值:
this.addEdge=function(v,w){
adjList.get(v).push(w);
adjList.get(w).push(v);
}
将图表化作可视的字符串:
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[i]+' ';
}
s+='\n';
}return s;}
4, 图的遍历:广度优先搜索,深度优先搜索;
遍历的中心思想:图的顶点已经被我们存储到私有的属性vertices[ ]数组中了;初始化,将每个点设置成同一种颜色,然后指定一个顶点开始访问,为了避免重复访问,根据点的颜色判断是否继续访问这个点;
被访问:已经将此顶点加入数组,没有将其邻接顶点加入字典;
被探索过:已经将此顶点加入数组,并且将其邻接顶点加入了字典;
用三种颜色表示它们的状态:
白色:表示该顶点还没有被访问。
灰色:表示该顶点被访问过,但并未被探索过。
黑色:表示该顶点被访问过且被完全探索过。
广度优先搜索:将点存储到队列中
-------------------------------------------------广度优先搜索-----------------------------------------------------
广度优先搜索:
创建一个颜色数组,顶点名作为color[ A ]参数,因为之前将图存储于字典中,遍历字典将所有的顶点,color[ ]都设置为白色。
------------------------------------------------------------------------------------------------------------------------
申请一个队列,将一个顶点压入队列,赋予变量u值为队列的第一个顶点且将这个顶点弹出队列,把颜色搞成灰色,从字典遍历这个顶点的邻接点,若邻接点中有白色的,则将这个点搞成灰色的,并将这个点压入队列中,遍历完毕将第一个顶点改成黑色。继续将队列的第一个点弹出栈,赋给变量u......
var initializeColor=function(){
var color=[ ];
for(var i=0;i<vertices.length;i++){
color[vertices[i ]]='white';
}
return color;}
-------------------------------------------------------------------------------------------------------
this.bfs=function(v, callback){
var color=initializeColor();
var queue=new queue(); //申请队列(先进先出)
queue.enqueue(v); //压入第一个点v
while(!queue.isEmpty()){
var u=queue.dequeue(); //弹出队列中第一个点
var neighbors=adjList.get(u);
for(var i=0;i<neightbors.length;i++){
var w=neightbors[i];
if(color[w]=="white"){ //如果是白色
color[w]=="grey";
queue.enqueue(w); //将邻接点全部压入队列
}
color[u]="black";
}
if(callback){
callback(v);
} }
};
callback函数可以自己定义功能:
function printNode(value){
console.log('Visited vertex: ' + value);
}
graph.bfs(myVertices[0], printNode); //测试
-----------------------------------------------------------------------------------------------------
广度优先搜索的使用:使用BFS寻找最短路径 (给定一个图G和源顶点v,找出对每个顶点u,u和v之间最短路径的距离)
this.BFS=function (v){
var color=initializeColor();
var queue=new queue;
queue.enqueue(v);
var d=[ ]; //定义用于盛放距离的数组
var pred=[ ]; //定义用于盛放每个字母前一个字母发数组
for(var i=0;i<vertices.length;i++){
d[vertices[i]]=0; //初始化都为0
pred[vertices[i]]=null;
}
while(!queue.isEmpty()){
var u=queue.dequeue();
color[u]="gray";
var neightbors=adjList.get(u);
for(var i=0;i<neightbors.length;i++){
var w=neightbors[i];
if(color[w]=="white"){
color[w]="grey";
queue.enqueue(w);
d[w]=d[u]+1; //每增加一个点距离加1;
pred[w]=u;
}
color[u]="black";
}}
return { //返回数组
distance: d,
predecessors:pred
};
}
调用一下函数:
var myVertices = ['A','B','C','D','E','F','G','H','I'];
var shortestPathA = graph.BFS(myVertices[0]);
console.log(shortestPathA);
理论上将输出:
distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3],
predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G:"C", H: "D", I: "E"]
我还想知道顶点A到其他点的最短路径(并且让它打印出来):
将预定义的数组里的点用for循环遍历,每个点被遍历的时候,都要申请一个栈,将这个点的前一个点按顺序放到栈里,(前面一个函数已经打印出了predecessors[ ]数组,盛放的就是每个点的前一个点的啥名字),放完了就让它们弹出pop栈,因为栈是先进后出,所以第一个被放入栈的终点将会最后一个弹出,在弹出的时候,用字符串拼接起来就行了。
var forvertex=myVertices[0];
for(var i=1;i<myVertices.length;i++){
var path=new stack();
for(var v=myVertices[i];v!=myVertices[0];v=shortestPathA.predecessors[v]){ //遍历到点D时,不停的寻找点D的前一个点
path.push(v) // 将这些点按顺序压入栈
}
var s=forvertex;
while(!path.isEmpty()){
s+="-" +path.pop(); //将这些点按顺序弹出栈,构成路径;
}
console.log(s);
}