JavaScript数据结构-19.拓扑排序

  1 <!DOCTYPE html>
  2 <html>
  3     <head>
  4         <meta charset="UTF-8">
  5         <title>拓扑排序</title>
  6     </head>
  7     <body>
  8         <script>
  9             function topSort(){
 10                 var stack = [];
 11                 var visited = [];
 12                 for(var i=0;i<this.vertices;i++){
 13                     visited[i] = false;
 14                 }
 15                 for(var i = 0;i<this.vertices;i++){
 16                     if(visited[i] == false){
 17                         this.topSortHelper(i,visited,stack);                        
 18                     }
 19                 }
 20                 for(var i = 0;i<stack.length;i++){
 21                     if(stack[i] != undefined && stack[i] != false){
 22                         console.log(this.vertexList[stack[i]]);
 23                     }
 24                 }
 25             }
 26             function topSortHelper(v,visited,stack){
 27                 visited[v] = true;
 28                 for (var k in this.adj[v]){
 29                     var w = this.adj[v][k];
 30                     if(!visited[w]){
 31                         this.topSortHelper(visited[w],visited,stack);
 32                     }
 33                 }
 34                 stack.push(v);
 35             }
 36             
 37             function addEdge(v,w){
 38                 this.adj[w].push(v);
 39                 this.adj[v].push(w);
 40                 this.edges++;
 41             }
 42             
 43             function showGraph(){
 44                 var visited = [];
 45                 for(var i = 0;i<this.vertices;i++){
 46                     console.log(this.vertexList[i]+"->");
 47                     visited.push(this.vertexList[i]);
 48                     for(var j = 0;j < this.vertices;j++){
 49                         if(this.adj[i][j] != undefined){
 50                             if(visited.indexOf(this.vertexList[j]) < 0){
 51                                 console.log(this.vertexList[j]+" ");
 52                             }
 53                         }
 54                     }
 55                     visited.pop();
 56                 }
 57             }
 58             
 59             //深度优先搜索
 60             function dfs(v){
 61                 this.marked[v] = true;
 62                 //输出一下 
 63                 if(this.adj[v] != undefined){
 64                     console.log("已访问 ："+v);
 65                 }
 66                for(var i = 0;i<this.adj[v].length;i++){
 67                        var w = this.adj[v][i];
 68                        if(!this.marked[w]){
 69                         this.dfs(w);
 70                       }
 71                 }
 72             }
 73             
 74             //广度优先
 75             function bfs(s){
 76                 var queue = [];
 77                 this.marked[s] = true;
 78                 queue.unshift(s);
 79                 while(queue.length > 0){
 80                     var v = queue.shift();
 81                     if(typeof(v) != 'string'){
 82                         console.log("已访问 ："+v);
 83                     }
 84                     for(var k in this.adj[v]){            
 85                         var w = this.adj[v][k];
 86                         if(!this.marked[w]){
 87                             this.edgeTo[w] = v;
 88                             this.marked[w] = true;
 89                             queue.unshift(w);
 90                         }
 91                     }
 92                 }        
 93             }
 94         
 95             function pathTo(v){
 96                 var source = 0;
 97                 if(!this.hasPathTo(v)){
 98                     return undefined;
 99                 }
100                 var path = [];
101                 for(var i = v;i != source;i=this.edgeTo[i]){
102                     path.push(i);
103                 }
104                 path.push(source);
105                 return path;
106             }
107             function hasPathTo(v){
108                 return this.marked[v];
109             }
110             function Graph(v){
111                 this.vertices = v;
112                 this.vertexList = [];
113                 this.edges = 0;
114                 this.adj = [];
115                 for(var i=0;i<this.vertices;i++){
116                     this.adj[i] = [];
117                 }
118                 this.addEdge = addEdge;
119                 this.showGraph = showGraph;
120                 this.dfs = dfs;
121                 this.edgeTo = [];
122                 this.marked = [];
123                 for(var i=0;i<this.vertices;i++){
124                     this.marked[i] = false;
125                 }
126                 this.bfs = bfs;
127                 this.hasPathTo = hasPathTo;
128                 this.topSortHelper = topSortHelper;
129                 this.topSort = topSort;
130             }
131             
132             
133             //测试
134             var obj = new Graph(6);
135             obj.addEdge(1,2);
136             obj.addEdge(2,5);
137             obj.addEdge(1,3);
138             obj.addEdge(1,4);
139             obj.addEdge(0,1);
140             obj.vertexList = ["css1","css2","data structures","javascript","operating system","html"];
141             obj.showGraph();
142             obj.topSort();
143         </script>
144     </body>
145 </html>