This is the 20th day of my participation in the August Text Challenge.More challenges in August

Part 1: Outline analysis

01 Examination analysis

The storage structure of the basic concept map of knowledge point map

  • Adjacency matrix
  • Adjacency list
  • Curb table
  • Adjacency multiple list

Graph traversal

  • Depth-first traversal: DFS algorithm
  • Breadth-first traversal: BFS algorithm

The application of figure

  • Minimum spanning tree: Prim and Kruskal • Shortest path: Dijkstra and Floyd
  • Topology sorting: AOV network
  • Key path: AOE network

Focus on

  • Depth-first traversal: DFS algorithm
  • Breadth-first traversal: BFS algorithm
  • Minimum spanning tree: Prim and Kruskal Algorithms buy a ticket. The shortest path is either Dijkstra or Floyd

The difficulties in

  • Shortest path: Dijkstra and Floyd

Part 2: Basic concepts of graphs

First, the basic concept of graph

Definition: A graph consists of data elements and lines connecting data elements, where the data elements are called vertices, and the lines connecting vertices are called edges: Graph G is denoted as G=(V,E) or G=(V(G),E(G)), where V(G) represents a finite non-empty set of vertices, and E(G) represents the set of edges between vertices, as shown on the right: G = (V, E) V = {6} E = {(1, 2), (2, 3), (3, 4), (4, 5), (1, 5), (5, 6), (2, 6), (3, 6)}

Note:

  • Linear tables have empty tables, trees have empty trees, but graphs have no empty graphs
  • Figure of the vertex set V must be not empty, but the edge set E can is empty, | V | chart the number of vertices in G, also known as the order of graph G
  • | E | table number of edges in the graph G

Related terms:

1. The directed graph

Definition: If E is a finite set of directed edges (also known as arcs), then graph G is a directed graph: arc is an ordered pair of vertices, denoted as

, where V, W are vertices, v is called arc tail,w is called arc head, the arc is called the arc from vertex V to vertex W, also known as V adjacent to W, or W adjacent to V
,>

2. The undirected graph

Definition: If E is a finite set of undirected edges (edges for short), then graph G is represented as an undirected graph: edges are unordered pairs of vertices, denoted as (v,w) or (w,v), where V and W are vertices, called vertex V and vertex W are adjacent edges to each other, as shown in the figure on the right: G = (V, E) V = {6} E = {(1, 2), (2, 3), (3, 4), (4, 5), (1, 5), (5, 6), (2, 6), (3, 6)}

3. Simple figure

Definition: if graph G satisfies: ① There is no repeated edge; ② Graph G is called simple graph if there are no edges from vertices to themselves. Note: Only simple graphs are discussed in data structures

4. Multiple figure

Definition: Graph G is a multiple graph if there is more than one edge between two nodes and vertices are allowed to relate to themselves by the same edge. Note: Multiple graphs are defined as opposed to simple graphs

5. Complete graph (also known as simple complete graph)

Definition: In an undirected graph, graph G is called undirected complete graph if there are edges between any two vertices. In a directed graph, graph G is called directed complete graph if there are two arcs between any two vertices in opposite directions

6. Subgraph and generation subgraph

Definition: If two graphs G=(V,E) and G ‘=(V’,E ‘), if V ‘is a subset of V and E’ is a subset of E, G ‘is said to be a subgraph of G, and if V(G’)= a subgraph of V(G) G ‘is satisfied, it is a generated subgraph of G

Note that not any subset of V and E can form a subgraph of G, because such a subset may not be a graph i.e. some vertices associated with edges in a subset of E may not be in the subset of V

7. Connected, connected graphs, and connected components

Definition: If there is a path from vertex V to vertex W in an undirected graph, it is said that V and W are connected. If any two vertices in graph G are connected, it is said that graph G is a connected graph. The maximal connected subgraph of an undirected graph is called a connected component

Note: • A graph must be disconnected if it has n vertices and less than n-1 edges

8. Strongly connected graphs and strongly connected components

Definition: If there are paths from vertex V to vertex W and from vertex W to vertex V in a directed graph, v and W are said to be strongly connected. If any two vertices in graph G are strongly connected, then graph G is called a strongly connected subgraph of a directed graph

Note:

  • Strongly connected graphs and strongly connected components are directed graphs
  • Connected graphs and connected components are for undirected graphs

9. Spanning trees and forests

Definition: The spanning tree of a connected graph is an unconnected graph with a minimal pair of connected subgraphs containing all vertices in the graph. The spanning tree of connected components constitutes a forest of unconnected graphs

Note:

  • When the number of vertices in a graph is N, its spanning tree contains N-1 edges
  • For spanning trees, if you cut an edge, it becomes an unconnected graph, and if you add an edge, it forms a loop
  • A maximally connected subgraph requires that the graph contain as many edges as possible while it is connected
  • The minimum connected subgraph requires the graph to contain the least number of edges if it is connected

10. Degree, in, and out of vertices

Definition:

  • The degree of each vertex is the number of edges with that vertex as an endpoint
  • For an undirected graph, the degree of vertex V is the number of edges attached to the vertex, denoted as TD(v) • For a directed graph, the degree of vertex V is divided into inbound and outbound degrees
  • The entry is the number of directed edges that end at vertex V, called ID(v).
  • The output is the number of directed edges starting at vertex V, and we call it OD of v.
  • The degree of vertex V is equal to the sum of its degree in and degree out, i.e. TD(v)=ID(v)+OD(v)

11. Edge weights and nets

Definition: In a graph, each edge can be marked with a value with some meaning, which is called the weight of the edge. The graph with a weight on the edge is called a weighted graph, also called a net

12. Dense and sparse graphs

Definition: the graph with few edges is called sparse graph, and vice versa is called dense graph

13. Path, path length and loop

Definition: a vertex 𝑉 𝑝 to 𝑉 𝑞 a path between refers to the vertex sequence 𝑉 𝑝, 𝑉 1, 2, 𝑉 𝑉 3,…, 𝑉 𝑞. The number of sides of a path is called the length of a path where the first vertex is the same as the last is called a loop or loop

14. Simple path and simple loop

Definition: In a path sequence, a path whose vertices do not repeat is called a simple path. A path whose vertices do not repeat is called a simple path

Distance 15.

Definition: The shortest path from vertex 𝑉𝑝 to vertex 𝑉𝑞, if it exists, is called the distance from 𝑉𝑝 to 𝑉𝑞. If there is no path at all from vertex 𝑉𝑞 to vertex x, the distance is called infinity (∞).

16. Have to trees

Definition: A directed tree is a graph with one vertex of 0 and all other vertices of 1