Structure de stockage des graphiques

C'est comme ça qu'une image en mémoire

La première façon：Une matrice de contiguïté est utilisée pour représenter un graphique

        En termes simples,,Utilisez deux tableaux pour représenter un graphique

                1.Premier tableau：Utilisez un tableau unidimensionnel pour stocker les informations Vertex dans le diagramme

                2.Deuxième tableau：Stocker des informations sur les bords et les arcs d'un graphique à l'aide d'un tableau bidimensionnel

        Tout d'abord, la représentation matricielle de contiguïté des graphiques non rectés：

        

                Prenons cette matrice bidimensionnelle,Les sommets de ce dessin sont représentés horizontalement et verticalement,Fais - le.,Aide à analyser la relation entre les deux sommets,Comme la direction(v1,v2)Ceci correspond parfaitement au tableau bidimensionnelarr[v1][v2]Une représentation de,Si un graphique est dirigé,Alors la direction estv1->v2,v1Pour la queue d'arc,v2Pour la tête d'arc,Représentant égalementv1Sortie,v2Pénétration,Et comme dans un graphique,Le numéro de chaque Vertex est,Ne dis pas non.,Même si tu le fais toi - même,Aussi à numéroter ,Dev0->v4,Donc ça veut dire qu'il y a quatre sommets dans ce graphique,Alors on pourra mettrev0Set to0Cette position,Par rapport aux noeuds suivants,v1Juste au nom de1,v2Juste au nom de2,Par analogie

                La fonction de segmentation ci - dessus signifie ,Si(v1,v2) Ce côté appartient à E(G),Donc ça veut dire,v1Avecv2Il y a un bord,Pour les graphiques non rectés, Sans tenir compte de l'ordre ,Il suffit de(v1,v2) C'est une valeur numérique. , Par exemple, définissez la valeur de cette position de la matrice de contiguïté à 1, Indique qu'il y a un lien entre les deux  , Il y a une autre chose à dire. , Parce que la matrice de contiguïté est un tableau bidimensionnel , Dans ce tableau, en plus de considérer (v1,v2) En dehors de cette position , Et un endroit à considérer (v2,v1), L'un d'eux regarde le paysage. , Une vue longitudinale , Parce que pour les graphiques non rectés, , Les deux positions correspondent (v1,v2) La relation entre ces deux sommets ,Alors..., S'il y a un bord entre ces deux sommets , Vous devez définir les valeurs pour les deux positions à 1.

        

          Nous allons juste montrer une sorte de relation dans le graphique ci - dessus. ,En haut du Code：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Nombre maximum de sommets
#define MAX_VERTEX 30

// Définir la structure du diagramme 
typedef struct _graph
{
	//Tableau vertex, Stocker le nom du vertex 
	char **vertex;
	// Tableau des bords 
	int edge[MAX_VERTEX][MAX_VERTEX];
	//Nombre de sommets
	int vertex_num;
	//Le nombre de côtés
	int edge_num;
}graph;

// Calculer la position des sommets entrés par l'utilisateur dans le tableau 
// C'est comme entrer un v1,v2, Donc pour les graphiques non rectés, ,(v1,v2)Avec(v2,v1) C'est le même côté. 
int calc_vertex_pos(graph &g,char* v)
{
	//Traverser le tableau Vertex
	for(int i = 0;i < g.vertex_num;i++) {
		// C'est une comparaison de chaînes. 
		if(strcmp(v,g.vertex[i]) == 0) {
			return i;// Retour direct à cet endroit 
		}
	}
	return -1;
}

