Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3e0ac74

Browse files
committed
Use Infinity instead of zero in Graph adjacency matrix to show that vertices are not connected.
1 parentf966ef5 commit3e0ac74

File tree

3 files changed

+14
-15
lines changed

3 files changed

+14
-15
lines changed

‎src/algorithms/graph/hamiltonian-cycle/hamiltonianCycle.js

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ function isSafe(adjacencyMatrix, verticesIndices, cycle, vertexCandidate) {
1515
constendVertexAdjacencyIndex=verticesIndices[endVertex.getKey()];
1616

1717
// Check if last vertex in the path and candidate vertex are adjacent.
18-
if(!adjacencyMatrix[endVertexAdjacencyIndex][candidateVertexAdjacencyIndex]){
18+
if(adjacencyMatrix[endVertexAdjacencyIndex][candidateVertexAdjacencyIndex]===Infinity){
1919
returnfalse;
2020
}
2121

@@ -43,7 +43,7 @@ function isCycle(adjacencyMatrix, verticesIndices, cycle) {
4343
constendVertexAdjacencyIndex=verticesIndices[endVertex.getKey()];
4444

4545
// Check if we can go from end vertex to the start one.
46-
return!!adjacencyMatrix[endVertexAdjacencyIndex][startVertexAdjacencyIndex];
46+
returnadjacencyMatrix[endVertexAdjacencyIndex][startVertexAdjacencyIndex]!==Infinity;
4747
}
4848

4949
/**

‎src/data-structures/graph/Graph.js

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -177,18 +177,17 @@ export default class Graph {
177177
constvertices=this.getAllVertices();
178178
constverticesIndices=this.getVerticesIndices();
179179

180-
// Init matrix with zeros.
180+
// Init matrix with infinities meaning that there is no ways of
181+
// getting from one vertex to another yet.
181182
constadjacencyMatrix=Array(vertices.length).fill(null).map(()=>{
182-
returnArray(vertices.length).fill(0);
183+
returnArray(vertices.length).fill(Infinity);
183184
});
184185

185186
// Fill the columns.
186187
vertices.forEach((vertex,vertexIndex)=>{
187188
vertex.getNeighbors().forEach((neighbor)=>{
188189
constneighborIndex=verticesIndices[neighbor.getKey()];
189-
adjacencyMatrix[vertexIndex][neighborIndex]=this.isDirected ?
190-
this.findEdge(vertex,neighbor).weight :
191-
1;
190+
adjacencyMatrix[vertexIndex][neighborIndex]=this.findEdge(vertex,neighbor).weight;
192191
});
193192
});
194193

‎src/data-structures/graph/__test__/Graph.test.js

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -348,10 +348,10 @@ describe('Graph', () => {
348348

349349
constadjacencyMatrix=graph.getAdjacencyMatrix();
350350
expect(adjacencyMatrix).toEqual([
351-
[0,1,0,0],
352-
[1,0,1,1],
353-
[0,1,0,1],
354-
[0,1,1,0],
351+
[Infinity,0,Infinity,Infinity],
352+
[0,Infinity,0,0],
353+
[Infinity,0,Infinity,0],
354+
[Infinity,0,0,Infinity],
355355
]);
356356
});
357357

@@ -375,10 +375,10 @@ describe('Graph', () => {
375375

376376
constadjacencyMatrix=graph.getAdjacencyMatrix();
377377
expect(adjacencyMatrix).toEqual([
378-
[0,2,0,0],
379-
[0,0,1,7],
380-
[0,0,0,5],
381-
[0,0,0,0],
378+
[Infinity,2,Infinity,Infinity],
379+
[Infinity,Infinity,1,7],
380+
[Infinity,Infinity,Infinity,5],
381+
[Infinity,Infinity,Infinity,Infinity],
382382
]);
383383
});
384384
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp