“This is the 26th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

7.2 Abstract data types for graphs

ADT Graph Data vertex finite non-empty set and edge set. Operation CreateGraph (*G,V,VR) : Construct graph G from the definition of vertex set V and edge arc set VR. DestroyGraph(*G) : Destroy the graph if G exists. LocateVex(G,u) : Returns the position in graph G if vertex U exists. GetVex (G,v) : Returns the value of vertex V in graph G. PutVex (G,v,value) : assign value to vertex V in graph G. FirstAdjVex (G,*v) : Returns an adjacency of vertex v, null if the vertex has no adjacency in G. NextAdjVex (G,v,*w) : Returns the next adjacency of vertex V relative to vertex W, or "null" if w is the last adjacency of v. InsertVex (*G,v) : Adds a new vertex v to graph G. DeleteVex (*G,v): Deletes vertex V and its associated arcs in graph G. InsertArc (*G,v,w): InsertArc <v,w> in graph G. If G is undirected, add symmetrical arc <w,v>. DeleteArc (*G,v,w): deletes arcs <v,w> from graph G, and symmetric arcs DFSTraverse(G): used for depth-first traverse of the circle G and called for each vertex during traverse. HFSTraverse(G) : breadth-first traverse of graph G, called for each vertex during traverse. endADTCopy the code

7.3 Storage Structure of Figure

7.3.1 Tie matrix

A graph’s Adjacency Matrix is stored as two arrays representing the graph. A one-dimensional array stores information about vertices in the graph, and a two-dimensional array (called an adjacency matrix) stores information about edges or arcs in the graph.

1. Adjacency matrix of undirected graph

2. Adjacency matrix of digraph

Analysis 1: The adjacency matrix of a digraph may be asymmetric. Analysis 2: Vertex out degree = sum of row I elements vertex in degree = sum of column I elements vertex in degree = sum of row I elements + sum of JTH elements

3. Adjacency matrix representation of nets (i.e. power graphs)

Code implementation:

Use two arrays to store the vertex table and adjacency matrix respectively

#define MVNum 100 #define MVNum 100 typedef char VerTexType; // let the data type of the vertex be a character typedef int ArcType; Typepedef struct{VerTexType vexs{MVNum]; ArcType arcs[MVNum][MVNum]; Int vexnum, arcnum; // The current number of points and edges of the graph. }AMGraph; // Adjacency Matrix GraphCopy the code