数据结构与算法JavaScript描述练习------第11章图和图算法

已于 2024-10-15 13:55:27 修改
阅读量208 收藏
点赞数 1
分类专栏： JavaScript 文章标签： javascript 算法 开发语言
于 2024-10-15 13:52:48 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/maxiumII/article/details/142940312
版权

1. 编写一个程序，测试广度优先和深度优先这两种图搜索算法哪一种速度更快。请使用不 同大小的图来测试你的程序。


function Graph(v) {
	this.vertices = v;
	this.edges = 0;
	this.adj = [];
	this.marked = [];
	this.edgeTo = [];
	for (var i = 0; i < this.vertices; i++) {
		this.adj[i] = [];
		this.marked[i] = false;
		this.edgeTo[i] = null;
	}
	this.addEdge = addEdge;
	this.showGraph = showGraph;
	this.pathTo = pathTo; 
	this.hasPathTo = hasPathTo;
	this.dfs = dfs;
	this.nonRecursiveDfs = nonRecursiveDfs;
	this.bfs = bfs;
	this.reset = reset;
}

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++) {
		console.log(i + " -> ");
		for (var j = 0; j < this.vertices; j++) {
			if (this.adj[i][j] != undefined) {
				console.log(this.adj[i][j] + ' ');
			}
		}
	}
}

function dfs(v) {
	this.marked[v] = true;
	if (this.adj[v] != undefined) {
		console.log("Visited vertex: " + v);
	}
	if (this.adj[v] && Array.isArray(this.adj[v])) {
		for (var w of this.adj[v]) {
			if (!this.marked[w]) {
				this.dfs(w);
			}
		}
	}
}

function nonRecursiveDfs(s) {
    let stack = [];
    this.marked[s] = true;
    stack.push(s);
    while (stack.length > 0) {
        let v = stack.pop();
        console.log("Visited vertex: " + v);
        for (let w of this.adj[v]) {
            if (!this.marked[w]) {
                this.marked[w] = true;
                this.edgeTo[w] = v;
                stack.push(w);
            }
        }
    }
}

function bfs(s) { 
	var queue = []; 
	this.marked[s] = true; 
	queue.push(s); 
	while (queue.length > 0) { 
		var v = queue.shift(); 
		console.log("Visisted vertex: " + v); 
		if (this.adj[v] && Array.isArray(this.adj[v])) {
			for (var w of this.adj[v]) { 
				if (!this.marked[w]) { 
					this.edgeTo[w] = v; 
					this.marked[w] = true; 
					queue.push(w); 
				} 
			}
		} 
	} 
}

function hasPathTo(v) {
	return this.marked[v];
}

function pathTo(v) {
	var source = 0;
	if (!this.hasPathTo(v)) {
		return undefined;
	}
	var path = [];
	for (var i = v; i !== source; i = this.edgeTo[i]) {
		if (this.edgeTo[i] === null) {
			console.error("Invalid edgeTo value:", i);
			return undefined;
		}
		path.push(i);
	}
	path.push(source);
	return path;
}

function reset() {
	for (var i = 0; i < this.vertices; i++) {
		this.marked[i] = false;
		this.edgeTo[i] = null;
	}
}	

function generateRandomGraph(vertices, edges) {
	var graph = new Graph(vertices);
	while (graph.edges < edges) {
		var v = Math.floor(Math.random() * vertices);
		var w = Math.floor(Math.random() * vertices);
		if (v !== w && !graph.adj[v].includes(w)) {
			graph.addEdge(v, w);
		}
	}
	return graph;
}

