Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to understand the object description of java diagram". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to understand the object description of java diagram".

I. Preface

As for the picture, I always seem to understand it.

What you understand is the meaning of the graph, but what you don't understand is the concrete implementation of the graph.

For the current interview questions of major manufacturers, there are no more than the following points:

Depth first search, breadth first search: DFS, BFS minimum spanning tree: Kruskal, Prim shortest path: Dijkstra, Dijkstra enhanced stack topological sorting: TopologicalSort

In fact, these algorithms don't sound too difficult to understand, but when you actually write the code, you will find that the edges and points of the silly graph are so difficult to describe that the person we write is gone, and you can't get in or out.

2. What is a graph

The picture shows the abstraction of the connecting relationships in our real life, such as the attention relationships of our moments and Weibo.

For graphs, they are divided into directed graphs and undirected graphs, as shown in the following figure:

We can see that the digraph represents only from one vertex to the other, while the undirected graph represents that the two vertices can reach each other.

In figure 1, V4 reaches V1, while V1 cannot reach V4.

In figure 2, V4 can reach V1 and V1 can also reach V4

Of course, there is also a form of graph, called weighted graph (mainly used to calculate some distances and fares), as shown in the following figure:

Third, how to store the structure of a graph

When we do exercises, the examples given to us are often like this: 743. Network delay time

The title will give us a two-dimensional matrix, with a row of matrices with three numbers, namely: starting point, ending point, weight.

How to express this two-dimensional matrix has become a difficult thing for us to do in the drawing problem.

This article will directly use a special representation to solve this problem, starting with the most basic adjacency matrix and adjacency table representation.

1. Adjacency matrix

An adjacency matrix is a matrix that represents the adjacent relationship between vertices in a graph.

For adjacency matrix of undirected graph: symmetric matrix: int [] []

The adjacency matrix of a digraph: the sum of rows is the degree of exit and the sum of columns is the degree of entry.

Adjacency Matrix of weighted Graph

2. Adjacency table

An adjacency table is a linked storage structure similar to an array of linked lists.

Adjacency table of undirected graph: HashMap

3. Object representation of the graph.

Let's think, do the above two methods represent the image of the graph?

Although some problems are comfortable to do when represented by a matrix, let's think about it. When we find the minimum spanning tree, when we use the connection of the edge to unlock the point, the matrix will be used.

It will not feel very abstract and difficult to understand, as shown, we need to customize the representation of a graph to enhance our understanding of the diagram.

For the picture, let's think about what it mainly includes.

A graph is a structure made up of points and edges, that is, if we want to draw a graph, we must have: points and edges.

Description of the point:

Value of point: int value

Adjacency point: ArrayList nexts

Adjacent edges: ArrayList edges

Entry: int in

Output: int out

Public class Node {public int value; public int in; public int out; public ArrayList nexts; public ArrayList edges; public Node (int value) {this.value = value; in = 0; out = 0; nexts = new ArrayList (); edges = new ArrayList ();}}

Description of the edge:

Where to come from: where Node from is going: weight of Node to side: int weight

Public class Edge {Node from; Node to; int weight; public Edge (Node from, Node to, int weight) {this.from = from; this.to = to; this.weight = weight;}}

Description of the figure:

Collection of multiple points: HashMap nodes set of multiple edges: Set edges

Public class Graph {public HashMap nodes; public Set edges; public Graph () {nodes = new HashMap (); edges = new HashSet ();}}

There may be questions here, although you write the image like this, but how to transform it?

Don't worry, we'll convert it next.

Public static Graph createGraph (int [] [] matrix) {/ / initialize a graph Graph graph = new Graph (); for (int [] arr: matrix) {/ / Point int from = arr [0]; / / Point int to = arr [1]; / / weight int value = arr [2] / / generate the corresponding point Node fromNode = new Node (from); Node toNode = new Node (to); / / check whether the information of this point is currently available if (! graph.nodes.containsKey (from)) {graph.nodes.put (from, fromNode) } if (! graph.nodes.containsKey (to)) {graph.nodes.put (to, toNode);} / / generate an edge (where the edge is a directed edge) Edge edge = new Edge (fromNode, toNode, value) / add edge graph.nodes.get (from) .edges.add (edge); / / add next point graph.nodes.get (from) .nexts.add (toNode); / / add graph.nodes.get (from) .out + +; graph.nodes.get (to) .add / / add edge graph.edges.add (edge) to the graph;} return graph;}

When we are done with the conversion, test:

Public static void main (String [] args) {int [] [] arr = new int [] [] {{2,1,1}, {2,3,1}, {3,4,1}}; Graph graph = createGraph (arr); / / which edges starting from 2 have List edgeList = graph.nodes.get (2) .edges For (Edge edge: edgeList) {System.out.println ("from" + edge.from.value + "- >" + edge.to.value + "weight is" + edge.weight ");}}

End result:

Weight from 2 to 1 to 1 from 2 to 1

From 2 to 3, the weight is 1

In the future, when we do the problem, we can save this conversion code and call it directly.

A simple and vivid picture of us.

IV. The function of the graph

Pictures are often used in the following places:

Depth first search, breadth first search: DFS, BFS

Minimum spanning tree: Kruskal, Prim

Shortest path: Dijkstra, Dijkstra enhanced stack version

Topological sorting: TopologicalSort

Thank you for your reading, the above is the content of "how to understand the object description of java diagram". After the study of this article, I believe you have a deeper understanding of how to understand the object description of java diagram. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.