A graph consists of a nonempty finite set V of vertices and a set E of edges (relationships between vertices). Graphs are divided into directed graphs and undirected graphs.

Use two arrays to store a graph. The first array is a one-dimensional array that holds the data in the graph. The second array is a two-dimensional array that stores the relationships between vertices, called the adjacency matrix. A[I][j]={1, when there is an edge 0 between vertex I and vertex j, when there is no edge between vertex I and vertex j}

Directed graph	The adjacency matrix of a directed graph

A complex graph relationship can be represented by a simple adjacency matrix, but this method is not suitable for sparse graphs (graphs with fewer edges).

// Adjacency list definition
#define MAX_VERTEX_NUM 20		// Set the maximum number of vertices in the graph to 20
typedef struct ArcNode
{
	// Type of node in a singly linked list
	int adjvex;					// This edge points to the position of the vertices in the order table (array subscript)
	struct ArcNode *next;		// Pointer to the next edge
	infoType *weight;			// Edge weights
}ArcNode;

typedef struct VNode
{
	// Vertex type
	VertexType data;			// The data in the vertex is of type VertexType
	ArcNode *firstarc;			// Point to a single linked list, i.e. point to an edge
}VNode;

VNode G[MAX_VERTEX_NUM];		// Array G of type VNode, which is the container for storing vertices in the graph.
Copy the code

Graph traversal: starting from one vertex of a graph, traversing the rest of the graph so that each vertex is visited only once. Graph traversal can be used to solve graph connectivity problems, topological sorting, shortest path, critical path

The basic idea of depth-first search: start from a vertex V in the graph, visit the vertex V, and then start from the unvisited adjacent points of V again, continue to depth-first traverse the graph until all vertices in the graph that are connected to the path of vertex V are accessed. Since a graph structure is not necessarily connected, a depth-first search may not traverse all vertices in the graph. If there are still unaccessed vertices in the graph, another unaccessed vertex in the graph is selected as the starting point to continue the depth-first search. Repeat until all vertices in the graph are accessed. Depth-first search is a recursive operation that repeats “visit vertex V and continue depth-first search from the unvisited adjacent points of V”.

