Graph is probably the data structure that has the closest resemblance to our daily life. There are many types of graphs describing the relationships in real life. For instance, our friend circle is a huge “graph”.
social graph of friendship
There are many types of “graphs”. In this Explore Card, we will introduce three types of graphs: undirected graphs, directed graphs, and weighted graphs.
- Undirected graphs
- Directed graphs
- Weighted graphs
The edges between any two vertices in an “undirected graph” do not have a direction, indicating a two-way relationship.
The edges between any two vertices in a “directed graph” graph are directional.
Each edge in a “weighted graph” has an associated weight. The weight can be of any metric, such as time, distance, size, etc. The most commonly seen “weighted map” in our daily life might be a city map. In Figure 3, each edge is marked with the distance, which can be regarded as the weight of that edge.
“Graph” is a non-linear data structure consisting of vertices and edges. There are a lot of terminologies to describe a graph. If you encounter an unfamiliar term in the following Explore Card, you may look up the definition below.
- Vertex: In Figure 1, nodes such as A, B, and C are called vertices of the graph.
- Edge: The connection between two vertices are the edges of the graph. In Figure 1, the connection between person A and B is an edge of the graph.
- Path: the sequence of vertices to go through from one vertex to another. In Figure 1, a path from A to C is [A, B, C], or [A, G, B, C], or [A, E, F, D, B, C].
Note: there can be multiple paths between two vertices. - Cycle: a path where the starting point and endpoint are the same vertex. In Figure 1, [A, B, D, F, E] forms a cycle. Similarly, [A, G, B] forms another cycle.
- Negative Weight Cycle: In a “weighted graph”, if the sum of the weights of all edges of a cycle is a negative value, it is a negative weight cycle. In Figure 4, the sum of weights is -3.
- Connectivity: if there exists at least one path between two vertices, these two vertices are connected. In Figure 1, A and C are connected because there is at least one path
- Degree of a Vertex: the term “degree” applies to unweighted graphs. The degree of a vertex is the number of edges connecting the vertex. In Figure 1, the degree of vertex A is 3 because three edges are connecting it.
- In-Degree: “in-degree” is a concept in directed graphs. If the in-degree of a vertex is d, there are d directional edges incident to the vertex. In Figure 2, A’s indegree is 1, i.e., the edge from F to A.
- Out-Degree: “out-degree” is a concept in directed graphs. If the out-degree of a vertex is d, there are d edges incident from the vertex. In Figure 2, A’s outdegree is 3, i,e, the edges A to B, A to C, and A to G.
- Using DFS Recursive Solution
const dfsPrint = (graph, sourceNode) => {
console.log(sourceNode);
for (const neighbor of graph[sourceNode]) {
dfsPrint(graph, neighbor);
}
};- Using DFS With Stack
const dfsPrint = (graph, sourceNode) => {
const stack = [sourceNode];
while (stack.length > 0) {
const current = stack.pop();
console.log(current);
for (const neighbor of graph[current]) {
stack.push(neighbor);
}
}
};- Using BFS With Queue
const bfs = (graph, sourceNode) => {
const queue = [sourceNode];
while (queue.length > 0) {
const current = queue.shift();
console.log(current);
for (const neighbor of graph[current]) {
queue.push(neighbor);
}
}
};- Has Path Problem Check if Graph Has Path From Source >>> Destination
const hasPathDfsStack = (graph, src, dest) => {
const stack = [src];
while (stack.length > 0) {
const currentNode = stack.pop();
if (currentNode === dest) {
return true;
}
for (const neighbor of graph[currentNode]) {
stack.push(neighbor);
}
}
return false;
};const hasPathUsingBFS = (graph, src, dest) => {
const queue = [src];
while (queue.length > 0) {
const currentNode = queue.shift();
if (currentNode === dest) {
return true;
}
for (const neighbor of graph[currentNode]) {
queue.push(neighbor);
}
}
return false;
};const hasPath = (graph, src, dest) => {
if (src === dest) {
return true;
}
for (const neighbor of graph[src]) {
if (hasPath(graph, neighbor, dest) === true) {
return true;
}
}
return false;
};- Undirected Graph Hash Path Problem Mark Visited
const undirectedPathUsingDFSRecursive = (edges, source, dest) => {
const graph = buildGraph(edges);
const visited = new Set();
return DFShasPath(graph, source, dest, visited);
};
const DFShasPath = (graph, src, dest, visited) => {
if (src === dest) return true;
if (visited.has(src)) return false;
visited.add(src);
for (const neighbor of graph[src]) {
if (DFShasPath(graph, neighbor, dest, visited)) {
return true;
}
}
return false;
};- Connected Component Problem
const connectedComponentCount = (graph) => {
const visited = new Set();
let counter = 0;
for (const node in graph) {
if (dfs(graph, Number(node), visited)) {
counter++;
}
}
return counter;
};
const dfs = (graph, currentNode, visited) => {
if (visited.has(currentNode)) return false;
visited.add(currentNode);
for (const neighbor of graph[currentNode]) {
dfs(graph, neighbor, visited);
}
return true; // The Whole Explore Done
};- Largest Component
const largestComponent = (graph) => {
const visited = new Set();
let largestSize = 0;
for (const node in graph) {
const size = exploreGrahs(graph, node, visited);
if (!size) continue;
largestSize = Math.max(largestSize, size);
}
return largestSize;
};
const exploreGrahs = (graph, node, visited) => {
if (visited.has(node)) return false;
visited.add(node);
let size = 1;
for (const neighbor of graph[node]) {
size += exploreGrahs(graph, neighbor, visited);
}
return size;
};- Shortest Path
const shortestPath = (edges, nodeA, nodeB) => {
const visited = new Set();
const queue = [[nodeA, 0]];
const graph = buildGraph(edges);
while (queue.length > 0) {
const [currentNode, distance] = queue.shift();
if (visited.has(currentNode)) continue;
visited.add(currentNode);
if (currentNode === nodeB) {
return distance;
}
for (const neighbor of graph[currentNode]) {
queue.push([neighbor, distance + 1]);
}
}
return -1;
};
const buildGraph = (edges) => {
const graph = {};
for (const [a, b] of edges) {
if (!graph[a]) graph[a] = [];
if (!graph[b]) graph[b] = [];
graph[a].push(b);
graph[b].push(a);
}
return graph;
};- Island Count
const islandCount = (grid) => {
const visited = new Set();
let islandCounter = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (dfs(grid, visited, i, j)) {
islandCounter++;
}
}
}
return islandCounter;
};
const dfs = (grid, visited, row, col) => {
const position = row + '-' + col;
if (grid[row] === undefined || grid[row][col] === undefined || grid[row][col] === 'W' || visited.has(position)) return false;
visited.add(position);
dfs(grid, visited, row + 1, col);
dfs(grid, visited, row - 1, col);
dfs(grid, visited, row, col + 1);
dfs(grid, visited, row, col - 1);
return true;
};- Minimum Island (GRID Graphs)
const minimumIsland = (grid) => {
const visited = new Set();
let minimumIslandSize = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
const size = dfs(grid, visited, i, j);
if (!size) continue;
minimumIslandSize = Math.min(size, minimumIslandSize);
}
}
return minimumIslandSize;
};
const dfs = (grid, visited, row, col) => {
const position = `${row}-${col}`;
if (grid[row] === undefined || grid[row][col] === undefined || grid[row][col] === 'W' || visited.has(position)) return false;
visited.add(position);
let size = 1;
size += dfs(grid, visited, row + 1, col);
size += dfs(grid, visited, row - 1, col);
size += dfs(grid, visited, row, col + 1);
size += dfs(grid, visited, row, col - 1);
return size;
};