|
前言：利用图类数据结构，可以运用到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;}
总体合并代码：
var graph=function(key,val,v,b){
var dictionary=function(key,val){
var node={ };
this.putin=function(key,val){
node[key]=val;
}
this.getout=function(key){
return node[key];
}
}
var point=[ ];
var diction=new dictionary();
this.setpoint=function(v){
point.push(v);
diction.putin(v,[]);
}
this.setedge=function(v,b){
diction.getout(v).push(b); //获取字典对应的点键值，设置此点的边
diction.getout(b).push(v);
}
this.tostring=function(){
var x1=point.length;
for(var i=0;i<x1;i++){
console.log(point[i]+"->");
for(var j=0;j<diction.getout(point[i]).length;j++)
console.log(diction.getout(point[i])[j]);
}
}
} //graph;
var m=new graph();
m.setpoint('A');
m.setpoint('B');
m.setedge('A','B');
m.setpoint('C');
m.setedge('A','C');
m.tostring();
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);
}
| 
转播