//Créer un graphique
void create_graph(graph &g)
{
	printf(" Veuillez saisir le nombre de sommets et de bords du diagramme :Vertex Edge\n");
	scanf("%d %d",&g.vertex_num,&g.edge_num);
	printf("Veuillez entrer%dValeurs Vertex\n",g.vertex_num);

	// Démarrer la boucle pour assigner une valeur Vertex au tableau vertex 
	// Besoin d'espace sur le tas pour stocker les chaînes avant l'affectation 
	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);
		// Ce tableau pointe à nouveau vers un espace assigné 
		g.vertex[i] = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.vertex[i],str);
	}
	// Initialiser le tableau bidimensionnel des bords 
	// En nombre de sommets n,Pour former unn*nUn tableau bidimensionnel de
	for(int i = 0;i < g.vertex_num;i++) {
		for(int j = 0;j < g.vertex_num;j++) {
			// Initialiser tous les bords correspondants à 0Indique qu'il n'existe pas
			g.edge[i][j] = 0;
		}
	}

	// Les deux tableaux ci - dessus sont initialisés 
	// Définir la relation entre les bords , Est - ce qu'il y a des bords 
	printf("Veuillez entrer%d Bords et sommets correspondants 1,Vertex2\n",g.edge_num);
	// Définir la relation entre deux sommets bordés 
	char v1[10];
	char v2[10];
	// Combien de côtés , Ça correspond au nombre de sommets. 
	for(int i = 0;i < g.edge_num;i++) {
		scanf("%s %s",v1,v2);
		// Ensuite, nous calculons la position des sommets dans le tableau 
		//- Oui.0Oh là là!,1Oh là là!,Toujours2 Attends, c'est une relation. 
		int m = calc_vertex_pos(g,v1);//Par exemple,v1=0
		int n = calc_vertex_pos(g,v2);//v2 = 1 (0,1) Ça veut dire qu'il y a des bords , Vous devez définir cette valeur de position à 1
		//En même temps(1,0) Cette position doit également être réglée à 1, Après tout, c'est un graphique non recté. 
		g.edge[m][n] = 1;
		g.edge[n][m] = 1;
	}
}

// Imprimer une image 
void print_graph(graph& g)
{
	// L'impression d'un graphique est l'impression d'un tableau bidimensionnel 
	printf("\t");
	// En - tête de vertex horizontal cyclique 
	for(int i = 0;i < g.vertex_num;i++) {
		printf("%s\t",g.vertex[i]);
	}
	// Contenu du tableau 2D cyclique 
	for(int i = 0;i < g.vertex_num;i++) {
		// Imprimer les en - têtes de vertex horizontaux 
		printf("\n");// Une ligne à la fois 
		printf("%s\t",g.vertex[i]);
		// Puis une ligne de contenu est sortie 
		for(int j = 0;j < g.vertex_num;j++) {
			printf("%d\t",g.edge[i][j]);
		}
	}
	printf("\t");
}


//Diagramme de construction
void test01()
{
	graph g;
	create_graph(g);
	print_graph(g);
}

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

Résultats des opérations：

  Voici un digraphe. ,Digraphe, C'est la direction, non? , Par exemple, pour les graphiques non rectés (v1,v2)Et(v2,v1) Ça veut dire quelque chose. ,Qu'est - ce que ça veut dire, C'est ce côté. , Donc il y a un digraphe , Si ce côté est v1->v2,C'est - à - direv1 Ça veut dire "queue de renard" ,v2 Ça veut dire tête de renard ,v1Sortie,v2Pénétration,Alors, à ce moment - là,(v1,v2)Avec(v2,v1) Pas vraiment. ,(v1,v2)Pour exprimerv1->v2,Alors(v2,v1) Comment cette coordonnée est - elle représentée dans la matrice de contiguïté? ？ Cette position nous permet de définir une valeur impossible , Et d'autres qui remplissent les conditions directionnelles , On va juste définir un poids. , Pourquoi dites - vous que l'orientation n'est pas pertinente? 0,Parce que0 Peut également représenter des poids , Le poids normal est la distance entre ces deux points. , Il y a quelque chose à voir avec ça. . C'est l'idée du graphe dirigé. , Voici une image

Pas grand - chose à dire,Directement au Code;

directed_graph.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
//Nombre maximum de sommets
#define MAX_VERTEX 30

// Définir la structure du diagramme 
typedef struct _graph
{
	//Tableau vertex, Stocker le nom du vertex 
	char **vertex;
	// Tableau des bords 
	int edge[MAX_VERTEX][MAX_VERTEX];
	//Nombre de sommets
	int vertex_num;
	//Le nombre de côtés
	int edge_num;
}graph;

// Calculer la position des sommets entrés par l'utilisateur dans le tableau 
// C'est comme entrer un v1,v2, Donc pour les graphiques non rectés, ,(v1,v2)Avec(v2,v1) C'est le même côté. 
int calc_vertex_pos(graph &g,char* v)
{
	//Traverser le tableau Vertex
	for(int i = 0;i < g.vertex_num;i++) {
		// C'est une comparaison de chaînes. 
		if(strcmp(v,g.vertex[i]) == 0) {
			return i;// Retour direct à cet endroit 
		}
	}
	return -1;
}

