In JavaScript, a graph is a non-linear data structure consisting of a collection of nodes (vertices) and edges that connect pairs of nodes. Graphs are widely used to represent relationships between objects or entities in various applications, such as social networks, maps, network topology, and routing algorithms.
Components of a Graph:
- Node (Vertex):
- Each node in a graph represents an entity or object and may contain additional information.
- Edge:
- An edge is a connection between two nodes that represents a relationship between them. An edge can be directed (one-way) or undirected (two-way).
Types of Graphs:
Directed Graph (Digraph):
- In a directed graph, each edge has a direction, indicating a one-way relationship between nodes.
Undirected Graph:
- In an undirected graph, edges have no direction, representing two-way relationships between nodes
Weighted Graph:
- A weighted graph has values associated with its edges, called weights, which represent the cost or distance between nodes.
Unweighted Graph:
- In an unweighted graph, all edges have the same weight or no weight at all.
Acyclic Graph:
- An acyclic graph is a graph with no cycles, meaning there are no paths that lead back to the starting node.
Cyclic Graph:
- A cyclic graph contains one or more cycles, where a cycle is a path that starts and ends at the same node.
Representations of Graphs:
Adjacency Matrix:
- An adjacency matrix is a 2D array where each cell
matrix[i][j]represents whether there is an edge from nodeito nodej. It’s suitable for dense graphs.
- An adjacency matrix is a 2D array where each cell
Adjacency List:
- An adjacency list is a collection of lists or arrays, where each list represents the neighbors of a node. It’s suitable for sparse graphs and more memory-efficient.
Operations and Algorithms:
Traversal:
- Graph traversal algorithms like depth-first search (DFS) and breadth-first search (BFS) are used to visit all nodes in a graph.
Shortest Path:
- Algorithms like Dijkstra’s algorithm and Bellman-Ford algorithm are used to find the shortest path between two nodes in a weighted graph.
Minimum Spanning Tree (MST):
- Algorithms like Kruskal’s algorithm and Prim’s algorithm are used to find the minimum spanning tree of a graph.
Topological Sorting:
- Topological sorting is used to order the nodes in a directed acyclic graph (DAG) such that for every directed edge
uv, nodeucomes beforevin the ordering.
- Topological sorting is used to order the nodes in a directed acyclic graph (DAG) such that for every directed edge
class Graph {
constructor() {
this.adjList = new Map();
}
addNode(node) {
if (!this.adjList.has(node)) {
this.adjList.set(node, []);
}
}
addEdge(node1, node2) {
this.addNode(node1);
this.addNode(node2);
this.adjList.get(node1).push(node2);
// For undirected graph, add both edges
this.adjList.get(node2).push(node1);
// For undirected graph, add both edges
}
printGraph() {
for (let [node, neighbors] of this.adjList) {
console.log(`${node} -> $
{neighbors.join(", ")}`);
}
}
}
// Example usage:
let graph = new Graph();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(4, 5);
graph.printGraph();
