Storage structure of graph

This is how to represent a graph in memory

The first way ： Adjacency matrix is used to represent a graph

         In a nutshell , Use two arrays to represent a graph

                1. The first array ： Use a one-dimensional array to store the vertex information in the graph

                2. The second array ： Use a two-dimensional array to store the information of edges and arcs in the graph

        First, the adjacency matrix representation of an undirected graph ：

        

                Let's talk about this two-dimensional matrix , Both the horizontal and vertical directions represent the vertices in the graph , To do so , It is helpful to analyze the relationship between two vertices , For example, direction (v1,v2) This is very consistent with the two-dimensional array arr[v1][v2] A representation of , At this time, if a graph is a directed graph , So the direction is v1->v2,v1 Represents arc tail ,v2 Represents arc head , On behalf of v1 The degree of ,v2 The degree of , Then, for example, in a graph , The number of each vertex is , Don't say no , You can even set it yourself , It should also be set to be numbered  , It's from v0->v4, So there are four vertices in this graph , Then we can put v0 Set to 0 This position , Relative to the following nodes ,v1 On behalf of 1,v2 On behalf of 2, By analogy

                The expression of the above piecewise function means , If (v1,v2) This edge belongs to E(G), So in other words ,v1 And v2 There is an edge , For undirected graphs , Don't think about order , Only need to (v1,v2) Just set it to a value , For example, set the value of this position of the adjacency matrix to 1, There is a connection between the two  , Another thing to say is , Because adjacency matrix is a two-dimensional array , In this array, in addition to considering (v1,v2) Outside this position , Also consider a location (v2,v1), One of these two positions looks horizontally , One looks vertically , Because for an undirected graph , These two positions correspond to (v1,v2) The relationship between these two vertices , therefore , If there is an edge between these two vertices , You need to set the values of both positions to 1.

        

          Let's express a relationship in the above figure , Let's go straight to the code ：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Maximum number of vertices 
#define MAX_VERTEX 30

// Define the graph structure 
typedef struct _graph
{
	// Vertex array , Store vertex names 
	char **vertex;
	// Array of edges 
	int edge[MAX_VERTEX][MAX_VERTEX];
	// Number of vertices 
	int vertex_num;
	// The number of sides 
	int edge_num;
}graph;

// Calculate the position of the user input vertex in the array 
// Here, for example, enter a v1,v2, So for an undirected graph ,(v1,v2) And (v2,v1) All represent the same side 
int calc_vertex_pos(graph &g,char* v)
{
	// Traverse the vertex array 
	for(int i = 0;i < g.vertex_num;i++) {
		// This is equivalent to string comparison 
		if(strcmp(v,g.vertex[i]) == 0) {
			return i;// Find and return directly to this location 
		}
	}
	return -1;
}

// Create a diagram 
void create_graph(graph &g)
{
	printf(" Please enter the number of vertices and edges of the graph : The vertices   edge \n");
	scanf("%d %d",&g.vertex_num,&g.edge_num);
	printf(" Please enter %d A peak value \n",g.vertex_num);

	// Start a loop to assign vertex values to the vertex array 
	// Before assignment, you need to make room on the heap to store the string 
	g.vertex = (char**)malloc(sizeof(char*) * g.vertex_num);
	for(int i = 0;i < g.vertex_num;i++) {
		char str[100] = {0};
		scanf("%s",str);
		// This array points to an allocated space 
		g.vertex[i] = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.vertex[i],str);
	}
	// Initialize the two-dimensional array of edges 
	// Count by the number of vertices n, To form a n*n Two dimensional array of 
	for(int i = 0;i < g.vertex_num;i++) {
		for(int j = 0;j < g.vertex_num;j++) {
			// Initialize all the corresponding edges to 0 Does not exist 
			g.edge[i][j] = 0;
		}
	}

	// The contents of the above two arrays are initialized 
	// Let's set the relationship between edges , Is whether there is an edge 
	printf(" Please enter %d Edges and their corresponding vertices 1, The vertices 2\n",g.edge_num);
	// Set the relationship between two vertices with edges 
	char v1[10];
	char v2[10];
	// How many sides are there , It corresponds to how many vertices there are 
	for(int i = 0;i < g.edge_num;i++) {
		scanf("%s %s",v1,v2);
		// Then we calculate the position of the vertex in the array 
		// yes 0 ah ,1 ah , still 2 Ah, wait, such a relationship 
		int m = calc_vertex_pos(g,v1);// such as v1=0
		int n = calc_vertex_pos(g,v2);//v2 = 1 (0,1) It means there is an edge , Set the position value to 1
		// meanwhile (1,0) This position should also be set to 1, After all, it is an undirected graph 
		g.edge[m][n] = 1;
		g.edge[n][m] = 1;
	}
}

