Hello! Today we will take a closer look at graph representation<\/strong> which is frequently asked in coding tests using Java, and solve related algorithm problems. Graphs are a crucial data structure for solving given problems, consisting of vertices and edges. There are various ways to represent graphs, and in this article, we will explain the Adjacency List and Adjacency Matrix methods.<\/p>\n An adjacency list is a way of storing a list of adjacent vertices for each vertex. It is usually implemented using arrays or lists. This method is very memory efficient and is useful in operations that proceed relatively slowly.<\/p>\n An adjacency matrix is a way of representing a graph using a 2D array. This method allows you to check the existence of an edge in O(1) time complexity, but it has high space complexity and can be inefficient for graphs of variable sizes.<\/p>\n Now let’s solve an actual problem. The given problem is Building Bridges<\/strong>.<\/p>\n Given N points on a 2D plane, we want to construct bridges so that every point can be connected to each other. Print the length of the shortest path. (Up to 2 decimal places)<\/p>\n To solve the problem, I will approach it in the following order:<\/p>\n Today, we explored graph representation methods and solved an algorithm problem. Next time, we will look into topics related to search algorithms. Thank you!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Graph Representation Methods<\/h2>\n
1. Adjacency List<\/h3>\n
class Graph {\n private int vertices; \/\/ number of vertices\n private LinkedList2. Adjacency Matrix<\/h3>\n
class Graph {\n private int vertices;\n private int[][] adjMatrix;\n\n \/\/ graph constructor\n public Graph(int v) {\n vertices = v;\n adjMatrix = new int[v][v];\n }\n\n \/\/ method to add an edge\n public void addEdge(int source, int destination) {\n adjMatrix[source][destination] = 1;\n \/\/ For undirected graphs\n \/\/ adjMatrix[destination][source] = 1;\n }\n}\n<\/code><\/pre>\nProblem: Building Bridges<\/h2>\n
Problem Description<\/h3>\n
\nThe length of the bridge is the Euclidean distance between two points.
\nFind the length of the shortest path. Note that two points cannot be connected again during the bridge construction process.<\/p>\nInput<\/h3>\n
\n
Output<\/h3>\n
Problem Solving Approach<\/h3>\n
\n
Java Code Implementation<\/h3>\n
import java.util.*;\n\nclass Point {\n int x, y;\n\n Point(int x, int y) {\n this.x = x;\n this.y = y;\n }\n\n double distance(Point p) {\n return Math.sqrt(Math.pow(this.x - p.x, 2) + Math.pow(this.y - p.y, 2));\n }\n}\n\nclass Graph {\n private int vertices;\n private ListConclusion<\/h2>\n
\nThrough this problem, we learned how to handle graphs and how to compute distances between points, as well as implement the shortest path algorithm using adjacency lists and adjacency matrices.
\nGraphs are a common concept in real life and are very useful in solving complex problems.<\/p>\n