Storage structure of graph (adjacency matrix)

1. The adjacency matrix of a graph (Adjacency Matrix) The storage method is to use two arrays to represent the graph . A one-dimensional array stores vertex information in a graph , A two-dimensional array ( It's called adjacency matrix ) Stores information about the edges or arcs in a graph .
2. Undirected graph
   We can set up two arrays , The vertex array is vertex[4]={V0,V1,V2,V3}, Edge array arc[4][4] Is symmetric matrix (0 Indicates that there are no edges between vertices ,1 Indicates that there are edges between vertices ).
   Symmetric matrix ： The so-called symmetric matrix is n The elements of a matrix of order satisfy a[i][j]=a[j][i] (0<=i,j<=n). That is, the main diagonal from the upper left corner to the lower right corner of the matrix is the axis , The elements in the upper right corner and the corresponding elements in the lower left corner are all equal .
   With this two-dimensional array of symmetric matrix , We can easily know the information in the diagram ：
   – It is very easy to determine whether any two vertices have edges or not ;
   – You know the degree of a vertex , In fact, this is the peak Vi In the adjacency matrix, the first one is i That's ok ( Or the first i Column ) The sum of the elements of ;
   – Seek the summit Vi All the adjacent nodes of the matrix are i Scan the elements again ,arc[i][j] by 1 It's the adjacency point .

3. Directed graph
Visible vertex array vertex[4]={V0,V1,V2,V3}, Arc array arc[4][4] It's also a matrix , But because it's a digraph , So this matrix is not asymmetric , For example, by V1 To V0 Have an arc , obtain arc[1][0]=1, and V0 To V1 There is no arc , therefore arc[0][1]=0.
The other thing is that there is a directed graph , To consider the degree of entry and exit , The vertices V1 The degree of entry is 1, It happens to be the V1 The sum of the numbers in the column , The vertices V1 The degree of departure is 2, It happens to be the V1 The sum of the numbers of rows .

4. Weighted graph per edge or arc （ network ）

The infinite value is set as the weight of an exception , Judge whether the value is abnormal to see whether the edge or arc exists .