Figure: concept of figure

chart ： The concept of graph

Definition of graph

chart （Graph）G By vertex set V(G) And edge set (G) constitute

explain ： about n A graph of vertices , Number each vertex consecutively , That is, the number of vertices is 0~n-1. Uniquely identify a vertex by number

Figure abstract data structure type = Logical structure + Basic operation （ Operation description ）

The basic operations of graphs as follows ：

• InitGraph(&g)： Graph initialization
• ClaerGraph(&g)： Destruction map
• DFS(G,v)： From the top v Departure depth first traversal
• BFS(G,v)： From the top v Starting breadth first traversal

In the figure G in , If the vertex pairs representing the edges are unordered , said G by Undirected graph . An undirected edge is represented by an ordered pair of parentheses

If the vertex pairs representing the edges are ordered , said G by Directed graph . Use angle brackets to indicate directed edges

The basic term of graph

1. Endpoints and adjacency points

• Undirected graph ： If there is an edge (i,j) , Then the summit i And vertex j by Endpoint , They are each other Adjacency point
• Directed graph ： If there is an edge <i,j>, Then the summit i by Start endpoint ( Referred to as The starting point ), The vertices j by Terminate endpoint ( abbreviation End ), They are each other Adjacency point

2. The degree of the vertex , In and out

• Undirected graph ： At the top i Is the number of edges at the endpoint The degree of the vertex
  
• Directed graph ： At the top i Is the number of incoming edges at the end , Call it The penetration of a vertex . At the top i Is the number of edges out of the starting point , Call it The degree of the vertex . The sum of the in and out degrees of a vertex is the The degree of the vertex
  
  

3. Complete graph

• Undirected graph ： There is an edge between every two vertices , be called Completely undirected , contains n(n-1)/2 side
• Directed graph ： There are two opposite sides between every two vertices , be called Completely directed graph , contains **n(n-1)** side
  

4. A dense picture , Sparse graph

When a graph approaches a complete graph , It is called a A dense picture

contrary , When a graph has fewer edges （ When e<<n(n-1)) when , It is called a Sparse graph

5. Subgraphs

There are two figures G=(V,E) and G’=(V’,E’), if V’ yes V Subset , namely V’ Belong to V, And E’ yes E Subset , namely E’ Belong to E, said G’ yes G Of Subgraphs

6. Path and path length

In a graph G=(V,E) in , From the top i To the top j One of route （i,i1,i2,…,im,j）. All of them （ix,iy） Belong to E(G), perhaps <ix,iy> Belong to E(G)

The length of the path Is the number of edges a path passes through

If a path has the same starting point and ending point , The other vertices are not the same , This path is called Simple path

7. Loop or ring

If the start point and end point of a path are the same vertex , Then this path is called a loop or ring . A simple path with the same starting point and ending point is called Simple circuit or Simple ring

8. connected , Connected graphs and connected components

Undirected graph ： If from the top i To the top j There is a path , It's called the summit i and j yes connected Of

If any two vertices in a graph are connected , It is called a Connected graph , Otherwise it is called Unconnected graph

Undirected graph G The polar Dalian Tong subgraph in is called G Of Connected component . obviously , Any connected graph has only one connected component , Namely itself , Instead of a connected graph, there are multiple Connected component

9. Strongly connected graphs and strongly connected components

Directed graph ： If from the top i To the top j There is a path , It is called from the vertex i To j yes connected Of

If the figure G Any two vertices in i and j All connected , From the top i To j And from vertex j To i There are paths , It's called a picture G yes Strongly connected graph

Directed graph G The maximal strongly connected subgraph in is called G Of Strong connected components . obviously , A strongly connected graph has only one strongly connected component , Namely itself . A non strongly connected graph has multiple strongly connected components

In a non strongly connected Find strong connected components Methods

1. Find the directed ring in the graph
2. Extend the directed ring ： If a vertex has a path to any vertex in the ring , And any vertex in the ring also has a path to this vertex , Then add this vertex

10. Power and net

Each edge in the graph can be attached with a corresponding value , This edge dependent value is called power . Weight can represent the distance from one vertex to another or the cost

A graph with weights on its edges is called With weight chart , Also known as network