// Print a picture 
void print_graph(graph& g)
{
	// To print a graph is to print this two-dimensional array 
	printf("\t");
	// Loop horizontal vertex header 
	for(int i = 0;i < g.vertex_num;i++) {
		printf("%s\t",g.vertex[i]);
	}
	// Loop through the contents of a two-dimensional array 
	for(int i = 0;i < g.vertex_num;i++) {
		// Print horizontal vertex header 
		printf("\n");// Change one line at a time 
		printf("%s\t",g.vertex[i]);
		// Then output a line of content 
		for(int j = 0;j < g.vertex_num;j++) {
			printf("%d\t",g.edge[i][j]);
		}
	}
	printf("\t");
}


// Build a diagram 
void test01()
{
	graph g;
	create_graph(g);
	print_graph(g);
}

int main() 
{
	test01();
	return 0;			
}

Running results ：

  Let's talk about directed graph , Directed graph , It's just that the sideband has a direction, right , For example, for an undirected graph (v1,v2) and (v2,v1) Actually, they all mean the same thing , What does that mean , It means this side , So for a digraph , If this side is v1->v2, in other words v1 Indicates fox tail ,v2 It means fox head ,v1 The degree of ,v2 The degree of , So at this point (v1,v2) And (v2,v1) It's not the same thing ,(v1,v2) To express v1->v2, that (v2,v1) How is this coordinate represented in the adjacency matrix ？ In fact, we can set an impossible value at this position , Then other , Let's set a weight , Why don't you say that the position irrelevant to the direction is set to 0, because 0 It may also represent weight , The general weight represents the distance between the two points , Time, these related things . This is the design idea of directed graph , Let's use a picture to show

Don't talk much , Go straight to the code ;

directed_graph.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
// Maximum number of vertices 
#define MAX_VERTEX 30

// Define the graph structure 
typedef struct _graph
{
	// Vertex array , Store vertex names 
	char **vertex;
	// Array of edges 
	int edge[MAX_VERTEX][MAX_VERTEX];
	// Number of vertices 
	int vertex_num;
	// The number of sides 
	int edge_num;
}graph;

// Calculate the position of the user input vertex in the array 
// Here, for example, enter a v1,v2, So for an undirected graph ,(v1,v2) And (v2,v1) All represent the same side 
int calc_vertex_pos(graph &g,char* v)
{
	// Traverse the vertex array 
	for(int i = 0;i < g.vertex_num;i++) {
		// This is equivalent to string comparison 
		if(strcmp(v,g.vertex[i]) == 0) {
			return i;// Find and return directly to this location 
		}
	}
	return -1;
}

// Create a diagram 
void create_graph(graph &g)
{
	printf(" Please enter the number of vertices and edges of the graph : The vertices   edge \n");
	scanf("%d %d",&g.vertex_num,&g.edge_num);
	printf(" Please enter %d A peak value \n",g.vertex_num);

	// Start a loop to assign vertex values to the vertex array 
	// Before assignment, you need to make room on the heap to store the string 
	g.vertex = (char**)malloc(sizeof(char*) * g.vertex_num);
	for(int i = 0;i < g.vertex_num;i++) {
		char str[100] = {0};
		scanf("%s",str);
		// This array points to an allocated space 
		g.vertex[i] = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.vertex[i],str);
	}
	// Initialize the two-dimensional array of edges 
	// Count by the number of vertices n, To form a n*n Two dimensional array of 
	for(int i = 0;i < g.vertex_num;i++) {
		for(int j = 0;j < g.vertex_num;j++) {
			// For digraphs , These points should be initialized to an unlikely value 
			g.edge[i][j] = INT_MAX;
		}
	}

	// The contents of the above two arrays are initialized 
	// Let's set the relationship between edges , Is whether there is an edge 
	printf(" Please enter %d Edges and their corresponding vertices 1, The vertices 2\n",g.edge_num);
	// Set the relationship between two vertices with edges 
	char v1[10];
	char v2[10];
	// Set a weight 
	int weight;
	// How many sides are there , It corresponds to how many vertices there are 
	for(int i = 0;i < g.edge_num;i++) {
		scanf("%s %s %d",v1,v2,&weight);
		// Then we calculate the position of the vertex in the array 
		// yes 0 ah ,1 ah , still 2 Ah, wait, such a relationship 
		int m = calc_vertex_pos(g,v1);// such as v1=0
		int n = calc_vertex_pos(g,v2);//v2 = 1 (0,1) It means there is an edge , Set the position value to 1
		// Now these two points have directions , So it's impossible to set them , There is only one direction 
		g.edge[m][n] = weight;// Directly change to weight 
	}
}

