A constructor is created in this class that takes a list of nodes as a parameter and initializes the adjacency list. The list of nodes will be stored by using an ArrayList. We will use a HashMap to map each node to a list of nodes. The Graph class will use an adjacency list to store the nodes and the connections between nodes. For more complex nodes, we can add multiple fields and methods to this class. It will just contain a string name attribute and a parametrized constructor. All the methods will be added to the Graph class. Another one will be called the Graph class and it will have an adjacency list to store the graph. One will be a simple Vertex or Node class with just a name attribute. We will create two classes to implement graphs in Java. Adjacency lists are more complex to work with but provide better space efficiency. A list is maintained for each node in the array and this list contains the nodes directly connected with our node. The length of the array is equal to the number of nodes.
These matrices are easy to create but there is an inefficient use of space.Īn adjacency list is simply an array of lists. If the graph is undirected, the matrix will be symmetric about the diagonal. For weighted graphs, instead of using 1, we can use the edge weight. 0 indicates that no edge is present between the two nodes and 1 denotes that an edge is present. Each row and column denote the nodes and the value of each cell of the matrix can be 0 or 1.
Adjacency MatrixĪ graph can be represented in the form of a square matrix of order 2(a 2-D matrix). For example, in the case of a graph of connected cities, the weight of an edge can denote the distance or time taken to travel from one node to another.Ī graph can be represented in two ways - using an Adjacency Matrix or using an Adjacency List. This weight can denote any relative measure between the nodes. The edge between B and C has two arrowheads which mean that we can move in both directions.Ī graph in which each edge has a weight or cost associated with it is called a weighted graph. This means that we can go from A to B but not in the other direction(from B to A). For example, in the image below the edge between A and B has an arrowhead pointing from A to B. In the following image, an edge exists between A and B and we can freely move from A to B, or from B to A without any restriction.Ī graph in which edges denote a direction is called a directed graph. The graph of cities shown in the previous section is an undirected graph. Undirected GraphĪ graph in which the edges are two-way or a graph in which the edge does not denote a direction is called an undirected graph.
Graphs are of various types but for this tutorial, we will only look at some of the most important ones. The following image shows a graph in which each node represents a city and an edge between two nodes denotes that there is a direct route between them. Graph Data StructureĪs discussed above, a graph is a network of nodes connected by edges. In this tutorial, we will learn the basics of graphs and implement some common operations on graphs in Java. They can be used to denote a network of people on social media websites, or they can be used to represent the connection between various cities. Graphs have a lot of real-world use cases. The elements of a graph are called vertices or nodes and the connection between two nodes or vertices is represented by an edge between them. A graph is a data structure that is used to store elements and connections between the elements.
0 kommentar(er)