// Code description
/* Depth-first search for a connected graph */
void DFS(VNode G[],int v)
{
	int w;
	visit(v);				// Access the current vertex
	visited[v] =1;			// Set the access flag corresponding to vertex v to 1
	w=FirstAdj(G,v);		// Find the first adjacency of vertex v, return -1 if no adjacency exists
	while(w! =- 1)
	{
		if(visited[w]==0)	// If the vertex is not accessed
		{
			DFS(G,w);		// Perform depth-first access recursively
			w=NextAdj(G,v); // Find the next adjacency of vertex v, if not -1}}}// The main depth-first search algorithm for G=(V,E)
void Travel_DFS(VNode G[],int visited[],int n)
{
	int i;
	for(i=0; i<n; i++) visited[i]=0;		// Initialize the tag array to 0
	for(i=0; i<n; i++)if(visited[i]==0)  	// If a vertex is not accessed, the depth-first search continues from that vertex
			DFS(G,i);
}
Copy the code

The Travel_DFS function contains three parameters G[], which represents the container for storing graph structure. Here, it can be understood as the array of orientation markers set by the adjacency table VISITED [], which is used to mark the visited vertices in the graph. N represents the number of vertices in the graph. Initialize Visited to 0, because none of the points in the graph has been visited at first. The recursive function DFS is then called starting from the first unvisited vertex, from which depth-first traversal of the entire graph is not possible with a single recursive function DFS(), because DFS can only traverse all vertices of the graph connected to V starting from vertex V. If the graph is not connected, it cannot be traversed completely by DFS alone

An example can be used to describe the detailed traversal process:

Assuming that V0 is taken as the starting point, the initial value of the access token array is visited[5]={0,0,0,0,0}; {(1) visit vertex V0, visited[5]=1,0,0,0,0 (2) Use the function FirstAdj to get the first adjacency of V0, such as V1 (3) if -1 is not returned, that is, there is an adjacency (3.1) visit vertex V1, Visited [5]=1,1,0,0,0 (3.2) Obtain the first adjacency of V1 by using the function FirstAdj, V2(because V0 has been visited) (3.3) If -1 is not returned, that is, an adjacency (3.3.1) visits vertex V2, Visited [5]=1,1,1,0,0 (3.3.2) Use the function FirstAdj to get the first adjacency of V2 and return -1, because they have been visited. (3.4) Use the function NextAdj() to get the next adjacency of V1 and return -1. \begin{cases} (1) &\ text{access vertex V0, ,0,0,0,0 visited [5] = {1}} \ \ (2) & \ text {use function FirstAdj get where V0 first adjacent points, such as V1} \ \ (3) & \ text {if you don’t return 1, with adjacency point} \ \ (3.1) & \ text {visit vertices V1, ,1,0,0,0 visited [5] = {1}} \ \ (3.2) & \ text {use function FirstAdj get V1 first adjacent points, V2 (because) has been visited where V0} \ \ (3.3) & \ text {if you don’t return 1, With the adjacent point} \ \ (3.3.1) & \ text {access vertex V2, visited [5] =,1,1,0,0} {1} \ \ (3.3.2 rainfall distribution on 10-12) & \ text {use function FirstAdj get V2 adjacent points, the first return 1, }\\ (3.4) &\ text{NextAdj() returns -1 because both are accessed}\\ (4) &\ text{NextAdj() returns -1 because both are accessed}\\ (4) &\ text{NextAdj() returns -1, Because lead son are visiting} {cases} \ \ \ end ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ (1) (2) (3) (3.1) (3.2) (3.3) (3.3.1) (3.3.2 rainfall distribution on 10-12) access points where V0 (3.4) and (4), Visited [5]=1,0,0,0,0 obtain the first adjacency of V0 by using the function FirstAdj. For example, if V1 does not return -1, that is, an adjacency visits the vertex V1. Visited [5]=1,1,0,0 obtain the first adjacency of V1 by using the function FirstAdj. If V2(because V0 has been visited) does not return -1, that is, some adjacency visits vertex V2. Visited [5]=1,1,1,0,0. We use FirstAdj to get the first adjacency of V2, and return -1 because all of them have been visited. Because they’re all accessed we use NextAdj() to get V0 and the next adjacency returns -1, because they’re all accessed

Here we instantiate the two functions involved above, FirstAdj() and NextAdj(); FirstAdj(): Returns the index of the first adjacency of a vertex in G, or -1 if the vertex has no adjacency

// Returns the index of the first adjacency in the array
int FirstAdj(VNode G[],int v)
{
	if(G[v].firstarc! =NULL) return (G[v].firstarc)->adjvex;	If the node has the first edge, return the subscript, otherwise return -1
	return - 1;
}
Copy the code

NextAdj() : Returns the subscript of the next adjacency of a vertex in array G, -1 if the vertex has no adjacency, or all adjacencies of the vertex have been accessed

// Returns the index of the next adjacency in the array
int NextAdj(VNode G[],int v)
{
	ArcNode *p;
	p=G[v].firstarc;
	while(p! =NULL)
	{
		if(visited[p->adjvex]) p=p->next;		// If already accessed, -1 is returned
		else return p->adjvex;
	}
	return - 1;
}
Copy the code

An undirected graph is created in the form of adjacency list, and a depth-first search method is applied to traverse every vertex in the graph

#include <stdio.h>
#include <stdlib.h>
#include "malloc.h"
#include "conio.h"

// Adjacency list definition
#define MAX_VERTEX_NUM 20		// Set the maximum number of vertices in the graph to 20
typedef int VertexType ;
typedef struct ArcNode
{
	// Type of node in a singly linked list
	int adjvex;					// This edge points to the position of the vertices in the order table (array subscript)
	struct ArcNode* next;		// Pointer to the next edge
	//infoType* weight; // Edge weights
}ArcNode;

typedef struct VNode
{
	// Vertex type
	VertexType data;			// The data in the vertex is of type VertexType
	ArcNode* firstarc;			// Point to a single linked list, i.e. point to an edge
}VNode;

VNode G[MAX_VERTEX_NUM];		// Array G of type VNode, which is the container for storing vertices in the graph.
int visited[5] = { 0.0.0.0.0 };

// Create a graph
void GreatGraph(int n, VNode G[])
{
	int i, e;
	ArcNode* p, * q;
	q = NULL;
	printf("Input vertex information \n");
	for (i = 0; i < n; i++) {scanf("%d", &G[i].data);			// Get the data in each vertex
		G[i].firstarc = NULL;		// Initialize the first edge of each vertex to be empty
	}
	for (i = 0; i < n; i++) {printf("Create edge \n of vertex %d",i);
		scanf("%d", &e);			// Enter the vertex coordinates to which the edge points
		while(e ! =- 1)
		{
			p = (ArcNode*)malloc(sizeof(ArcNode));		// Create an edge
			p->next = NULL;		// Next points to empty
			p->adjvex = e;		// Assign the information that the edge points to a vertex to Adjvex
			if (G[i].firstarc == NULL)
				G[i].firstarc = p;	// the first edge of the I node
			else
			{
				q->next = p;
			}
			q = p;
			scanf("%d", &e); }}}// Returns the index of the first adjacency in the array
int FirstAdj(VNode G[], int v)
{
	if(G[v].firstarc ! =NULL) return (G[v].firstarc)->adjvex;	If the node has the first edge, return the subscript, otherwise return -1
	return - 1;
}

// Returns the index of the next adjacency in the array
int NextAdj(VNode G[], int v)
{
	ArcNode* p;
	p = G[v].firstarc;
	while(p ! =NULL)
	{
		if (visited[p->adjvex]) p = p->next;		// If already accessed, -1 is returned
		else return p->adjvex;
	}
	return - 1;
}

void DFS(VNode G[], int v)
{
	int w;
	printf("%d ", G[v].data);		// Access the current vertex, print the vertex amount data information
	visited[v] = 1;			// Set the access flag corresponding to vertex v to 1
	w = FirstAdj(G, v);		// Find the first adjacency of vertex v, return -1 if no adjacency exists
	while(w ! =- 1)
	{
		if (visited[w] == 0)	// If the vertex is not accessed
		{
			DFS(G, w);		// Perform depth-first access recursively
		}
		w = NextAdj(G, v); // Find the next adjacency of vertex v, if not -1}}/* 1; /* 1; Get the data in each vertex by Getdata and assign it to G[I].data. The firstarc field for each vertex is initialized to NULL 2, and edges between vertices are created. The edges should be created in strict accordance with the logical structure of the diagram originally designed. The process of creating edges is similar to that of creating linked lists. When -1 is entered, the edge attached to the vertex is created */
int main(a)
{
	VNode G[5];
	GreatGraph(5, G);
	printf("DFS search \n");
	DFS(G, 0);
	_getche();
	return 0;
}
Copy the code

Effect:

Put up a few links and learn

Blog.csdn.net/ledou2/arti… Blog.csdn.net/ledou2/arti…