//Créer un graphique
void create_graph(graph &g)
{
	printf(" Veuillez saisir le nombre de sommets et de bords du diagramme :Vertex Edge\n");
	scanf("%d %d",&g.vertex_num,&g.edge_num);
	printf("Veuillez entrer%dValeurs Vertex\n",g.vertex_num);

	// Démarrer la boucle pour assigner une valeur Vertex au tableau vertex 
	// Besoin d'espace sur le tas pour stocker les chaînes avant l'affectation 
	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);
		// Ce tableau pointe à nouveau vers un espace assigné 
		g.vertex[i] = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.vertex[i],str);
	}
	// Initialiser le tableau bidimensionnel des bords 
	// En nombre de sommets n,Pour former unn*nUn tableau bidimensionnel de
	for(int i = 0;i < g.vertex_num;i++) {
		for(int j = 0;j < g.vertex_num;j++) {
			//Pour les digraphes, Ces points doivent être initialisés à une valeur improbable 
			g.edge[i][j] = INT_MAX;
		}
	}

	// Les deux tableaux ci - dessus sont initialisés 
	// Définir la relation entre les bords , Est - ce qu'il y a des bords 
	printf("Veuillez entrer%d Bords et sommets correspondants 1,Vertex2\n",g.edge_num);
	// Définir la relation entre deux sommets bordés 
	char v1[10];
	char v2[10];
	// Définir un poids 
	int weight;
	// Combien de côtés , Ça correspond au nombre de sommets. 
	for(int i = 0;i < g.edge_num;i++) {
		scanf("%s %s %d",v1,v2,&weight);
		// Ensuite, nous calculons la position des sommets dans le tableau 
		//- Oui.0Oh là là!,1Oh là là!,Toujours2 Attends, c'est une relation. 
		int m = calc_vertex_pos(g,v1);//Par exemple,v1=0
		int n = calc_vertex_pos(g,v2);//v2 = 1 (0,1) Ça veut dire qu'il y a des bords , Vous devez définir cette valeur de position à 1
		// Ces deux points sont orientés , C'est impossible. , Il n'y a qu'une seule direction. 
		g.edge[m][n] = weight;// Convertir directement en poids 
	}
}

// Imprimer une image 
void print_graph(graph& g)
{
	// L'impression d'un graphique est l'impression d'un tableau bidimensionnel 
	printf("\t");
	// En - tête de vertex horizontal cyclique 
	for(int i = 0;i < g.vertex_num;i++) {
		printf("%s\t",g.vertex[i]);
	}
	// Contenu du tableau 2D cyclique 
	for(int i = 0;i < g.vertex_num;i++) {
		// Imprimer les en - têtes de vertex horizontaux 
		printf("\n");// Une ligne à la fois 
		printf("%s\t",g.vertex[i]);
		// Puis une ligne de contenu est sortie 
		for(int j = 0;j < g.vertex_num;j++) {
			printf("%d\t",g.edge[i][j]);
		}
	}
	printf("\t");
}


//Diagramme de construction
void test01()
{
	graph g;
	create_graph(g);
	print_graph(g);
}

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

  La représentation de la matrice de contiguïté est décrite ci - dessus. ,Et cette méthode, C'est un tableau bidimensionnel. , Donc si vous avez plus de points , Avec peu de côtés ,Espace、 C'est une perte de temps. ,Alors..., Pour éviter de gaspiller trop d'espace, nous pouvons le faire en utilisant des listes de contiguïtés. , C'est comme ouvrir de l'espace en mémoire. , Disons que quand il y a une relation entre deux sommets, , Ouvrez une mémoire pour indiquer cette relation. , Donc pas de gaspillage d'espace , C'est plus difficile à réaliser.

Voici comment implémenter un graphique non recté avec une liste de contiguïtés ：

Commençons par analyser la structure des données ：

        

Pour analyser l'idée d'insertion de chaque vertex ：

         

Continue.

 

 Continue.

 Un autre point.;

Code complet du graphique non rectiligne supérieur ：

undirected_graph1.cpp

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

// Nombre maximum de sommets pouvant être stockés 
#define MAX_VERTEX 100

struct edge_node {
	int position;//Ça veut direvertex Quel index de noeud dans le tableau 
	edge_node *next;// Pointeur pour stocker la prochaine broche adjacente 
	// Le poids peut être écrit ici. 
};

struct vertex {
	char *name;// Stocker le nom du vertex , Le pointeur de niveau 1 pointe vers l'espace alloué au - dessus d'un tas 
	// Et stocke chaque premier contact adjacent , En fait, c'est un noeud de tête ici. 
	edge_node *first_node;
};

