preface

What is a graph? What can it be used for? This article will take you through the above questions in graphic form, welcome interested developers to read this article.

concept

As shown in the figure below, circles are called vertices (nodes), and the lines connecting the vertices are called edges. That is, a graph is made up of vertices and the edges connecting each pair of vertices.

role

Diagrams can be used to represent various relationships:

  • It is very convenient to use the interpersonal graph, which shows the relationships in the society. Suppose we want to hold an event, the participants as the apex, people who know each other by the edge, can be used to show the interpersonal relationship between the participants.

  • By taking the station as the vertex and connecting the two adjacent stations with edges, a graph can be used to show the route of the subway.

  • In computer networks, routers are regarded as vertices, and two routers connected to each other are connected by edges, so that the network connection can be shown in graphs.

classification

Graphs can be roughly divided into undirected graphs, weighted graphs and directed graphs

Weighted graph

All of these graphs are made up of vertices and edges, and we can put a value on an edge.

This value is called the edge weight or weight, and the weighted graph is called a “weighted graph”. Edges without weights can only represent the state of connection between two vertices, while edges with weights can represent the “degree of connection” between vertices.

Degree: Depending on the content of the graph, it can mean different things. For example, in a computer network, add the time it takes to transmit data to the edge between two routers, and this graph can show the communication time between networks.

On a road map, if you add the time it takes to travel between stations to the side, it shows the movement time of the entire route. If the fare between two stations is added to the edge, the fare can be shown.

Directed graph

When we want to indicate in a road map that the route is only one-way, we add arrows to the sides, and such a graph is called a “directed graph.” For example, links in a web page are also directional, and it is convenient to use a directed graph to represent them.

A graph without an arrow is an “undirected graph”.

As shown in the figure, we can go from vertex A to vertex B, but not directly from B to A, and there are two edges between B and C pointing in two directions, so we can move in both directions.

As with undirected graphs, edges of digraphs can be weighted.

As shown in the figure, the weight from B to C is 5, and the weight from C to B is 7. If you make a graph of movement time, then B to C is downhill. Just like this, digraphs can also be weighted asymmetrically

convenience

Suppose we have two vertices, S and t, and we devise an algorithm to find the path with the smallest sum of weights from s to T.

So, this algorithm can be applied to these problems: looking for the shortest communication time path in the computer network, looking for the shortest time path in the road map, looking for the road map with the least cost of travel.

And just like that, as long as we can represent these relationships in graphs, we can use algorithms that solve graph problems to solve these seemingly different problems.

Figure in the search

Graph search refers to the process of starting from a vertex of the graph, reaching different vertices through edge to edge, and finally finding the target vertex. According to the search order, the search algorithm of graph has “breadth first search”, “depth first search” and so on.

The search of graph can solve the basic problem of graph: algorithm of shortest path problem, which is to find a path with the minimum sum of weight of edges in the path “from S to T”.

Write in the last

  • The pictures used in this article are from “my first algorithm book”, if infringement, please leave a message in the comment section, the author immediately delete the relevant pictures.
  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