Graph is a non-linear data structure consisting of vertices/nodes and edges. Vertices are the nodes in graph and edges are the lines or arcs that connect two nodes in the graph.
Graphs can be categorized directed graph and undirected graph based on if the edge of the graph can have direction or can be categorized weighted graph and unweighted graph based on if the edge has the same weight (represented by an integer) or not.
Graphs can be represented in two ways:
-
Adjacency Matrix: Use a 2-D array to represent a graph. Initially, every element in the array is initialized as 0. If a particular position
arr[i][j]has value, it means from vertex i to vertex j has the edge. -
Adjacency List: Use an array of lists to store edges between two vertices. The size of array is the number of vertices. Each index in the array represents a specfic vertex in the graph. The entry at the index i of the array contains a linked list containing the vertices that are adjacent to vertex i.
Implement graph(unweighted) data structure using adjacency matrix and its relevant methods.
constructor(vertexList, options)Initialize a graph with a list of vertics and specify the graph as directed or not and weighted or not.addEdge(v1, v2, weight)Add an edge between two vertices (starting from vertex v1 to v2) in graph.removeEdge(v1, v2)Remove an edge between two verticesaddVertex(vertex)Add a vertex with a given value.removeVertex(vertex)Remove a vertex of a given value.