// Enfin, la structure de l'ensemble du diagramme est nécessaire 
// Pour stocker des informations sur les dessins correspondants 
struct graph {
	// Contient toutes les informations sur les sommets 
	vertex head[MAX_VERTEX];
	// Nombre de sommets et de bords 
	int vertex_num;
	int edge_num;
};



// Ici, vous pouvez déterminer l'emplacement des sommets 
int find_pos(graph &g,char *v)//Ici.v Peut imprimer s'il y a un point ,Je veux direscanf Une affectation directe n'est pas acceptable 
{
	for (int i = 0; i < g.vertex_num; i++) {
		// L'espace dans lequel les noms de vertex sont stockés en boucle 
		if (strcmp(g.head[i].name, v) == 0) {
			return i;
		}
	}
	return -1;
}

// Commencez par créer une image 
void create_graph(graph &g)
{
	printf(" Veuillez saisir le nombre de sommets et de bords :\n");
	scanf("%d %d", &g.vertex_num, &g.edge_num);
	// Valeur du Vertex d'entrée circulaire 
	printf("Veuillez entrer%dValeurs Vertex:\n", g.vertex_num);
	// Boucle pour assigner des valeurs aux sommets 
	for (int i = 0; i < g.vertex_num; i++){
		char str[30] = { 0 };
		scanf("%s", str);
		//Simplicitéscanf("%s",&g.head[i].name)Certainement pas,C'estname Un pointeur secondaire. 
		g.head[i].name = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.head[i].name, str);// Où conserver les sommets 
		// En plus de la chaîne d'assignation , Vous devez également initialiser l'adresse d'une broche adjacente 
		g.head[i].first_node = NULL;// Ressemblant à chaque point supérieur de la tête nextC'est tout.NULL
	}

	// Commencez par entrer les bords , Deux sommets. 
	printf("Veuillez entrer%dBordure,Vertex1,Vertex2", g.edge_num);
	char v1[10];
	char v2[10];
	// Boucle pour assigner des valeurs aux bords 
	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);
		// Numéro de chaque Vertex trouvé en mémoire 
		//Et puis, par exemple,m C'est la tête qui représente un sommet. ,Ici, oui.
		// Traiter comme un en - tête de liste 
		// Et puis nous avons mis en place la prise de tête , Pour indiquer un lien 
		// Enfin, nous réalisons une interaction entre les relations , C'est pour les graphiques non rectés v1Avecv2Etv2Avecv1C'est pareil.
		
		// Créer un nouveau point de contiguïté 
		edge_node *p_new = (edge_node*)malloc(sizeof(edge_node));
		// Puis commencez à insérer dans la tête , Cette tête est mPoint
		p_new->position = n;
		//Ici.p_new Il faut d'abord indiquer 
		p_new->next = g.head[m].first_node;
		g.head[m].first_node = p_new;

		//Et ensuite réaliserv0Avecv1 Une alternance de , C'est ce que ça veut dire. 
		edge_node *p_new1 = (edge_node*)malloc(sizeof(edge_node));
		// En fait, c'est la réalisation d'un mAvecnAlterner
		p_new1->position = m;
		p_new1->next = g.head[n].first_node;
		g.head[n].first_node = p_new1;
	}
}


// Imprimer cette image 
void print_graph(graph &g)
{
	for (int i = 0; i < g.vertex_num; i++) {
		printf("%s: ", g.head[i].name);
		// Prenez le noeud de tête et traversez une table à chaîne unique. 
		edge_node *p_node =  g.head[i].first_node;
		while (p_node != NULL) {
			//Ce qu'on a, c'estn,Je l'ai cherchém
			int index = p_node->position;
			printf("%s ", g.head[index].name);
			p_node = p_node->next;
		}
		//Nouvelle ligne
		printf("\n");
	}
}

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

 Résultats des opérations：

    Comment réaliser un digraphe , Par exemple, voici un graphique dirigé

     

        Pour les digraphes, Tout ce qui est nécessaire, c'est de supprimer le code ci - dessus où l'inversion doit être traitée. ,Parce quev0 v1Avecv1 v0 Ça ne veut plus dire ça. ,Directement au Code

        directed_graph1.cpp

        

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

// Nombre maximum de sommets pouvant être stockés 
#define MAX_VERTEX 100

