javascript数据结构8-图（Graph）

发表于 | 更新于 | 分类于

图（graph）
图由边的集合及顶点的集合组成
有向图：
有向图
无向图：
这里写图片描述
代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Graph</title>
</head>
<body>
<script>
	function Graph(v){
      	this.vertices=v;
      	this.edges=0;
      	this.adj=[];
     	for(var i=0;i<this.vertices;++i){
        	this.adj[i]=[];
          // this.adj[i].push("");
      }
      	this.addEdge=addEdge;
      	this.showGraph=showGraph;
      
      //深度优先搜索
      this.dfs=dfs;
      this.marked=[];
      for(var i=0;i<this.vertices;++i){
        	this.marked[i]=false;
      }

      // 广度搜索
      this.bfs=bfs;
      	
    }
  
	//   增加顶点
  	function addEdge(v,w){
      	this.adj[v].push(w);
      	this.adj[w].push(v);
		    this.edges++;      
    }
  	
  	//遍历
  	function showGraph(){
      	for(var i=0;i<this.vertices;++i){
          	document.write('<br/>');
          	document.write(i+"-->");
          	for(var j=0;j<this.vertices;++j){
              	if(this.adj[i][j]!=undefined){
                  	document.write(this.adj[i][j]+' ');
                }
            }
        }
    }
  
  	//深度优先搜索
  	function dfs(v){
  		//var w;
  		this.marked[v]=true;
    	if(this.adj[v]!=undefined){
        	document.write("<br/>访问的节点:"+v);
      }
      // for(var w in this.adj[v]){
      //console.log(this.adj[0].length);    
          var w=this.adj[v].shift();
          while(w!=undefined){
              if(!this.marked[w]){
              	this.dfs(w);
              }
              w=this.adj[v].shift();
          }
     
          //console.log(w);
          //console.log(this.adj[v]);
    }

    // 广度搜索
    function bfs(s){
        var queue=[];
        this.marked[s]=true;
        queue.push(s);//添加到队尾
        var w;  //存放邻接表
        while(queue.length>0){

           var v=queue.shift();//从队首删除
           if(v!=undefined){
              document.write("<br/>访问的节点:"+v);
           }

             w=this.adj[v].shift();
             while(w!=undefined){
                if(!this.marked[w]){
                    this.marked[w]=true;
                    queue.push(w);
                }
                 w=this.adj[v].shift();
             }
        }
    }
  	//测试
  	var  graph=new Graph(5);
  	graph.addEdge(0,1);  
  	graph.addEdge(0,2);  
  	graph.addEdge(1,3);  
  	graph.addEdge(2,4);  
    //console.log(graph);
  	//console.log(graph.adj);
  	graph.showGraph();
    document.write("<br/>");
    document.write("======深度度优先搜索=====");
    graph.dfs(0);
    document.write("<br/>");
    document.write("======广度优先搜索=====");
    var  graph1=new Graph(5);
    graph1.addEdge(0,1);  
    graph1.addEdge(0,2);  
    graph1.addEdge(1,3);  
    graph1.addEdge(2,4);  
    graph1.bfs(0);
</script>
</body>
</html>

运行结果：

0–>1 2
1–>0 3
2–>0 4
3–>1
4–>2
======深度度优先搜索=====
访问的节点:0
访问的节点:1
访问的节点:3
访问的节点:2
访问的节点:4
======广度优先搜索=====
访问的节点:0
访问的节点:1
访问的节点:2
访问的节点:3
访问的节点:4

深度搜索的含义：
深度搜索
广度搜索的含义：
广度搜索