function benchmarkSearchAlgorithms(verticesCount, edgesCount) {
	const graph = generateRandomGraph(verticesCount, edgesCount);
    const source = 0;

    console.log("Benchmarking BFS and DFS for " + verticesCount + " vertices and " + edgesCount + " edges:");

    const startTimeBFS = performance.now();
    graph.reset();
    graph.bfs(source);
    const endTimeBFS = performance.now();
    const bfsTime = endTimeBFS - startTimeBFS;

    const startTimeDFS = performance.now();
    graph.reset();
    graph.nonRecursiveDfs(source);
    const endTimeDFS = performance.now();
    const dfsTime = endTimeDFS - startTimeDFS;

    console.log("BFS took "bfsTime.toFixed(2) + " ms");
    console.log("DFS took "dfsTime.toFixed(2) + " ms");

    if (bfsTime < dfsTime) {
        console.log('BFS is faster.');
    } else if (bfsTime > dfsTime) {
        console.log('DFS is faster.');
    } else {
        console.log('BFS and DFS are equally fast.');
    }
}

var sizes = [100, 500, 1000, 5000]; 
var densities = [1000, 5000, 10000, 50000]; 

sizes.forEach((vertices, index) => {
    benchmarkSearchAlgorithms(vertices, densities[index]);
});

2. 编写一个用文件来存储图的程序。

<!doctype html>
<html lang="en">
	<head>
		<title>Graph File Reader</title>
		<meta charset="utf-8">
	</head>
	<body>
	<h1>Graph File Reader</h1>
    <input type="file" id="fileInput" />
    <button onclick="saveGraphToFile()">Save Graph to File</button>
    <pre id="output"></pre>
	<script src = "2.js"></script>
	</body>
</html>
5 6
0 1
0 2
1 2
1 3
2 3
3 4
function Graph(v) {
	this.vertices = v;
	this.edges = 0;
	this.adj = [];
	this.marked = [];
	this.edgeTo = [];
	for (var i = 0; i < this.vertices; i++) {
		this.adj[i] = [];
		this.marked[i] = false;
		this.edgeTo[i] = null;
	}
	this.addEdge = addEdge;
	this.showGraph = showGraph;
	this.pathTo = pathTo; 
	this.hasPathTo = hasPathTo;
	this.dfs = dfs;
	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++) {
		console.log(i + " -> ");
		for (var j = 0; j < this.vertices; j++) {
			if (this.adj[i][j] != undefined) {
				console.log(this.adj[i][j] + ' ');
			}
		}
	}
}
*/
function dfs(v) {
	this.marked[v] = true;
	if (this.adj[v] != undefined) {
		console.log("Visited vertex: " + v);
	}
	if (this.adj[v] && Array.isArray(this.adj[v])) {
		for (var w of this.adj[v]) {
			if (!this.marked[w]) {
				this.dfs(w);
			}
		}
	}
}

function bfs(s) { 
	var queue = []; 
	this.marked[s] = true; 
	queue.push(s); // 添加到队尾 
	while (queue.length > 0) { 
		var v = queue.shift(); // 从队首移除 
		console.log("Visisted vertex: " + v); 
		if (this.adj[v] && Array.isArray(this.adj[v])) {
			for (var w of this.adj[v]) { 
				if (!this.marked[w]) { 
					this.edgeTo[w] = v; 
					this.marked[w] = true; 
					queue.push(w); 
				} 
			}
		} 
	} 
}

function hasPathTo(v) {
	return this.marked[v];
}

function pathTo(v) {
	var source = 0;
	if (!this.hasPathTo(v)) {
		return undefined;
	}
	var path = [];
	for (var i = v; i !== source; i = this.edgeTo[i]) {
		if (this.edgeTo[i] === null) {
			console.error("Invalid edgeTo value:", i);
			return undefined;
		}
		path.push(i);
	}
	path.push(source);
	return path;
}
  
  
function showGraph() {
	var output = '';
	for (var i = 0; i < this.vertices; i++) {
        output += `${i} -> ${this.adj[i].join(' ')}\n`;
    }
	document.getElementById('output').innerText = output;
}


function readGraphFromFile(filePath) {
    var fileInput = document.getElementById('fileInput');
    var file = fileInput.files[0];

    if (!file) {
        alert('Please select a file.');
        return;
    }

    var reader = new FileReader();

    reader.onload = function (event) {
        var data = event.target.result;
        var lines = data.split('\n').filter(line => line.trim() !== '');

        var [vertices, edges] = lines[0].split(' ').map(Number);
        var graph = new Graph(vertices);

        for (var i = 1; i <= edges; i++) {
            var [v, w] = lines[i].split(' ').map(Number);
            graph.addEdge(v, w);
        }

        graph.showGraph();
    };

    reader.onerror = function (error) {
        console.error('Error reading file:', error);
    };

    reader.readAsText(file);
}

document.getElementById('fileInput').addEventListener('change', readGraphFromFile);

function saveGraphToFile() {
    var graph = new Graph(5); 
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    var data = `${graph.vertices} ${graph.edges}\n`;
	var edgesSet = new Set();
            for (var i = 0; i < graph.vertices; i++) {
                for (var j = 0; j < graph.adj[i].length; j++) {
                    var w = graph.adj[i][j];
                    if (i < w && !edgesSet.has(`${i}-${w}`)) {
                        edgesSet.add(`${i}-${w}`);
                        data += `${i} ${w}\n`;
                    }
                }
            }

    var blob = new Blob([data], { type: 'text/plain' });
    var link = document.createElement('a');
    link.href = URL.createObjectURL(blob);
    link.download = 'graph.txt';
    link.click();
}

3. 编写一个从文件读取图的程序。

        同2

4. 构建一个图，用它为你居住地的地图建模。测试一下从一个开始顶点到最后顶点的最短路径。

function Graph(v) {
	this.vertices = v;
	this.edges = 0;
	this.adj = [];
	this.marked = [];
	this.edgeTo = [];
	for (var i = 0; i < this.vertices; i++) {
		this.adj[i] = [];
		this.marked[i] = false;
		this.edgeTo[i] = null;
	}
	this.addEdge = addEdge;
	this.showGraph = showGraph;
	this.pathTo = pathTo; 
	this.hasPathTo = hasPathTo;
	this.dfs = dfs;
	this.bfs = bfs;
	this.reset = reset;
}

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++) {
		console.log(i + " -> ");
		for (var j = 0; j < this.vertices; j++) {
			if (this.adj[i][j] != undefined) {
				console.log(this.adj[i][j] + ' ');
			}
		}
	}
}

function dfs(v) {
	this.marked[v] = true;
	if (this.adj[v] != undefined) {
		console.log("Visited vertex: " + v);
	}
	if (this.adj[v] && Array.isArray(this.adj[v])) {
		for (var w of this.adj[v]) {
			if (!this.marked[w]) {
				this.dfs(w);
			}
		}
	}
}

function bfs(s) { 
	var queue = []; 
	this.marked[s] = true; 
	queue.push(s); // 添加到队尾 
	while (queue.length > 0) { 
		var v = queue.shift(); // 从队首移除 
		console.log("Visisted vertex: " + v); 
		if (this.adj[v] && Array.isArray(this.adj[v])) {
			for (var w of this.adj[v]) { 
				if (!this.marked[w]) { 
					this.edgeTo[w] = v; 
					this.marked[w] = true; 
					queue.push(w); 
				} 
			}
		} 
	} 
}

function hasPathTo(v) {
	return this.marked[v];
}

function pathTo(v) {
	var source = 0;
	if (!this.hasPathTo(v)) {
		return undefined;
	}
	var path = [];
	for (var i = v; i !== source; i = this.edgeTo[i]) {
		if (this.edgeTo[i] === null) {
			console.error("Invalid edgeTo value:", i);
			return undefined;
		}
		path.push(i);
	}
	path.push(source);
	return path.reverse();
}

function reset() {
    for (var i = 0; i < this.vertices; i++) {
        this.marked[i] = false;
        this.edgeTo[i] = null;
    }
}

var graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 4);
graph.addEdge(4, 5);
graph.showGraph();
graph.reset();
graph.bfs(0);
var shortestPath = graph.pathTo(5);
console.log("Shortest path from 0 to 5:", shortestPath);

graph.reset();
console.log("DFS traversal:");
graph.dfs(0);
graph.reset();
console.log("BFS traversal:");
graph.bfs(0);

5. 对上一题中创建的图执行深度优先搜索和广度优先搜索。

        同4

拓扑排序：

function Graph(v) {
	this.vertices = v;
	this.vertexList = [];
	this.edges = 0;
	this.adj = [];
	this.marked = [];
	this.edgeTo = [];
	for (var i = 0; i < this.vertices; i++) {
		this.adj[i] = [];
		this.marked[i] = false;
		this.edgeTo[i] = null;
	}
	this.addEdge = addEdge;
	this.showGraph = showGraph;
	this.pathTo = pathTo; 
	this.hasPathTo = hasPathTo;
	this.dfs = dfs;
	this.bfs = bfs;
	this.topSortHelper = topSortHelper;
	this.topSort = topSort;
}

function addEdge(v, w) {
	this.adj[v].push(w);
	this.adj[w].push(v);
	this.edges++;
}

function showGraph() {
	var visited = [];
	for (var i = 0; i < this.vertices; i++) {
		console.log(this.vertexList[i] + " -> ");
		visited.push(this.vertexList[i]);
		for (var j = 0; j < this.vertices; j++) {
			if (this.adj[i][j] != undefined) {
				if (visited.indexOf(this.vertexList[j]) < 0) {
					console.log(this.vertexList[j] + ' ');
				}
				
			}
		}
		visited.pop();
	}
}

function dfs(v) {
	this.marked[v] = true;
	if (this.adj[v] != undefined) {
		console.log("Visited vertex: " + v);
	}
	if (this.adj[v] && Array.isArray(this.adj[v])) {
		for (var w of this.adj[v]) {
			if (!this.marked[w]) {
				this.dfs(w);
			}
		}
	}
}

function bfs(s) { 
	var queue = []; 
	this.marked[s] = true; 
	queue.unshift(s); 
	while (queue.length > 0) { 
		var v = queue.shift(); 
		if (typeof(v) !== 'string') {
			console.log("Visisted vertex: " + v); 
		}
		if (this.adj[v] && Array.isArray(this.adj[v])) {
			for (var w of this.adj[v]) { 
				if (!this.marked[w]) { 
					this.edgeTo[w] = v; 
					this.marked[w] = true; 
					queue.unshift(w); 
				} 
			}
		} 
	} 
}

function hasPathTo(v) {
	return this.marked[v];
}

function pathTo(v) {
	var source = 0;
	if (!this.hasPathTo(v)) {
		return undefined;
	}
	var path = [];
	for (var i = v; i !== source; i = this.edgeTo[i]) {
		if (this.edgeTo[i] === null) {
			console.error("Invalid edgeTo value:", i);
			return undefined;
		}
		path.push(i);
	}
	path.push(source);
	return path;
}

function topSort() {
	var stack = [];
	var visited = [];
	for (var i = 0; i < this.vertices; i++) {
		visited[i] = false;
	}
	for (var i = 0; i < stack.length; i++) {
		if (visited[i] === false) {
			this.topSortHelper(i, visited, stack);
		}
	}
	for (var i = 0; i < stack.length; i++) {
		if (stack[i] != undefined && stack[i] != false) {
			console.log(this.vertexList[stack[i]]);
		}
	}
}

function topSortHelper(v, visited, stack) {
	visited[v] = true;
	if (this.adj[v] && Array.isArray(this.adj[v])) {
		for (var w of this.adj[v]) {
			if (!visited[w]) {
				this.topSortHelper(visited[w], visited, stack);
			}
		}
		stack.push(v);
	}
}

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值