struct edge_node {
	int position;//Ça veut direvertex Quel index de noeud dans le tableau 
	edge_node *next;// Pointeur pour stocker la prochaine broche adjacente 
	// Le poids peut être écrit ici. 
};

struct vertex {
	char *name;// Stocker le nom du vertex , Le pointeur de niveau 1 pointe vers l'espace alloué au - dessus d'un tas 
	// Et stocke chaque premier contact adjacent , En fait, c'est un noeud de tête ici. 
	edge_node *first_node;
};

// Enfin, la structure de l'ensemble du diagramme est nécessaire 
// Pour stocker des informations sur les dessins correspondants 
struct graph {
	// Contient toutes les informations sur les sommets 
	vertex head[MAX_VERTEX];
	// Nombre de sommets et de bords 
	int vertex_num;
	int edge_num;
};



// Ici, vous pouvez déterminer l'emplacement des sommets 
int find_pos(graph &g,char *v)//Ici.v Peut imprimer s'il y a un point ,Je veux direscanf Une affectation directe n'est pas acceptable 
{
	for (int i = 0; i < g.vertex_num; i++) {
		// L'espace dans lequel les noms de vertex sont stockés en boucle 
		if (strcmp(g.head[i].name, v) == 0) {
			return i;
		}
	}
	return -1;
}

// Commencez par créer une image 
void create_graph(graph &g)
{
	printf(" Veuillez saisir le nombre de sommets et de bords :\n");
	scanf("%d %d", &g.vertex_num, &g.edge_num);
	// Valeur du Vertex d'entrée circulaire 
	printf("Veuillez entrer%dValeurs Vertex:\n", g.vertex_num);
	// Boucle pour assigner des valeurs aux sommets 
	for (int i = 0; i < g.vertex_num; i++){
		char str[30] = { 0 };
		scanf("%s", str);
		//Simplicitéscanf("%s",&g.head[i].name)Certainement pas,C'estname Un pointeur secondaire. 
		g.head[i].name = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.head[i].name, str);// Où conserver les sommets 
		// En plus de la chaîne d'assignation , Vous devez également initialiser l'adresse d'une broche adjacente 
		g.head[i].first_node = NULL;// Ressemblant à chaque point supérieur de la tête nextC'est tout.NULL
	}

	// Commencez par entrer les bords , Deux sommets. 
	printf("Veuillez entrer%dBordure,Vertex1,Vertex2", g.edge_num);
	char v1[10];
	char v2[10];
	// Boucle pour assigner des valeurs aux bords 
	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);
		// Numéro de chaque Vertex trouvé en mémoire 
		//Et puis, par exemple,m C'est la tête qui représente un sommet. ,Ici, oui.
		// Traiter comme un en - tête de liste 
		// Et puis nous avons mis en place la prise de tête , Pour indiquer un lien 
		// Enfin, nous réalisons une interaction entre les relations , C'est pour les graphiques non rectés v1Avecv2Etv2Avecv1C'est pareil.
		
		// Créer un nouveau point de contiguïté 
		edge_node *p_new = (edge_node*)malloc(sizeof(edge_node));
		// Puis commencez à insérer dans la tête , Cette tête est mPoint
		p_new->position = n;
		//Ici.p_new Il faut d'abord indiquer 
		p_new->next = g.head[m].first_node;
		g.head[m].first_node = p_new;
/*
 *  Un digraphe annote cette position. 
		//Et ensuite réaliserv0Avecv1 Une alternance de , C'est ce que ça veut dire. 
		edge_node *p_new1 = (edge_node*)malloc(sizeof(edge_node));
		// En fait, c'est la réalisation d'un mAvecnAlterner
		p_new1->position = m;
		p_new1->next = g.head[n].first_node;
		g.head[n].first_node = p_new1;
*/
	}
}


// Imprimer cette image 
void print_graph(graph &g)
{
	for (int i = 0; i < g.vertex_num; i++) {
		printf("%s: ", g.head[i].name);
		// Prenez le noeud de tête et traversez une table à chaîne unique. 
		edge_node *p_node =  g.head[i].first_node;
		while (p_node != NULL) {
			//Ce qu'on a, c'estn,Je l'ai cherchém
			int index = p_node->position;
			printf("%s ", g.head[index].name);
			p_node = p_node->next;
		}
		//Nouvelle ligne
		printf("\n");
	}
}

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

Résultats des opérations：

    Les digraphes et les digraphes sont finis. .