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
int[][] matrix = {
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
// Expected output adjacency list
Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
for (int i = 0; i < matrix.length; i++) {
List<Integer> neighbors = new ArrayList<>();
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 1) {
neighbors.add(j);
}
}
adjacencyList.put(i, neighbors);
}
System.out.println(adjacencyList);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.