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

This article mainly explains "what are the basic visualization methods". The content of the explanation is simple and clear, and it is easy to learn and understand. let's follow the editor's train of thought. Let's study and learn "what are the basic visualization methods"?

First of all, what is the chart?

A chart consists of a set of finite vertices or nodes and a set of edges that connect these vertices. If two vertices are connected to each other through the same edge, they are called adjacencies. Here are some basic definitions related to the chart, which you can refer to the example in the figure.

Order: number of vertices in the chart

Size: number of sides in the chart

Vertex degree: the number of edges incident to the vertex

Isolated vertex: a vertex that is not connected to any other vertex in the graph

Self-loop: an edge from a vertex to itself

Directed graph: all edges in the graph have directions to represent the starting point and the end point

Undirected graph: the edge of a graph has no direction

Weighted graphs: edges of graphs have weighted values

Unweighted graphs: edges of graphs have no weight

Figure 1: visualization of chart terms

1. Breadth first search

Figure 2: breadth-first search (BFS) traversing animation

Traversing or searching is one of the basic operations performed on a chart. In breadth-first search (BFS), starting with a specific vertex, explore all relevant information about its current depth before entering the vertex of the next layer. Unlike trees, diagrams can contain loops (the first and last vertices are the same path). Therefore, you must track the vertices you have visited. When implementing BFS, you should use queue data structures.

Figure 2 is an animation of the BFS traversal of an example diagram, noticing how vertices are found (yellow) and accessed (red).

Application:

For social network search

Used to determine the shortest path and minimum spanning tree

Used by search engine crawlers to build web page indexes

Used to find available neighboring nodes in peer-to-peer networks such as BitTorrent

two。 Depth first search

Figure 3: traversal animation for depth-first search (DFS)

In depth-first search (DFS), start from a specific vertex and search along each branch as much as possible before backtracking. In DFS, you also need to keep track of visited vertices. When implementing DFS, use stack data structures to support backtracking.

Figure 3 animates the DFS traversal of the same sample diagram used in figure 2, noticing how it traverses to depth and backtracking.

Application:

Used to find the path between two vertices

Used to detect loops in the diagram

For topological sorting

Used to solve problems where there is only one solution (such as a maze)

3. The shortest path

Figure 4 Animation shows the shortest path from vertex 1 to vertex 6

The shortest path from one vertex to another is the path in the graph, so the sum of the weights of the moving edges should be minimized. Figure 4 shows an animation in which the shortest path from vertex 1 to vertex 6 is determined.

Algorithm:

The shortest path algorithm of Dijkstra

Behrman-Ford (Bellman-Ford) algorithm

Application:

It is used to solve the minimum delay path problem in the network.

Used to find a route from one location to another in software such as Google or Apple Maps.

Used in an abstract machine to determine the method of achieving a target state through the transition between different states. For example, it can be used to determine how to win a game with minimum walking.

4. Cycle detection

Figure 5: a loop

A loop is the same path as the first vertex and the last vertex in the graph. If you start from a vertex, follow a path, and finally reach the starting point, then the path is a cycle. Loop detection is the process of detecting these cycles. Figure 5 shows the animation of traversing a loop.

Algorithm:

Freudian cycle detection algorithm

Brent algorithm

Application:

For message-based distributed algorithms

Used to process large-scale charts using distributed processing systems on the cluster

Used to detect deadlock in concurrent systems

Used in encrypted applications to determine the key that can map messages to messages with the same encrypted value

5. Minimum spanning tree

Figure 6. Show the animation of the minimum spanning tree

The minimum spanning tree is a subset of the edges of the graph, which connects the vertices with the least sum of edge weights and does not contain any loops. Figure 6 is an animation of the process of obtaining a minimum spanning tree.

Algorithm:

Purin algorithm

Kruskal algorithm

Application:

Used to build broadcast trees in computer networks

For chart-based clustering analysis

For image segmentation

For regionalization in the field of social geography, the region is divided into adjacent regions.

6. Strongly connected component

Figure 7: strongly connected components

If every vertex in the graph can be reached by other vertices, then the graph is strongly connected. Figure 7 contains three strongly connected components, with vertices represented in red, green, and yellow, respectively.

Algorithm:

Kosaraju algorithm

Tarjan strongly connected component algorithm

Application:

Used to calculate the Dulmage Mendelsohn decomposition, is a classification of the edge of the binary chart.

Used in social networks to find and recommend people with close connections according to common interests.

7. Topological sorting

Figure 8: topological sorting of vertices in the figure

The topological sort of the chart is a linear sort of its vertices, so for each directed edge (u, v) in the sort, the vertex u comes before v. Figure 8 shows an example of topological sorting of vertices (1, 2, 3, 5, 4, 6, 7, 8). As you can see, vertex 5 should come after vertices 2 and 3. Similarly, vertex 6 should come after vertices 4 and 5.

Algorithm:

Kahn algorithm

Based on depth first algorithm

Application:

For instruction scheduling

For data serialization

Used to determine the order of compilation tasks to be performed in the build file

Used to parse symbolic dependencies in linkers

8. Graph coloring

Figure 9: Vertex shading

Graph coloring refers to assigning colors to the elements of a graph under certain conditions, and vertex coloring is the most commonly used graphic coloring technique. In vertex coloring, we try to color the vertices of the graph with k colors, and any two adjacent vertices have different colors. Other shading techniques include edge shading and facial shading. The chromatic number of a graph is the minimum number of colors required to color the graph. Figure 9 shows that vertices are shaded with four colors.

Algorithm:

Use breadth-first or depth-first search algorithms

Greedy coloring

Application:

Used to set a schedule

Used to assign mobile radio frequencies

Used to model and solve Sudoku games

It is used to check whether the graph is bipartite.

Used to color the maps of neighboring countries or states with different colors

9. Maximum flow

Figure 10: determine the maximum flow

A graph can be modeled as a flow network with edge weights as traffic capacity. In the maximum flow problem, the flow path that can obtain the maximum possible flow rate must be found. Figure 10 is an animation example that determines the maximum traffic and the final flow value of the network.

Algorithm:

Ford-Fulkerson algorithm

Edmonds-Karp algorithm

Dinic algorithm

Application:

Used for airline scheduling and arranging flight crew.

Used for image segmentation to find the background and foreground in the image.

Used to eliminate players who can't win the game and can't compete with the best of the current team.

10. Match

Figure 11: bipartite graph matching

The match in the chart is a set of edges that do not have a common vertex (that is, neither two have a common vertex). If a match contains the maximum number of edges matched by as many vertices as possible, then the match is called the maximum match. Figure 11 shows the exact matching animation of a bipartite graph with two sets of vertices, represented in orange and blue, respectively.

Algorithm:

Hopcroft-Karp (Hopcroft-Karp) algorithm

Hungarian algorithm

Flowering algorithm

Application:

Used to match the bride and groom (the stability of the marriage)

Used to determine vertex coverage

Used in traffic theory to solve the problem of travel resource allocation and optimization.

Thank you for your reading. the above is the content of "what are the basic visualization methods". After the study of this article, I believe you have a deeper understanding of the basic visualization methods. the specific use of the situation also needs to be verified by practice. 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.