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

This article introduces the relevant knowledge of "what graphics algorithms are there". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

What is a picture?

A graph consists of a finite set of vertices or nodes and a set of edges that connect these vertices. If two vertices are connected to each other through the same side, they are called adjacent vertices.

Here are some basic definitions related to the graph. You can refer to the example in figure 1.

Order: number of vertices in the drawin

Size: number of edges in the drawin

Vertex degree: the number of edges incident to the vertex

Isolated vertices: vertices that are not connected to any other vertices in the graph

Self-loop: from vertex to its own edge

Digraph: a graph in which all edges have a direction indicating what is the starting vertex and what is the ending vertex.

Undirected graph: a graph with edges without direction

Weighted graphs: edges of graphs have weights

Unweighted shapes: edges of graphics have no weight

> Fig 1. Visualization of Terminology of Graphs (Image by Author)

1. Breadth first search

> Fig 2. Animation of BFS traversal of a graph (Image by Author)

Traversing or searching is one of the basic operations that can be performed on a drawing. In the breadth-first search (BFS), we start with a specific vertex, explore all its neighbors at the current depth, and then move on to the next vertex. Unlike a tree, a graph can contain loops (the same path as the first and last vertices). Therefore, we must track the vertices we visit. When implementing BFS, we use queue data structures.

Figure 2 shows the animation of the BFS traversal of the sample diagram. Notice how to find vertices (yellow) and access vertices (red).

Application field

Used to determine the shortest path and the minimum spanning tree.

The search engine searcher is used to build a web index.

Used to search on social networks.

Used to find available neighbor nodes in a peer-to-peer network, such as BitTorrent.

two。 Depth first search

> Fig 3. Animation of DFS traversal of a graph (Image by Author)

In depth-first search (DFS), we start with specific vertices and explore as much as possible along each branch before backtracking. In DFS, we also have to track the vertices we visit. When implementing DFS, we use stack data structures to support backtracking.

Figure 3 shows the animation of the DFS traversal of the sample diagram, which is the same as figure 2. Notice how it traverses depth and backtracking.

Application field

Lets you find the path between two vertices.

It is used to detect the period in the diagram.

Used for topological sorting.

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

3. The shortest path

> Fig 4. Animation showing the shortest path from vertex 1 to vertex 6 (Image by Author)

The shortest path from one vertex to another is a path in the graph, so the sum of the weights of the edges that should be moved is minimum.

Figure 4 shows an animation that determines the shortest path from vertex 1 to vertex 6 in the graph.

Algorithm

Dijkstra shortest path algorithm

Bellman-Ford algorithm

Application field

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

Used in the network to solve the minimum delay path problem.

Used in abstract machines to determine the choice to reach a target state by transitioning between different states (for example, it can be used to determine the minimum number of times it is possible to win a game).

> Image by Daniel Dino-Slofer from Pixabay

4. Cycle detection

> Fig 5.A cycle (Image by Author)

A loop is the same path as the first vertex and the last vertex in the graph. If we start at a vertex, follow a path, and then end at the starting vertex, then the path is a loop. 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 field

For algorithms based on distributed messages.

Used to process large-scale drawings on a cluster using a distributed processing system.

Used to detect deadlocks in concurrent systems.

The key used to determine a message in an encrypted application that maps the message to the same encrypted value.

5. Minimum spanning tree

> Fig 6. Animation showing a minimum spanning tree (Image by Author)

The minimum spanning tree is a subset of the edges of a graph, which connects all vertices with the sum of the minimum edge weights and does not contain cycles.

Figure 6 is an animation that shows the process of getting the minimum spanning tree.

Algorithm

The algorithm of Prim

The algorithm of Kruskal

Application field

Used to construct trees for broadcasting in computer networks.

Used for graph-based clustering analysis.

Used for image segmentation.

The regionalization of a sociogeographic region that divides a social region into continuous regions.

6. Securely connected components

> Fig 7. Strongly connected components (Image by Author)

If every vertex in the graph is reachable from every other vertex, the graph is said to be firmly connected.

Figure 7 shows an example diagram containing three firmly connected components with red, green, and yellow vertices.

Algorithm

The algorithm of Kosaraju

Strong connection component algorithm of Tarjan

Application field

It is used to calculate the Dulmage-Mendelsohn decomposition, which is the classification of the edges of bipartite graphs.

Used in social networks to find a group of people who are closely connected and make suggestions based on common interests.

> Image by Gerd Altmann from Pixabay

7. Topological sorting

> Fig 8. A topological ordering of vertices in a graph (Image by Author)

The topological sort of a graph is a linear sort of its vertices, so for each directed edge in the sort (umenet v), the vertex u is before v.

Figure 8 shows an example of the topological order of vertices (1, 2, 3, 5, 4, 6, 7, 8). You can see that vertex 5 should be after vertices 2 and 3. Similarly, vertex 6 should be after vertices 4 and 5.

Algorithm

Kahn algorithm

Algorithm based on depth-first search

Application field

Used for instruction scheduling.

Used for data serialization.

Used to determine the order of compilation tasks performed in makefile.

Used to resolve symbolic dependencies in the linker.

8. Graphic coloring

> Fig 9. Vertex colouring (Image by Author)

Graphic shading assigns colors to graphic elements while ensuring certain conditions. Vertex shading is the most commonly used graphic shading technique. In vertex shading, we try to use k colors to color the vertices of the graph, and no two adjacent vertices should have the same color. Other shading techniques include edge shading and facial shading.

The chromatic number of a graph is the minimum number of colors required for coloring the graph.

Figure 9 shows the vertex shading of a sample graph using four colors.

Algorithm

Use breadth-first or depth-first search algorithms

Greedy coloring

Application field

Used to schedule.

Used to assign mobile radio frequencies.

Used to model and solve Sudoku games.

Used to check whether the graph is a bipartite graph.

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

> Image by TheAndrasBarta from Pixabay

9. Maximum flow

> Fig 10. Determining the maximum flow (Image by Author)

We can model the graph as a traffic network with edge weights as traffic. In the problem of maximum flow, we must find a flow path that can obtain the maximum possible flow.

Figure 10 shows an animated example of determining the maximum traffic of the network and determining the final flow value.

Algorithm

Ford-Foxson algorithm

Edmonds-Karp algorithm

The algorithm of Dinic

Application field

Used for airline scheduling to dispatch pilots.

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

Used to eliminate baseball teams that cannot win enough games to catch up with the leaders in their department.

10. Match

> Fig 11. Matching of a bipartite graph (Image by Author)

A match in a graph is a set of edges that do not have a common vertex (that is, no two edges share a common vertex). If a match contains as many edges as possible that match as many vertices as possible, the match is called a maximum match.

Figure 11 shows the animation that obtains an exact match between the bipartite graph and the two sets of vertices represented by orange and blue.

Algorithm

Hopcroft-Karp algorithm

Hungarian algorithm

Flowering algorithm

Application field

Used for docking meetings to match the bride and groom (stable marital problems).

Used to determine vertex coverage.

It is used to solve the problems of resource allocation and travel optimization in transportation theory.

This is the end of the content of "what are the graphic algorithms"? thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.