2021-01-06 17:13:52 -03:00
|
|
|
// https://en.wikipedia.org/wiki/Neighbourhood_(graph_theory)
|
|
|
|
|
|
2021-01-06 17:37:19 -03:00
|
|
|
class Graph {
|
2021-01-06 17:10:09 -03:00
|
|
|
// Generic graph: the algorithm works regardless of direction or weight
|
2023-10-03 23:08:19 +02:00
|
|
|
constructor() {
|
2021-01-06 17:10:09 -03:00
|
|
|
this.edges = []
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
addEdge(node1, node2) {
|
2021-01-06 17:10:09 -03:00
|
|
|
// Adding edges to the graph
|
|
|
|
|
this.edges.push({
|
|
|
|
|
node1,
|
|
|
|
|
node2
|
|
|
|
|
})
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
nodeNeighbors(node) {
|
2021-01-06 17:10:09 -03:00
|
|
|
// Returns an array with all of the node neighbors
|
2021-01-17 01:11:13 -03:00
|
|
|
const neighbors = new Set()
|
2021-01-18 20:56:58 -03:00
|
|
|
for (const edge of this.edges) {
|
2021-01-06 17:10:09 -03:00
|
|
|
// Checks if they have an edge between them and if the neighbor is not
|
|
|
|
|
// already in the neighbors array
|
2023-10-03 23:08:19 +02:00
|
|
|
if (edge.node1 === node && !neighbors.has(edge.node2)) {
|
2021-01-18 20:54:44 -03:00
|
|
|
neighbors.add(edge.node2)
|
2023-10-03 23:08:19 +02:00
|
|
|
} else if (edge.node2 === node && !neighbors.has(edge.node1)) {
|
2021-01-18 20:54:44 -03:00
|
|
|
neighbors.add(edge.node1)
|
2021-01-06 17:10:09 -03:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
return neighbors
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2021-10-10 17:55:08 +02:00
|
|
|
export { Graph }
|
|
|
|
|
|
|
|
|
|
// const graph = new Graph()
|
|
|
|
|
// graph.addEdge(1, 2)
|
|
|
|
|
// graph.addEdge(2, 3)
|
|
|
|
|
// graph.addEdge(3, 5)
|
|
|
|
|
// graph.addEdge(1, 5)
|
|
|
|
|
// graph.nodeNeighbors(1)
|
