Details of the diagram

1. Explanation of terms:

• A graph (Graph) is composed of a finite non-empty set of vertices and a set of edges between vertices, usually expressed as: G(V, E), where G represents a graph, V is the set of vertices in the graph G, and E is the set of edges in the graph G. The data elements in the graph are called vertices, and the Vertex set is finite and non-empty. In a graph, there may be a relationship between any two vertices, the logical relationship between vertices is represented by edges, and the edge set can be empty.
• Graphs are divided into undirected graphs and directed graphs according to the presence or absence of edges. An undirected graph consists of vertices and edges, and a directed graph consists of vertices and arcs. An arc is divided into an arc tail and an arc head, and the end with an arrow is the arc head.
• The graph is divided into sparse and dense graphs according to the number of edges or arcs. If there is an edge between any two vertices in the graph, it is called a complete graph, and a directed graph is called a directed complete graph. A graph is called simple if there are no duplicate edges or edges from vertices to itself.
• There are concepts of adjacency and attachment between vertices in the graph. The number of edges of an undirected graph vertex is called the degree. Directed graph vertices are divided into in-degree and out-degree.
• Edges or arcs with weights on the graph are called nets.
• There is a path between vertices in the graph, and the existence of a path between two vertices indicates that they are connected. If the path eventually returns to the starting point, it is called a cycle, and the one that does not repeat is called a simple path. If any two vertices are connected, the graph is a connected graph, and if it is directed, it is called a strongly connected graph. There are subgraphs in the graph. If the subgraphs are maximally connected, they are connected components. If they are directed, they are called strongly connected components.
• An undirected graph that is connected and has n vertices and n-1 edges is called a spanning tree (similar in structure to a sloping tree). In a directed graph, a vertex whose in-degree is 0 and the other vertices whose in-degree is 1 is called a directed tree. A directed graph consists of several directed trees to form a generative forest.

2. The storage structure of the graph - the adjacency matrix (two arrays, one one-dimensional, one two-dimensional)

The representation of the adjacency matrix of the graph requires two arrays to represent the information of the graph, a one-dimensional array representing the information of each data element, and a two-dimensional array (adjacency matrix) representing the information of the edges or arcs in the graph.

If the graph has n vertices, then the adjacency matrix is ​​an n*n square matrix, and the value of each element in the square matrix is ​​calculated as follows:

A specific example of an adjacency matrix representation graph is shown in the following figure:

First give an example of an undirected graph:

The following is an example of a directed graph:

OK, so far, we have given an adjacency matrix for an undirected graph and an adjacency matrix for a directed graph, and we can draw some conclusions from these two adjacency matrices:

• The adjacency matrices of undirected graphs are all diagonally symmetric
• To know the degree of a vertex in an undirected graph (the number of edges of an undirected graph vertex), it is actually the sum of the elements of this vertex vi in ​​the i-th row or (i-th column) in the adjacency matrix; for example, the degree of v1 is 2
• For a directed graph, to know the out-degree of a vertex, it is actually the sum of the elements in the i-th row of the vertex vi in ​​the adjacency matrix. If you want to know the in-degree of a vertex, it is the sum of the elements in the i-th column. . The out-degree looks at the sum of this row, and the in-degree looks at the sum of this column

However, if the graph we need to represent is a net, for example, suppose there is a graph with n vertices, and the adjacency matrix of the net is also an n*n square matrix, but the values ​​of the square matrix elements are calculated differently. As shown below:

Here Wij represents the weights on the edges of two vertices vi and vj. Infinity represents a value that a computer allows, greater than the weights on all edges, that is, an impossible limit. The following is a concrete example, representing a directed net's graph and adjacency matrix:

3. The storage structure of the graph - the code implementation of the adjacency matrix.