// Print a picture 
void print_graph(graph& g)
{
	// To print a graph is to print this two-dimensional array 
	printf("\t");
	// Loop horizontal vertex header 
	for(int i = 0;i < g.vertex_num;i++) {
		printf("%s\t",g.vertex[i]);
	}
	// Loop through the contents of a two-dimensional array 
	for(int i = 0;i < g.vertex_num;i++) {
		// Print horizontal vertex header 
		printf("\n");// Change one line at a time 
		printf("%s\t",g.vertex[i]);
		// Then output a line of content 
		for(int j = 0;j < g.vertex_num;j++) {
			printf("%d\t",g.edge[i][j]);
		}
	}
	printf("\t");
}


// Build a diagram 
void test01()
{
	graph g;
	create_graph(g);
	print_graph(g);
}

int main() 
{
	test01();
	return 0;			
}

  The expression of adjacency matrix is described above , What about this method , Is to use two-dimensional array to do , So if there are too many points , With fewer edges , Space 、 Time is a waste , therefore , In order to avoid wasting too much space, we can use adjacency table to do it , Its meaning is similar to opening up space on memory , When there is a relationship between two vertices , Just open a memory to indicate this relationship , So it won't waste space , It is difficult to implement

Let's talk about using adjacency table to realize undirected graph ：

First, let's analyze the data structure ：

        

Let's analyze the idea of inserting each vertex ：

         

continue

 

  continue

  Say something else ;

Upper undirected graph complete code ：

undirected_graph1.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// The maximum number of vertices that can be stored 
#define MAX_VERTEX 100

struct edge_node {
	int position;// The said vertex Which node index in the array 
	edge_node *next;// Store the pointer of the next adjacent contact 
	// The weight here can be written or not 
};

struct vertex {
	char *name;// Store vertex names , The first level pointer points to the space allocated on a heap 
	// There is also the storage of each adjacent first adjacent contact , In fact, here it is equivalent to the head node 
	edge_node *first_node;
};

// Finally, you need the structure of the whole graph 
// To store the information of the corresponding diagram 
struct graph {
	// Store all the information of the vertex 
	vertex head[MAX_VERTEX];
	// Number of vertices and edges 
	int vertex_num;
	int edge_num;
};



// Let's determine the vertex position 
int find_pos(graph &g,char *v)// here v If there is a point, you can print , I mean scanf It's impossible to assign values directly 
{
	for (int i = 0; i < g.vertex_num; i++) {
		// Loop the space where the vertex names are stored 
		if (strcmp(g.head[i].name, v) == 0) {
			return i;
		}
	}
	return -1;
}

// Let's create a diagram first 
void create_graph(graph &g)
{
	printf(" Please enter the number of vertices and edges :\n");
	scanf("%d %d", &g.vertex_num, &g.edge_num);
	// Cycle through the values of the vertices 
	printf(" Please enter %d A peak value :\n", g.vertex_num);
	// Loop to assign values to vertices 
	for (int i = 0; i < g.vertex_num; i++){
		char str[30] = { 0 };
		scanf("%s", str);
		// pure scanf("%s",&g.head[i].name) Definitely not , This name It's a two-level pointer 
		g.head[i].name = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.head[i].name, str);// In which index position to store the vertex 
		// In addition to the assignment string , You also need to initialize the address of an adjacent node 
		g.head[i].first_node = NULL;// Similar to every overhead point next Is full of NULL
	}

	// Let's start by entering edges , That is, two vertices 
	printf(" Please enter %d side , The vertices 1, The vertices 2", g.edge_num);
	char v1[10];
	char v2[10];
	// Loop to assign values to edges 
	for (int i = 0; i < g.edge_num; i++) {
		scanf("%s %s", v1,v2);
		int m = find_pos(g, v1);
		int n = find_pos(g, v2);
		// Number of each vertex found in memory 
		// And then for example m Is it the head representing a vertex , Here you can. 
		// As the head of the linked list 
		// Then we implement header insertion , To express a connection 
		// Finally, we implement an interaction of the relationship , This is for an undirected graph v1 And v2 and v2 And v1 Same relationship 
		
		// Create a new adjacency point 
		edge_node *p_new = (edge_node*)malloc(sizeof(edge_node));
		// Then start inserting... In the head , This head is m spot 
		p_new->position = n;
		// here p_new Must first refer to 
		p_new->next = g.head[m].first_node;
		g.head[m].first_node = p_new;

		// Then implement v0 And v1 An alternation of , It means 
		edge_node *p_new1 = (edge_node*)malloc(sizeof(edge_node));
		// In fact, it is to achieve a m And n Alternation of 
		p_new1->position = m;
		p_new1->next = g.head[n].first_node;
		g.head[n].first_node = p_new1;
	}
}


