This is the 21st day of my participation in the August Text Challenge.More challenges in August

The storage structure of the graph

1. Adjacency matrix method

A one-dimensional array is used to store the information of vertices in the graph, and A two-dimensional array is used to store the information of edges in the graph. The two-dimensional array that stores the adjacency relations between vertices is called adjacency matrix pair unweighted graph. The adjacency matrix A of graph G with node number N is N × N.

A one-dimensional array is used to store the information of vertices in the graph, a two-dimensional array is used to store the information of edges in the graph, and the two-dimensional array that stores the adjacency relationship between vertices is called adjacency matrix

For weighted graphs, the adjacency matrix A of graph G with node number N is n by n.

The adjacency matrix of the graph stores the structure definition code

#define  MaxVertexNum  100        // Maximum number of vertices
typedef  char  VertexType;            // Data type of the vertex
typedef int EdgeType; // The data type of the edge weights in the weighted graph
typedef  struct{
VertexType Vex[MaxVertexNum]; / / vertex table
EdgeType  Edge[MaxVertexNum][MaxVertexNum];  // adjacency matrix, edge list
int  vexnum,arcnum;                               // The current number of vertices and arcs of the graph
}MGraph;
Copy the code

A one-dimensional array is used to store the information of vertices in the graph, a two-dimensional array is used to store the information of edges in the graph, and the two-dimensional array that stores the adjacency relationship between vertices is called adjacency matrix

Pay attention to

  • The adjacency matrix of undirected graph is symmetric matrix, and the adjacency matrix of large scale can be compressed
  • The spatial complexity of the adjacency matrix representation is O(𝑛2), where n is the number of vertices of the graph 𝑉
  • For undirected graphs, the number of non-zero elements (or non-infinity elements) in the ith row (or column) of the adjacency matrix is exactly the degree TD(𝑉𝑖) of the ith vertex.
  • For digraph, the number of non-zero elements (or non-infinity elements) in the ith row (or column) of the adjacency matrix is exactly the output OD(𝑉𝑖) (or input ID(𝑉𝑖) of the ith vertex.
  • The adjacency matrix method is used to store graphs, and it only takes O(1) time complexity to determine whether any two vertices in the graph are connected by an edge
  • But to determine how many edges there are in the graph, the entire two-dimensional array must be traversed in time O(𝑛2)
  • Dense graphs are suitable for the stored representation of adjacency matrices

2. Adjacency list

A singlelinked list is established for each vertex 𝑣𝑖 in graph G. The nodes in the ith singlelinked list represent edges attached to vertex 𝑣𝑖 (the arc ending vertex 𝑣𝑖 in the digraph). This singlelinked list is called vertex 𝑣𝑖 (the edge-out list is called for digraph)

Undirected graph adjacency list method

Directed graph adjacency list method

The adjacency list method of the graph stores the structure definition code

#define  MaxVertexNum  100     // The maximum number of vertices in the graph
typedef  struct  ArcNode{            // Side table node
int  adjvex;                              // The vertex to which the arc points
struct  ArcNode  *next;        // Pointer to the next arc
//InfoType info; // Net weights
}ArcNode;
typedef   struct  VNode{             // Vertex table node
VertexType  data;                 // Vertex information
ArcNode  *first;                    // a pointer to the first arc attached to the vertex
}VNode,AdjList[MaxVertexNum]; 
typedef  struct{
AdjList  vertices; / / adjacency list
int  vexnum,arcnum;        // The number of vertices and arcs
}ALGraph;
Copy the code

Pay attention to

  • The undirected graph, the required storage space for O (| V | | | E + 2)
  • The directed graph, the required storage space for O (| | V + | E |)
  • Using adjacency list to represent sparse graph can greatly save storage space
  • Finding all the adjacent edges of a given vertex takes only O(1) time in the adjacency list, and O(n) time in the adjacency matrix for scanning one row for the same operation.
  • To determine whether there is an edge between two given vertices, the adjacency matrix only needs O(1) time complexity, while the adjacency list needs to look up the edge list of corresponding nodes, which is inefficient
  • For the adjacency list representation of directed graphs, it is necessary to scan the corresponding edge list to find the output of a given vertex, but to find its input requires traversing the entire adjacency list
  • The adjacency list representation of a graph is not unique, because the link order of edge nodes in the single linked list corresponding to each vertex can be arbitrary