A graph is a data structure more complex than linear lists and trees, consisting of vertices and edges, used to represent relationships between objects. Graphs have wide applications in computer science, such as social networks, routing algorithms, recommendation systems, etc.
Basic Concepts of Graphs
Definition of Graphs
A graph G consists of two sets:
- Vertex Set V: All vertices in the graph
- Edge Set E: Edges connecting the vertices
Represented as: G = (V, E)
Classification of Graphs
By Whether Edges Have Direction
- Undirected Graph: Edges have no direction
- Directed Graph: Edges have direction (called arcs)
By Whether Edges Have Weights
- Unweighted Graph: Edges have no weights
- Weighted Graph: Edges have weight values
Other Classifications
- Connected Graph: There is a path between any two vertices
- Disconnected Graph: There are disconnected vertices
- Complete Graph: There is an edge between any two vertices
- Sparse Graph: Number of edges much less than the square of the number of vertices
- Dense Graph: Number of edges close to the square of the number of vertices
Graph Representation Methods
Adjacency Matrix
Use a two-dimensional array to represent the connection relationships between vertices in the graph.
class Graph {
constructor(isDirected = false) {
this.vertices = []; // Vertex list
this.edges = []; // Edge list
this.adjMatrix = []; // Adjacency matrix
this.isDirected = isDirected; // Whether it is a directed graph
}
// Add vertex
addVertex(vertex) {
this.vertices.push(vertex);
// Expand adjacency matrix
for (let i = 0; i < this.adjMatrix.length; i++) {
this.adjMatrix[i].push(0);
}
this.adjMatrix.push(new Array(this.vertices.length).fill(0));
}
// Add edge
addEdge(v1, v2, weight = 1) {
const i = this.vertices.indexOf(v1);
const j = this.vertices.indexOf(v2);
if (i === -1 || j === -1) return false;
this.adjMatrix[i][j] = weight;
if (!this.isDirected) {
this.adjMatrix[j][i] = weight;
}
return true;
}
// Get edge weight
getEdgeWeight(v1, v2) {
const i = this.vertices.indexOf(v1);
const j = this.vertices.indexOf(v2);
if (i === -1 || j === -1) return undefined;
return this.adjMatrix[i][j];
}
// Print adjacency matrix
printMatrix() {
console.log("Vertices:", this.vertices.join(", "));
for (let i = 0; i < this.adjMatrix.length; i++) {
console.log(`${this.vertices[i]}: ${this.adjMatrix[i].join(" ")}`);
}
}
}
// Usage example
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B", 1);
graph.addEdge("B", "C", 2);
graph.addEdge("A", "C", 3);
graph.printMatrix();
Advantages:
- Checking if there is an edge between two vertices is very fast (O(1))
- Suitable for dense graphs
Disadvantages:
- High space complexity (O(V²))
- Wastes space for sparse graphs
Adjacency List
Use an array + linked list to store adjacent vertices for each vertex.
class GraphList {
constructor(isDirected = false) {
this.vertices = []; // Vertex list
this.adjList = new Map(); // Adjacency list
this.isDirected = isDirected; // Whether it is a directed graph
}
// Add vertex
addVertex(vertex) {
if (!this.adjList.has(vertex)) {
this.vertices.push(vertex);
this.adjList.set(vertex, []);
}
}
// Add edge
addEdge(v1, v2, weight = 1) {
this.addVertex(v1);
this.addVertex(v2);
this.adjList.get(v1).push({ node: v2, weight });
if (!this.isDirected) {
this.adjList.get(v2).push({ node: v1, weight });
}
}
// Get adjacent vertices of a vertex
getNeighbors(vertex) {
return this.adjList.get(vertex) || [];
}
// Print adjacency list
printList() {
for (const [vertex, neighbors] of this.adjList) {
let neighborStr = neighbors.map(n => `${n.node}(${n.weight})`).join(" -> ");
console.log(`${vertex}: ${neighborStr}`);
}
}
}
// Usage example
const graphList = new GraphList();
graphList.addVertex("A");
graphList.addVertex("B");
graphList.addVertex("C");
graphList.addEdge("A", "B", 1);
graphList.addEdge("B", "C", 2);
graphList.addEdge("A", "C", 3);
graphList.printList();
Advantages:
- High space efficiency (O(V+E))
- Suitable for sparse graphs
Disadvantages:
- Checking if there is an edge between two vertices requires traversal (O(degree))
Edge List
Store all edges in a list.
class GraphEdgeList {
constructor() {
this.vertices = new Set();
this.edges = [];
}
addVertex(vertex) {
this.vertices.add(vertex);
}
addEdge(from, to, weight = 1) {
this.addVertex(from);
this.addVertex(to);
this.edges.push({ from, to, weight });
}
getEdges() {
return this.edges;
}
}
// Usage example
const graphEdge = new GraphEdgeList();
graphEdge.addEdge("A", "B", 1);
graphEdge.addEdge("B", "C", 2);
graphEdge.addEdge("A", "C", 3);
console.log(graphEdge.getEdges());
Advantages:
- Simple, easy to iterate over all edges
Disadvantages:
- Inefficient for finding adjacent vertices of a vertex (requires traversing all edges)
Graph Traversal Algorithms
Depth-First Search (DFS)
DFS traverses as far as possible along each branch before backtracking.
class GraphTraversal {
constructor() {
this.adjList = new Map();
}
// ... (addVertex and addEdge methods omitted, similar to GraphList)
dfs(startVertex, visited = new Set(), result = []) {
if (!this.adjList.has(startVertex)) return result;
visited.add(startVertex);
result.push(startVertex);
for (const neighbor of this.adjList.get(startVertex)) {
if (!visited.has(neighbor.node)) {
this.dfs(neighbor.node, visited, result);
}
}
return result;
}
dfsIterative(startVertex) {
if (!this.adjList.has(startVertex)) return [];
const visited = new Set();
const result = [];
const stack = [startVertex];
while (stack.length > 0) {
const vertex = stack.pop();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
// Push neighbors in reverse order to simulate recursion
const neighbors = this.adjList.get(vertex).slice().reverse();
for (const neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
stack.push(neighbor.node);
}
}
}
}
return result;
}
}
// Usage example
const traversalGraph = new GraphTraversal();
traversalGraph.addEdge("A", "B");
traversalGraph.addEdge("A", "C");
traversalGraph.addEdge("B", "D");
traversalGraph.addEdge("B", "E");
traversalGraph.addEdge("C", "F");
console.log(traversalGraph.dfs("A")); // ["A", "B", "D", "E", "C", "F"]
console.log(traversalGraph.dfsIterative("A")); // Similar order
Breadth-First Search (BFS)
BFS traverses level by level using a queue.
class GraphTraversal {
// ... (previous code)
bfs(startVertex) {
if (!this.adjList.has(startVertex)) return [];
const visited = new Set();
const result = [];
const queue = [startVertex];
while (queue.length > 0) {
const vertex = queue.shift();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
for (const neighbor of this.adjList.get(vertex)) {
if (!visited.has(neighbor.node)) {
queue.push(neighbor.node);
}
}
}
}
return result;
}
}
// Usage example
console.log(traversalGraph.bfs("A")); // ["A", "B", "C", "D", "E", "F"]
Graph Algorithms
Shortest Path Algorithms
Dijkstra’s Algorithm (for weighted graphs with non-negative weights)
class Dijkstra {
constructor() {
this.adjList = new Map();
}
// ... (addVertex and addEdge methods omitted)
dijkstra(startVertex) {
const distances = new Map();
const previous = new Map();
const priorityQueue = []; // Can use a heap for optimization
// Initialize distances
for (const vertex of this.adjList.keys()) {
distances.set(vertex, Infinity);
previous.set(vertex, null);
}
distances.set(startVertex, 0);
priorityQueue.push({ vertex: startVertex, dist: 0 });
while (priorityQueue.length > 0) {
// Sort by distance (for simplicity, use min-heap in production)
priorityQueue.sort((a, b) => a.dist - b.dist);
const { vertex: u, dist } = priorityQueue.shift();
if (dist > distances.get(u)) continue;
for (const neighbor of this.adjList.get(u)) {
const v = neighbor.node;
const weight = neighbor.weight;
const alt = dist + weight;
if (alt < distances.get(v)) {
distances.set(v, alt);
previous.set(v, u);
priorityQueue.push({ vertex: v, dist: alt });
}
}
}
return { distances, previous };
}
getPath(previous, target) {
const path = [];
let current = target;
while (current !== null) {
path.unshift(current);
current = previous.get(current);
}
return path;
}
}
// Usage example
const dijkstraGraph = new Dijkstra();
dijkstraGraph.addEdge("A", "B", 4);
dijkstraGraph.addEdge("A", "C", 2);
dijkstraGraph.addEdge("B", "C", 1);
dijkstraGraph.addEdge("B", "D", 5);
dijkstraGraph.addEdge("C", "D", 8);
dijkstraGraph.addEdge("C", "E", 10);
dijkstraGraph.addEdge("D", "E", 2);
const { distances, previous } = dijkstraGraph.dijkstra("A");
console.log(distances); // Map { 'A' => 0, 'B' => 3, 'C' => 2, 'D' => 8, 'E' => 10 }
console.log(dijkstraGraph.getPath(previous, "E")); // [ 'A', 'C', 'B', 'D', 'E' ]
Bellman-Ford Algorithm (can handle negative weights)
class BellmanFord {
constructor() {
this.vertices = [];
this.edges = [];
}
addVertex(vertex) {
if (!this.vertices.includes(vertex)) {
this.vertices.push(vertex);
}
}
addEdge(from, to, weight) {
this.addVertex(from);
this.addVertex(to);
this.edges.push({ from, to, weight });
}
bellmanFord(startVertex) {
const distances = new Map();
const previous = new Map();
// Initialize distances
for (const vertex of this.vertices) {
distances.set(vertex, Infinity);
previous.set(vertex, null);
}
distances.set(startVertex, 0);
// Relax edges V-1 times
for (let i = 0; i < this.vertices.length - 1; i++) {
for (const { from, to, weight } of this.edges) {
const u = from;
const v = to;
if (distances.get(u) !== Infinity && distances.get(u) + weight < distances.get(v)) {
distances.set(v, distances.get(u) + weight);
previous.set(v, u);
}
}
}
// Check for negative weight cycles
for (const { from, to, weight } of this.edges) {
const u = from;
const v = to;
if (distances.get(u) !== Infinity && distances.get(u) + weight < distances.get(v)) {
throw new Error("Graph contains negative weight cycle");
}
}
return { distances, previous };
}
}
// Usage example
const bfGraph = new BellmanFord();
bfGraph.addEdge("A", "B", 4);
bfGraph.addEdge("A", "C", 2);
bfGraph.addEdge("B", "C", 1);
bfGraph.addEdge("B", "D", 5);
bfGraph.addEdge("C", "D", 8);
bfGraph.addEdge("C", "E", 10);
bfGraph.addEdge("D", "E", 2);
const { distances: bfDist } = bfGraph.bellmanFord("A");
console.log(bfDist); // Similar to Dijkstra's result
Minimum Spanning Tree Algorithms
Prim’s Algorithm
class Prim {
constructor() {
this.adjList = new Map();
}
// ... (addVertex and addEdge methods omitted)
prim() {
const visited = new Set();
const mst = [];
const priorityQueue = []; // Min-heap for edges
// Start from first vertex
const start = this.adjList.keys().next().value;
visited.add(start);
// Add all edges from start
for (const neighbor of this.adjList.get(start)) {
priorityQueue.push({
from: start,
to: neighbor.node,
weight: neighbor.weight
});
}
while (priorityQueue.length > 0 && visited.size < this.adjList.size) {
// Sort by weight (use heap in production)
priorityQueue.sort((a, b) => a.weight - b.weight);
const minEdge = priorityQueue.shift();
if (!visited.has(minEdge.to)) {
visited.add(minEdge.to);
mst.push(minEdge);
// Add new edges from this vertex
for (const neighbor of this.adjList.get(minEdge.to)) {
if (!visited.has(neighbor.node)) {
priorityQueue.push({
from: minEdge.to,
to: neighbor.node,
weight: neighbor.weight
});
}
}
}
}
return mst;
}
}
Kruskal’s Algorithm
class UnionFind {
constructor(size) {
this.parent = new Array(size).fill(0).map((_, i) => i);
this.rank = new Array(size).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX === rootY) return false;
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
return true;
}
}
class Kruskal {
constructor() {
this.vertices = [];
this.edges = [];
}
addVertex(vertex) {
if (!this.vertices.includes(vertex)) {
this.vertices.push(vertex);
}
}
addEdge(v1, v2, weight) {
this.addVertex(v1);
this.addVertex(v2);
this.edges.push({ from: v1, to: v2, weight });
}
kruskal() {
// Sort edges by weight
this.edges.sort((a, b) => a.weight - b.weight);
const uf = new UnionFind(this.vertices.length);
const mst = [];
const vertexIndex = {};
// Create mapping from vertex to index
this.vertices.forEach((v, i) => vertexIndex[v] = i);
for (const edge of this.edges) {
const { from, to, weight } = edge;
const u = vertexIndex[from];
const v = vertexIndex[to];
if (uf.union(u, v)) {
mst.push(edge);
// Stop if V-1 edges are added
if (mst.length === this.vertices.length - 1) {
break;
}
}
}
return mst;
}
}
Topological Sort
class TopologicalSort {
constructor() {
this.vertices = [];
this.adjList = new Map();
}
addVertex(vertex) {
if (!this.adjList.has(vertex)) {
this.vertices.push(vertex);
this.adjList.set(vertex, []);
}
}
addEdge(v1, v2) {
this.addVertex(v1);
this.addVertex(v2);
this.adjList.get(v1).push(v2);
}
topologicalSort() {
const visited = new Set();
const stack = [];
const dfs = (vertex) => {
visited.add(vertex);
for (const neighbor of this.adjList.get(vertex)) {
if (!visited.has(neighbor)) {
dfs(neighbor);
}
}
stack.push(vertex); // Post-order traversal
};
for (const vertex of this.vertices) {
if (!visited.has(vertex)) {
dfs(vertex);
}
}
return stack.reverse(); // Reverse to get topological order
}
hasCycle() {
const visited = new Set();
const recursionStack = new Set();
const hasCycleUtil = (vertex) => {
if (!visited.has(vertex)) {
visited.add(vertex);
recursionStack.add(vertex);
for (const neighbor of this.adjList.get(vertex)) {
if (
!visited.has(neighbor) && hasCycleUtil(neighbor) ||
recursionStack.has(neighbor)
) {
return true;
}
}
}
recursionStack.delete(vertex);
return false;
};
for (const vertex of this.vertices) {
if (hasCycleUtil(vertex)) {
return true;
}
}
return false;
}
}
// Usage example
const topoSort = new TopologicalSort();
topoSort.addEdge("A", "C");
topoSort.addEdge("B", "C");
topoSort.addEdge("B", "D");
topoSort.addEdge("C", "E");
topoSort.addEdge("D", "F");
topoSort.addEdge("E", "F");
console.log(topoSort.topologicalSort()); // ["B", "A", "D", "C", "E", "F"] or other valid order
console.log(topoSort.hasCycle()); // false
Graph Application Scenarios
- Social Networks: Graph of relationships between users
- Routing Algorithms: Route selection in the internet
- Recommendation Systems: Graph-based recommendation algorithms
- Transportation Networks: Connections between roads and intersections
- Dependency Resolution: Software package dependencies
- Task Scheduling: Dependencies between tasks
- Network Analysis: Node connections in computer networks
- Bioinformatics: Protein interaction networks
Performance Comparison
| Algorithm | Time Complexity | Space Complexity | Applicable Scenarios |
|---|---|---|---|
| DFS | O(V+E) | O(V) | Path finding, connectivity detection |
| BFS | O(V+E) | O(V) | Shortest path (unweighted graph), level traversal |
| Dijkstra | O((V+E)logV) | O(V) | Shortest path in weighted graphs (non-negative weights) |
| Bellman-Ford | O(VE) | O(V) | Shortest path in weighted graphs (can handle negative weights) |
| Prim | O(ElogV) | O(V) | Minimum spanning tree |
| Kruskal | O(ElogE) | O(E) | Minimum spanning tree |
| Topological Sort | O(V+E) | O(V) | Task scheduling, dependency resolution |
Summary
Graphs are a powerful data structure capable of representing various complex relationships. In JavaScript, graphs can be implemented using adjacency matrices or adjacency lists, and various classic algorithms can be applied to solve practical problems. Choosing the appropriate graph representation and algorithm depends on the specific application scenario and performance requirements.
Understanding the basic concepts of graphs, traversal methods, and classic algorithms is key to mastering graph data structures. In practical development, graph algorithms are widely used in network analysis, recommendation systems, path planning, and other fields, making them an important part of computer science.
