Master advanced graph operations including adjacency matrix, adjacency list, and various graph representations.
class GraphMatrix {
constructor(numVertices) {
this.numVertices = numVertices;
this.matrix = Array(numVertices)
.fill()
.map(() => Array(numVertices).fill(0));
}
addEdge(source, destination, weight = 1) {
// For directed graph
this.matrix[source][destination] = weight;
// For undirected graph, uncomment the line below
// this.matrix[destination][source] = weight;
}
removeEdge(source, destination) {
this.matrix[source][destination] = 0;
// For undirected graph, uncomment the line below
// this.matrix[destination][source] = 0;
}
hasEdge(source, destination) {
return this.matrix[source][destination] !== 0;
}
getNeighbors(vertex) {
const neighbors = [];
for (let i = 0; i < this.numVertices; i++) {
if (this.matrix[vertex][i] !== 0) {
neighbors.push(i);
}
}
return neighbors;
}
}
class GraphList {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(source, destination, weight = 1) {
// Add vertex if it doesn't exist
if (!this.adjacencyList[source]) {
this.addVertex(source);
}
if (!this.adjacencyList[destination]) {
this.addVertex(destination);
}
// For weighted graph, store objects with vertex and weight
this.adjacencyList[source].push({ node: destination, weight });
// For undirected graph, uncomment the line below
// this.adjacencyList[destination].push({ node: source, weight });
}
removeEdge(source, destination) {
if (this.adjacencyList[source]) {
this.adjacencyList[source] = this.adjacencyList[source]
.filter(edge => edge.node !== destination);
}
// For undirected graph, uncomment the block below
/*
if (this.adjacencyList[destination]) {
this.adjacencyList[destination] = this.adjacencyList[destination]
.filter(edge => edge.node !== source);
}
*/
}
getNeighbors(vertex) {
return this.adjacencyList[vertex]
? this.adjacencyList[vertex].map(edge => edge.node)
: [];
}
}
| Operation | Adjacency Matrix | Adjacency List |
|---|---|---|
| Add Edge | O(1) | O(1) |
| Remove Edge | O(1) | O(E) |
| Check Edge | O(1) | O(E) |
| Get All Edges | O(V²) | O(V+E) |
Implement a function that converts an adjacency matrix to an adjacency list representation.
// Input adjacency matrix
const matrix = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
];
// Expected output adjacency list
{
'0': [1, 3],
'1': [0, 2],
'2': [1, 3],
'3': [0, 2]
}Implement a function that returns all vertices reachable from a given vertex in a directed graph.
Implement a function that calculates the density of a graph (ratio of actual edges to maximum possible edges).
For a directed graph with V vertices:
Density = Number of Edges / (V * (V-1))
For an undirected graph:
Density = (2 * Number of Edges) / (V * (V-1))
Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are excellent for practicing graph representations and algorithms.