function largestConnectedComponent(graph) {
let maxSize = 0;
const visited = new Set();
for (const node of Object.keys(graph)) {
const size = componentSize(graph, node, visited);
maxSize = Math.max(maxSize, size);
}
return maxSize;
}
function componentSize(graph, currNode, visited) {
let count = 0;
function visit(node) {
if (visited.has(node)) return;
visited.add(node);
count += 1;
for (const nbr of graph[node]) {
visit(nbr);
}
}
visit(currNode);
return count;
}
const graph = {
"0": ["8", "1", "5"],
"1": ["0"],
"5": ["0", "8"],
"8": ["0", "5"],
"2": ["3", "4"],
"3": ["2", "4"],
"4": ["3", "2"],
};
const a = largestConnectedComponent(graph);
console.log(a);
const { buildGraph } = require("./utils");
function isTherePath(graph, nodeA, nodeB) {
return hasPath(graph, nodeA, nodeB, new Set());
}
function hasPath(graph, src, dst, visited) {
if (src === dst) return true;
for (const nbr of graph.get(src)) {
if (!visited.has(nbr)) {
visited.add(nbr);
if (hasPath(graph, nbr, dst, visited)) return true;
}
}
return false;
}
module.exports = {
isTherePath,
}
/*
const edges = [
["i", "j"],
["k", "i"],
["m", "k"],
["k", "l"],
["o", "n"],
];
console.log(isTherePath(edges, "j", "m")); // true
console.log(isTherePath(edges, "j", "n")); // false
*/
function getConnectedComponentsCount(graph) {
let count = 0;
const visited = new Set();
for (const node of Object.keys(graph)) {
if (visit(graph, node, visited)) {
count += 1;
}
}
function visit(graph, node, visited) {
if (visited.has(node)) return false;
visited.add(node);
for (const nbr of graph[node]) {
visit(graph, nbr, visited);
}
return true;
}
return count;
}
module.exports = {
getConnectedComponentsCount,
}
/*
const graph = {
'1': [ '2' ],
'2': [ '1' ],
'3': [ ],
'4': [ '6' ],
'5': [ '6' ],
'7': [ '6' ],
'8': [ '6' ],
'6': [ '4', '5', '7', '8' ],
};
const count = getConnectedComponentsCount(graph);
console.log(count);
*/
function buildGraph(edges) {
const graph = new Map();
for (const [node1, node2] of edges) {
if (!graph.has(node1)) graph.set(node1, []);
if (!graph.has(node2)) graph.set(node2, []);
graph.get(node1).push(node2);
graph.get(node2).push(node1);
}
return graph;
}
module.exports = {
buildGraph,
};
function largestConnectedComponent(graph) {
let maxSize = 0;
const visited = new Set();
for (const node of Object.keys(graph)) {
const size = componentSize(graph, node, visited);
maxSize = Math.max(maxSize, size);
}
return maxSize;
}
function componentSize(graph, currNode, visited) {
let count = 0;
function visit(node) {
if (visited.has(node)) return;
visited.add(node);
count += 1;
for (const nbr of graph[node]) {
visit(nbr);
}
}
visit(currNode);
return count;
}
const graph = {
"0": ["8", "1", "5"],
"1": ["0"],
"5": ["0", "8"],
"8": ["0", "5"],
"2": ["3", "4"],
"3": ["2", "4"],
"4": ["3", "2"],
};
const a = largestConnectedComponent(graph);
console.log(a);
