chat-gptにきいたらおしえてくれた
参考動画
<html lang="en">
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.5.0/p5.js"></script>
<div id="p5canvas"></div>
<script>
class Graph {
constructor() {
this.vertices = [];
this.edges = [];
}
addVertex(x, y) {
this.vertices.push({ x, y });
}
addEdge(source, destination, weight) {
if (this.vertices[source] && this.vertices[destination]) {
this.edges.push({ source, destination, weight });
} else {
throw new Error("Invalid vertex");
}
}
find(parents, vertex) {
if (parents[vertex] === -1) {
return vertex;
}
return this.find(parents, parents[vertex]);
}
union(parents, x, y) {
const xRoot = this.find(parents, x);
const yRoot = this.find(parents, y);
parents[xRoot] = yRoot;
}
kruskalWithSteps() {
const mst = [];
const parents = Array(this.vertices.length).fill(-1);
this.edges.sort((a, b) => a.weight - b.weight);
for (let i = 0; i < this.edges.length; i++) {
console.log("step",i);
const { source, destination, weight } = this.edges[i];
const sourceRoot = this.find(parents, source);
const destinationRoot = this.find(parents, destination);
if (sourceRoot !== destinationRoot) {
mst.push({ source, destination, weight });
this.union(parents, sourceRoot, destinationRoot);
}
console.log("Step:", i + 1);
console.log("Minimum Spanning Tree:", mst);
console.log("====================");
}
return mst;
}
findSingletonVertices(mstEdges,start,goal) {
const vertexCount = new Map();
for (const edge of mstEdges) {
vertexCount.set(edge.source, (vertexCount.get(edge.source) || 0) + 1);
vertexCount.set(edge.destination, (vertexCount.get(edge.destination) || 0) + 1);
}
const singletonVertices = [];
for (const [vertex, count] of vertexCount) {
if (count === 1 && vertex !== start && vertex !== goal) {
singletonVertices.push(vertex);
}
}
return mstEdges.filter(edge => !singletonVertices.includes(edge.source) && !singletonVertices.includes(edge.destination));
//return singletonVertices;
}
removeEdgesConnectedToVertices(edges, vertices) {
return edges.filter(edge => !vertices.includes(edge.source) && !vertices.includes(edge.destination));
}
}
function getRandomInt(max) {
return Math.floor(Math.random() * max);
}
// 使用例
let graph ;
let mstEdges ;
let singletonVertices;
let remainingEdges;
let startVertex ;
let endVertex ;
let hubVertices ;
const vtx=[50,200,350,500,125,275,425,125,275,425];
const vty=[150,150,150,150,75,75,75,225,225,225];
const edges=[
[0,1,5],[1,2,5],[2,3,5],
[4,5,5],[5,6,5],[7,8,5],[8,9,5],
[0,4,5],[0,7,5],[1,4,5],[1,7,5],
[1,5,5],[1,8,5],[2,5,5],[2,8,5],
[2,6,5],[2,9,5],[3,6,5],[3,9,5],
];
function runKruskal(){
graph = new Graph();
for(let i=0;i<vtx.length;i++){
graph.addVertex(vtx[i], vty[i]);
}
for(let i=0;i<edges.length;i++){
graph.addEdge(edges[i][0],edges[i][1],getRandomInt(10)+1);
}
startVertex = 0;
endVertex = 3;
mstEdges = graph.kruskalWithSteps(graph.kruskalWithSteps());
remainingEdges = graph.findSingletonVertices(mstEdges,startVertex,endVertex);
mstEdges.forEach(edge => {
console.log(`Source: ${edge.source}, Destination: ${edge.destination}, Weight: ${edge.weight}`);
});
console.log(singletonVertices);
console.log(remainingEdges);
}
function setup() {
createCanvas(550, 500).parent("p5canvas");
textSize(17);
runKruskal();
}
function mousePressed() {
runKruskal();
}
function draw() {
background(100);
stroke(255, 255, 155);
strokeWeight(1);
for(let i=0;i<graph.vertices.length;i++){
fill(255);
circle(graph.vertices[i].x,graph.vertices[i].y,15);
}
for(let i=0;i<graph.edges.length;i++){
let snum=graph.edges[i].source;
let dnum=graph.edges[i].destination;
let x1=graph.vertices[snum].x;
let y1=graph.vertices[snum].y;
let x2=graph.vertices[dnum].x;
let y2=graph.vertices[dnum].y;
line(x1,y1,x2,y2);
}
for(let i=0;i<graph.vertices.length;i++){
fill(255);
text(i,graph.vertices[i].x,graph.vertices[i].y-10);
}
stroke(0, 0, 255);
fill(255,255,255);
for(let i=0;i<graph.edges.length;i++){
let snum=graph.edges[i].source;
let dnum=graph.edges[i].destination;
let x1=graph.vertices[snum].x;
let y1=graph.vertices[snum].y;
let x2=graph.vertices[dnum].x;
let y2=graph.vertices[dnum].y;
text(graph.edges[i].weight,(x1+x2)/2,(y1+y2)/2-10);
}
stroke(200,255,200);
strokeWeight(5);
for(let i=0;i<mstEdges.length;i++){
let snum=mstEdges[i].source;
let dnum=mstEdges[i].destination;
let x1=graph.vertices[snum].x;
let y1=graph.vertices[snum].y;
let x2=graph.vertices[dnum].x;
let y2=graph.vertices[dnum].y;
line(x1,y1,x2,y2);
}
}
</script>
</html>
0 件のコメント:
コメントを投稿