#include<iostream>
using namespace std;
enum Graphkind{ DG, DN, UDG, UDN }; //{directed graph, undirected graph, directed net, undirected net}
typedef struct  Node
{
int * vex;  //vertex array
int vexnum; //number of vertices
int edge;   //number of edges in the graph
int ** adjMatrix; //The adjacency matrix of the graph
enum Graphkind kind;
}MGraph;
void createGraph(MGraph & G,enum Graphkind kind)
{
cout << "Enter the number of vertices" << endl;
cin >> G.vexnum;
cout << "Enter the number of edges" << endl;
cin >> G.edge;
//Type of input
//cout << "Type of input graph: DG: directed graph DN: undirected graph, UDG: directed network, UDN: undirected network" << endl;
G.kind = kind;
//Make room for two arrays
G.vex = new int[G.vexnum];
G.adjMatrix = new int*[G.vexnum];
cout << G.vexnum << endl;
int i;
for (i = 0; i < G.vexnum; i++)
{
    G.adjMatrix[i] = new int[G.vexnum];
}
for (i = 0; i < G.vexnum; i++)
{
    for (int k = 0; k < G.vexnum; k++)
    {
        if (G.kind == DG || G.kind == DN)
        {
            G.adjMatrix[i][k] = 0;
        }
        else {
            G.adjMatrix[i][k] = INT_MAX;
        }
    }

}
/*//Enter the information of each element, this information does not need to be used now
for (i = 0; i < G.vexnum; i++)
{
    cin >> G.vex[i];
}*/
cout << "Please enter the serial numbers of two related vertices: for example: 1 2 means vertex 1 points to vertex 2" << endl;
for (i = 0; i < G.edge; i++)
{
    int a, b;
    cin >> a;
    cin >> b;
    if (G.kind == DN) {
        G.adjMatrix[b - 1][a - 1] = 1;
        G.adjMatrix[a - 1][b - 1] = 1;
    }
    else if (G.kind == DG)
    {
        G.adjMatrix[a - 1][b - 1] = 1;
    }
    else if (G.kind == UDG)
    {
        int weight;
        cout << "Enter the weight for this edge:" << endl;
        cin >> weight;
        G.adjMatrix[a - 1][b - 1] = weight;
    }
    else {
        int weight;
        cout << "Enter the weight for this edge:" << endl;
        cin >> weight;
        G.adjMatrix[b - 1][a - 1] = weight;
        G.adjMatrix[a - 1][b - 1] = weight;
    }
}

void print(MGraph g)
{
	int i, j;
	for (i = 0; i < g.vexnum; i++)
	{
		for (j = 0; j < g.vexnum; j++)
		{
		
			if (g.adjMatrix[i][j] == INT_MAX)
			cout << "∞" << " ";
			else
			cout << g.adjMatrix[i][j] << " ";
		
		}
		cout << endl;
	}
}

void clear(MGraph G)
{
delete G.vex;
G.vex = NULL;
	for (int i = 0; i < G.vexnum; i++)
	{
	delete G.adjMatrix[i];
	G.adjMatrix[i] = NULL;
	}
delete G.adjMatrix;
}
//If the error is reported, it may be that g and G of void do not have *
int main()
{
    MGraph G;
    cout << "Directed graph example:" << endl;
    createGraph(G, DG);
    print(G);
    clear(G);
    cout << endl;
    cout << "Undirected graph example:" << endl;
    createGraph(G, DN);
    print(G);
    clear(G);

    cout << endl;
    cout << "An example of a directed graph network:" << endl;
    createGraph(G, UDG);
    print(G);
    clear(G);

    cout << endl;
    cout << "An example of an undirected graph network:" << endl;
    createGraph(G, UDN);
    print(G);
    clear(G);

    cout << endl;
return 0;
}

Output result:

4. The storage structure of the graph - the advantages and disadvantages of the adjacency matrix

• advantage:
  Intuitive and easy to understand, you can easily determine whether any two vertices have an edge. The biggest advantage is that it is easy to calculate the degree of each vertex.
• shortcoming:
  When I represent a complete graph, the adjacency matrix is ​​the best way to represent it, but for a sparse matrix, because it has fewer edges but more vertices, it will cause a waste of space. (suitable for complete graphs, not suitable for sparse matrices)

5. The storage structure of the graph - the adjacency list (two structures)

An adjacency list is a chained storage structure for a graph. It is mainly to deal with the problem of wasting space when the adjacency matrix has few vertices. It does this by declaring two structures. As shown below:

            A head node and a table node

OK, although we know that the adjacency list is represented by these two structures, then how is it represented? Don't worry, let's convert it to c++ code first, and then give an example, you will understand .

typedef char Vertextype;

//table node structure
struct ArcNode {
	int adjvex;   //The position of the vertex pointed to by an edge (usually an array index).
	ArcNode * nextarc; //point to the next table node
	int weight;   //This only needs to be used for netmaps. Ordinary graphs can be ignored directly
};

//head node
struct Vnode
{
	Vertextype data;  //This is to record the information of each vertex (now generally do not need to use how)
	ArcNode * firstarc; //Point to the first piece of information attached to this vertex edge (table node)
};

Example of an undirected graph:

From the figure, we can know that the vertices are saved by a one-dimensional array of the head node type, in which the firstarc of each head node points to the first piece of information attached to the vertex edge, the adjvex of the table node Indicates the subscript of another vertex of the edge in the vertex array. The weight field is meaningless for ordinary graphs and can be ignored. nextarc points to the information of the next edge attached to the vertex.

Here is another example of a directed graph:

Through the above two examples, we should understand how the adjacency list represents the information of the graph.

General network weights

6. The storage structure of the graph - the code implementation of the adjacency list

#include<iostream>
#include<string>
using namespace std;

typedef string Vertextype;

//table node structure
struct ArcNode {
		int adjvex;   //The position of the vertex pointed to by an edge (usually an array index).
		ArcNode * nextarc; //point to the next table node
		int weight;   //This only needs to be used for netmaps.
};

//head node
struct Vnode
{
		Vertextype data;  //This is to record the information of each vertex (now generally do not need to use how)
		ArcNode * firstarc; //Point to the first piece of information attached to this vertex edge (table node)
};

//picture
struct Graph
{
		int kind;  //Type of graph (directed graph: 0, undirected graph: 1, directed net: 2, undirected net: 3)
		int vexnum; //number of vertices in the graph
		int edge;  //number of edges in the graph
		Vnode * node; //Array of (vertex) head nodes of the graph
};
void createGraph(Graph &g,int kind)
{
		cout << "Please enter the number of vertices:" << endl;
		cin >> g.vexnum;
		cout << "Please enter the number of edges (undirected graph/The net is multiplied by 2):" << endl;
		cin >> g.edge;
		g.kind = kind; //Determine the type of graph
		g.node = new Vnode[g.vexnum];
 
		int i;
		cout << "Enter information for each vertex:" << endl;//record information for each vertex
		for (i = 0; i < g.vexnum; i++)
		{
				cin >> g.node[i].data;
				g.node[i].firstarc=NULL;
		}

		cout << "Please enter the start and end numbers of each edge:" << endl;
		for (i = 0; i < g.edge; i++)
		{
		    int a;
		    int b;
		    cin >> a; //starting point
		    cin >> b; //end
		    ArcNode * next=new ArcNode;
		    next->adjvex = b - 1;
		    if(kind==0 || kind==1)
		    next->weight = -1;
		    else {//If it is a network graph, it also needs weights
		        cout << "Enter the weight for this edge:" << endl;
		        cin >> next->weight;
		    }
		    next->nextarc = NULL;
		
		    //concatenate edges
		    if (g.node[a - 1].firstarc == NULL) {
		        g.node[a - 1].firstarc=next;
		
		    }
		    else
		    {
		        ArcNode * p;
		        p = g.node[a - 1].firstarc;
		        while (p->nextarc)//Find the last table node of the linked list
		        {
		            p = p->nextarc;
		        }
		        p->nextarc = next;
		    }
		}
}

void print(Graph  g)
{
		int i;
		cout << "The adjacency list of the graph is:" << endl;
		for (i = 0; i < g.vexnum; i++)
		{
				cout << g.node[i].data<<" ";
				ArcNode * now;
				now = g.node[i].firstarc;
				while (now)
				{
						cout << now->adjvex << " ";
						now = now->nextarc;
				}
				cout << endl;
		}
}

int main()
{
		Graph g;
		cout << "Directed graph example" << endl;
		createGraph(g,0);
		print(g);
		cout << endl;

		cout << "An example of an undirected graph" << endl;
		createGraph(g, 1);
		print(g);
		cout << endl;
		return 0;
}

Output result:

7. The storage structure of the graph - the advantages and disadvantages of the adjacency list

• advantage:
  For sparse graphs, adjacency lists are more space efficient than adjacency matrices.
• shortcoming:
  It is not easy to judge whether two vertices are related (edges), the out-degree of a vertex is easy, but the in-degree needs to traverse the entire adjacency list.