// Print this picture 
void print_graph(graph &g)
{
	for (int i = 0; i < g.vertex_num; i++) {
		printf("%s: ", g.head[i].name);
		// Get the head node to traverse a single linked list 
		edge_node *p_node =  g.head[i].first_node;
		while (p_node != NULL) {
			// Get is n, Looking for it m
			int index = p_node->position;
			printf("%s ", g.head[index].name);
			p_node = p_node->next;
		}
		// Line break 
		printf("\n");
	}
}

int main()
{
	graph g;
	create_graph(g);
	print_graph(g);
	return 0;
}

  Running results ：

    How to implement a directed graph , For example, the following digraph

     

        For digraphs , Nothing more than to delete the places where the above code needs to handle the inversion , because v0 v1 And v1 v0 It is no longer a meaning , Go straight to the code

        directed_graph1.cpp

        

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// The maximum number of vertices that can be stored 
#define MAX_VERTEX 100

struct edge_node {
	int position;// The said vertex Which node index in the array 
	edge_node *next;// Store the pointer of the next adjacent contact 
	// The weight here can be written or not 
};

struct vertex {
	char *name;// Store vertex names , The first level pointer points to the space allocated on a heap 
	// There is also the storage of each adjacent first adjacent contact , In fact, here it is equivalent to the head node 
	edge_node *first_node;
};

// Finally, you need the structure of the whole graph 
// To store the information of the corresponding diagram 
struct graph {
	// Store all the information of the vertex 
	vertex head[MAX_VERTEX];
	// Number of vertices and edges 
	int vertex_num;
	int edge_num;
};



// Let's determine the vertex position 
int find_pos(graph &g,char *v)// here v If there is a point, you can print , I mean scanf It's impossible to assign values directly 
{
	for (int i = 0; i < g.vertex_num; i++) {
		// Loop the space where the vertex names are stored 
		if (strcmp(g.head[i].name, v) == 0) {
			return i;
		}
	}
	return -1;
}

// Let's create a diagram first 
void create_graph(graph &g)
{
	printf(" Please enter the number of vertices and edges :\n");
	scanf("%d %d", &g.vertex_num, &g.edge_num);
	// Cycle through the values of the vertices 
	printf(" Please enter %d A peak value :\n", g.vertex_num);
	// Loop to assign values to vertices 
	for (int i = 0; i < g.vertex_num; i++){
		char str[30] = { 0 };
		scanf("%s", str);
		// pure scanf("%s",&g.head[i].name) Definitely not , This name It's a two-level pointer 
		g.head[i].name = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.head[i].name, str);// In which index position to store the vertex 
		// In addition to the assignment string , You also need to initialize the address of an adjacent node 
		g.head[i].first_node = NULL;// Similar to every overhead point next Is full of NULL
	}

	// Let's start by entering edges , That is, two vertices 
	printf(" Please enter %d side , The vertices 1, The vertices 2", g.edge_num);
	char v1[10];
	char v2[10];
	// Loop to assign values to edges 
	for (int i = 0; i < g.edge_num; i++) {
		scanf("%s %s", v1,v2);
		int m = find_pos(g, v1);
		int n = find_pos(g, v2);
		// Number of each vertex found in memory 
		// And then for example m Is it the head representing a vertex , Here you can. 
		// As the head of the linked list 
		// Then we implement header insertion , To express a connection 
		// Finally, we implement an interaction of the relationship , This is for an undirected graph v1 And v2 and v2 And v1 Same relationship 
		
		// Create a new adjacency point 
		edge_node *p_new = (edge_node*)malloc(sizeof(edge_node));
		// Then start inserting... In the head , This head is m spot 
		p_new->position = n;
		// here p_new Must first refer to 
		p_new->next = g.head[m].first_node;
		g.head[m].first_node = p_new;
/*
 *  Just annotate this position in the digraph 
		// Then implement v0 And v1 An alternation of , It means 
		edge_node *p_new1 = (edge_node*)malloc(sizeof(edge_node));
		// In fact, it is to achieve a m And n Alternation of 
		p_new1->position = m;
		p_new1->next = g.head[n].first_node;
		g.head[n].first_node = p_new1;
*/
	}
}


// Print this picture 
void print_graph(graph &g)
{
	for (int i = 0; i < g.vertex_num; i++) {
		printf("%s: ", g.head[i].name);
		// Get the head node to traverse a single linked list 
		edge_node *p_node =  g.head[i].first_node;
		while (p_node != NULL) {
			// Get is n, Looking for it m
			int index = p_node->position;
			printf("%s ", g.head[index].name);
			p_node = p_node->next;
		}
		// Line break 
		printf("\n");
	}
}

int main()
{
	graph g;
	create_graph(g);
	print_graph(g);
	return 0;
}

Running results ：

    The directed graph and the undirected graph are all done .