JavaScript數(shù)據(jù)結(jié)構(gòu)15——圖的廣度優(yōu)先遍歷

用鄰接矩陣存儲時

//圖的廣度優(yōu)先遍歷
//用鄰接矩陣存儲一個圖
//頂點
function Vertex(name) {
  this.name =name;
}
//鄰接矩陣
//maxvex:頂點數(shù)
//arcnum:邊數(shù)
function arc(maxvex,arcnum){
  this.maxvex = maxvex;
  this.arcnum = arcnum;
  this.data = new Array(maxvex);
  for (var i = 0; i < this.data.length; i++) {
    this.data[i] = new Array(maxvex);
    for (var j = 0; j < this.data[i].length; j++) {
      this.data[i][j] = Infinity;
      if(i==j){
        this.data[i][j] = 0;
      }
    }
  }
}
//圖
function Mgraph(maxvex,arcnum,vertexs){
  this.arc = new arc(maxvex,arcnum);
  this.vertexs = vertexs;
}
//添加邊
Mgraph.prototype.addArc = function(start,end,length){
  var i = this.vertexs.indexOf(start);
  var j = this.vertexs.indexOf(end);
  this.arc.data[i][j] = length;
  this.arc.data[j][i] = length;
}
//循環(huán)隊列
function Queue(maxSize) {
    this.data = new Array(maxSize);
    this.front = 0;//頭指針
    this.rear = 0;//尾指針
    this.maxSize = maxSize;
}
//長度
Queue.prototype.length = function(){
    return (this.rear-this.front+this.maxSize)%this.maxSize;
}
Queue.prototype.enterQueue = function(data){
    if((this.rear+1)%this.maxSize==this.front){
        //滿
        return 1;
    }
    console.info('入隊列'+data.name);
    this.data[this.rear] = data;
    this.rear = (this.rear+1)%this.maxSize;
    return 0;
}
Queue.prototype.deleteQueue = function(){
    if(this.front == this.rear){
        //空
        return 1;
    }
    var data = this.data[this.front];
    console.info('出隊列'+data.name);
    this.front = (this.front+1)%this.maxSize;
    return data;
}
//建造一個
var v0 = new Vertex('V0');
var v1 = new Vertex('V1');
var v2 = new Vertex('V2');
var v3 = new Vertex('V3');
var v4 = new Vertex('V4');
var vertexs = [v0,v1,v2,v3,v4];
var mgraph = new Mgraph(5,6,vertexs);
 mgraph.addArc(v1,v0,9);
 mgraph.addArc(v1,v2,3);
 mgraph.addArc(v2,v3,5);
 mgraph.addArc(v3,v4,1);
 mgraph.addArc(v0,v4,6);
 mgraph.addArc(v2,v0,2);
 console.info(mgraph.arc);
 Mgraph.prototype.BFSTraverse = function(){
    //需要使用隊列系統(tǒng)輔助完成
    var q = new Queue(this.arc.maxvex);
    for (var i = 0; i < this.arc.maxvex; i++) {
      this.vertexs[i].visited = false;
    }
    for (var i = 0; i < this.arc.maxvex; i++) {
      if(!this.vertexs[i].visited){
        this.vertexs[i].visited = true;
        q.enterQueue(this.vertexs[i]);
        while(q.length()){
          var data = q.deleteQueue();
          i = this.vertexs.indexOf(data);
          for (var j = 0; j <this.arc.maxvex; j++) {
            if(this.arc.data[i][j]>1&&this.arc.data[i][j]<Infinity
              &&!this.vertexs[j].visited){
              this.vertexs[j].visited = true;
              q.enterQueue(this.vertexs[j]);
            }
          }
        }
      }
    }
 }
 mgraph.BFSTraverse();

輸出

arc {
maxvex: 5,
arcnum: 6,
data:
[ [ 0, 9, 2, Infinity, 6 ],
[ 9, 0, 3, Infinity, Infinity ],
[ 2, 3, 0, 5, Infinity ],
[ Infinity, Infinity, 5, 0, 1 ],
[ 6, Infinity, Infinity, 1, 0 ] ] }
入隊列V0
出隊列V0
入隊列V1
入隊列V2
入隊列V4
出隊列V1
出隊列V2
入隊列V3
出隊列V4
出隊列V3
[Finished in 0.1s]

用鄰接表存儲的時候

//圖的廣度優(yōu)先遍歷
//圖的鄰接表
//頂點
function Vertex(name) {
  this.name =name;
}
//邊
function EdgeNode(weight,adjVex){
  this.weight = weight;
  this.adjVex = adjVex;
}
//圖
function Graph(vertexs){
  this.vertexs = vertexs;
}
//循環(huán)隊列
function Queue(maxSize) {
    this.data = new Array(maxSize);
    this.front = 0;//頭指針
    this.rear = 0;//尾指針
    this.maxSize = maxSize;
}
//長度
Queue.prototype.length = function(){
    return (this.rear-this.front+this.maxSize)%this.maxSize;
}
Queue.prototype.enterQueue = function(data){
    if((this.rear+1)%this.maxSize==this.front){
        //滿
        return 1;
    }
    console.info('入隊列'+data.name);
    this.data[this.rear] = data;
    this.rear = (this.rear+1)%this.maxSize;
    return 0;
}
Queue.prototype.deleteQueue = function(){
    if(this.front == this.rear){
        //空
        return 1;
    }
    var data = this.data[this.front];
    console.info('出隊列'+data.name);
    this.front = (this.front+1)%this.maxSize;
    return data;
}
var v0 = new Vertex('V0');
var v1 = new Vertex('V1');
var v2 = new Vertex('V2');
var v3 = new Vertex('V3');
var v4 = new Vertex('V4');
var edge1 = new EdgeNode(6,v4);
var edge2 = new EdgeNode(9,v0);
var edge3 = new EdgeNode(2,v0);
var edge4 = new EdgeNode(4,v1);
var edge5 = new EdgeNode(3,v2);
var edge6 = new EdgeNode(5,v3);
v0.firstEdge = edge1;
v1.firstEdge = edge2;
v2.firstEdge = edge3;
v3.firstEdge = edge4;
edge2.next = edge5;
edge3.next = edge6;
var vertexs = [v0,v1,v2,v3,v4];
var g = new Graph(vertexs);
console.info(g.vertexs);
Graph.prototype.BFSTraverse = function(){
  for (var i = 0; i < this.vertexs.length; i++) {
    this.vertexs[i].visited = false;
  }
  var q = new Queue(this.vertexs.length);
  var p;
  for (var i = 0; i < this.vertexs.length; i++) {
    if(!this.vertexs[i].visited){
      this.vertexs[i].visited = true;
      q.enterQueue(this.vertexs[i]);
      while(q.length()){
        q.deleteQueue();
        p = this.vertexs[i].firstEdge;
        while(p){
          if(p.adjVex&&!p.adjVex){
            p.adjVex.visited = true;
            q.enterQueue(p.adjVex);
          }
          p = p.next;
        }
      }
    }
  }
}
g.BFSTraverse();

輸出

[ Vertex {
name: 'V0',
firstEdge: EdgeNode { weight: 6, adjVex: [Object] } },
Vertex {
name: 'V1',
firstEdge: EdgeNode { weight: 9, adjVex: [Object], next: [Object] } },
Vertex {
name: 'V2',
firstEdge: EdgeNode { weight: 2, adjVex: [Object], next: [Object] } },
Vertex {
name: 'V3',
firstEdge: EdgeNode { weight: 4, adjVex: [Object] } },
Vertex { name: 'V4' } ]
入隊列V0
出隊列V0
入隊列V1
出隊列V1
入隊列V2
出隊列V2
入隊列V3
出隊列V3
入隊列V4
出隊列V4
[Finished in 0.1s]

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末纬霞,一起剝皮案震驚了整個濱河市胶滋,隨后出現(xiàn)的幾起案子泛豪,更是在濱河造成了極大的恐慌淮悼,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,126評論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件窒盐,死亡現(xiàn)場離奇詭異彤蔽,居然都是意外死亡屁桑,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評論 3 400
  • 文/潘曉璐 我一進店門赵讯,熙熙樓的掌柜王于貴愁眉苦臉地迎上來盈咳,“玉大人,你說我怎么就攤上這事边翼∮阆欤” “怎么了?”我有些...
    開封第一講書人閱讀 169,941評論 0 366
  • 文/不壞的土叔 我叫張陵组底,是天一觀的道長丈积。 經(jīng)常有香客問我,道長债鸡,這世上最難降的妖魔是什么江滨? 我笑而不...
    開封第一講書人閱讀 60,294評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮厌均,結(jié)果婚禮上唬滑,老公的妹妹穿的比我還像新娘。我一直安慰自己棺弊,他們只是感情好晶密,可當(dāng)我...
    茶點故事閱讀 69,295評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著镊屎,像睡著了一般惹挟。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上缝驳,一...
    開封第一講書人閱讀 52,874評論 1 314
  • 那天连锯,我揣著相機與錄音,去河邊找鬼用狱。 笑死运怖,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的夏伊。 我是一名探鬼主播摇展,決...
    沈念sama閱讀 41,285評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼溺忧!你這毒婦竟也來了咏连?” 一聲冷哼從身側(cè)響起盯孙,我...
    開封第一講書人閱讀 40,249評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎祟滴,沒想到半個月后振惰,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,760評論 1 321
  • 正文 獨居荒郊野嶺守林人離奇死亡垄懂,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,840評論 3 343
  • 正文 我和宋清朗相戀三年骑晶,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片草慧。...
    茶點故事閱讀 40,973評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡桶蛔,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出漫谷,到底是詐尸還是另有隱情仔雷,我是刑警寧澤,帶...
    沈念sama閱讀 36,631評論 5 351
  • 正文 年R本政府宣布抖剿,位于F島的核電站朽寞,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏斩郎。R本人自食惡果不足惜脑融,卻給世界環(huán)境...
    茶點故事閱讀 42,315評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望缩宜。 院中可真熱鬧肘迎,春花似錦、人聲如沸锻煌。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽宋梧。三九已至匣沼,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間捂龄,已是汗流浹背释涛。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評論 1 275
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留倦沧,地道東北人唇撬。 一個月前我還...
    沈念sama閱讀 49,431評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像展融,于是被迫代替她去往敵國和親窖认。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,982評論 2 361

推薦閱讀更多精彩內(nèi)容