picture

In a linear table, the data elements are strung together, there is only a linear relationship, and each data element has only one direct predecessor and one direct successor. In the tree structure, there is an obvious hierarchical relationship between data elements, and the data elements on each layer may be related to multiple elements in the next layer, but can only be related to one element in the previous layer. A graph is a more complex data structure than linear tables and trees. In a graph structure, the relationship between nodes can be arbitrary, and any two data elements in the graph may be related.

The adjacency matrix holds the data in two arrays. A one-dimensional array stores vertex information in the graph, and a two-dimensional array stores information about edges or arcs in the graph.

Header files and structures

#include <stdio.h>
#include <malloc.h>

int *visitedPtr;

typedef struct Graph {
	int **connections;
	int numNodes;
} *GraphPtr;

Initialize graph and record function

GraphPtr initGraph(int paraSize, int **paraData) {
	int i, j;
	GraphPtr resultPtr = (GraphPtr)malloc(sizeof(struct Graph));
	resultPtr->numNodes = paraSize;
	resultPtr->connections = (int **)malloc(5 * sizeof(int *));
	for (i = 0; i < paraSize; i++) {
		resultPtr->connections[i] = (int *)malloc(5 * sizeof(int));
		for (j = 0; j < 5; j++) {
			resultPtr->connections[i][j] = paraData[i][j];
		}
	}

	return resultPtr;
}

void initTranverse(GraphPtr paraGraphPtr) {
	int i;

	visitedPtr = (int *)malloc(paraGraphPtr->numNodes * sizeof(int));

	for (i = 0; i < paraGraphPtr->numNodes; i++) {
		visitedPtr[i] = 0;
	}
}

This record function is used to record whether a node has been traversed

Depth-first traversal and breadth-first traversal

void depthFirstTranverse(GraphPtr paraGraphPtr, int paraNode) {
	int i;

	visitedPtr[paraNode] = 1;
	printf("%d\t", paraNode);

	for ( i = 0; i < paraGraphPtr->numNodes; i++) {
		if (paraGraphPtr->connections[paraNode][i] && visitedPtr[i] == 0) {
			depthFirstTranverse(paraGraphPtr, i);
		}
	}
}

void widthFirstTranverse(GraphPtr paraGraphPtr, int paraNode, int cnt) {
	int tempNode[paraGraphPtr->numNodes];
	int i, front = 0;
	visitedPtr[paraNode] = 1;
	tempNode[cnt] = paraNode;
	while ((cnt + 1) != paraGraphPtr->numNodes) {
		paraNode = tempNode[front];
		for (i = 0; i < paraGraphPtr->numNodes; i++) {
			if (visitedPtr[i])
				continue;
			if (paraGraphPtr->connections[paraNode][i] == 0)
				continue;
			visitedPtr[i] = 1;
			cnt++;
			tempNode[cnt] = i;
		}
		front++;
	}

	for (i = 0; i < paraGraphPtr->numNodes; i++) {
		printf("%d\t", tempNode[i]);
	}
}

For breadth-first traversal, I use an array to replace the function of the queue. Compared to this, the array here is relatively concise.

Test function and program entry

void testGraphTranverse() {
	int i, j;

	int myGraph[5][5] = {
		{0, 1, 0, 1, 0},
		{1, 0, 1, 0, 1},
		{0, 1, 0, 1, 1},
		{1, 0, 1, 0, 0},
		{0, 1, 1, 0, 0}
	};
	int **tempPtr;
	printf("Preparing data\r\n");

	tempPtr = (int **)malloc(5 * sizeof(int *));
	for (i = 0; i < 5; i++) {
		tempPtr[i] = (int *)malloc(5 * sizeof(int));
	}

	for (i = 0; i < 5; i++) {
		for (j = 0; j < 5; j++) {
			tempPtr[i][j] = myGraph[i][j];
		}
	}

	printf("Data ready\r\n");

	GraphPtr tempGraphPtr = initGraph(5, tempPtr);
	printf("num nodes = %d \r\n", tempGraphPtr->numNodes);
	printf("Graph initialized\r\n");

	printf("Depth first visit:\r\n");
	initTranverse(tempGraphPtr);
	depthFirstTranverse(tempGraphPtr, 4);

	printf("\r\nWidth first visit:\r\n");
	initTranverse(tempGraphPtr);
	widthFirstTranverse(tempGraphPtr, 4, 0);
}
int main() {
	testGraphTranverse();
	return 0;
}

output result

Preparing data
Data ready
num nodes = 5
Graph initialized
Depth first visit:
4       1       0       3       2
Width first visit:
4       1       2       0       3

adjacency list

We found that the adjacency matrix is ​​a huge waste of storage space when the number of edges in the graph is small relative to the vertices. We can consider using chained storage for edges or arcs to avoid the problem of wasting space. Recall the child representation of the tree structure, store the node into an array, and store the children of the node in a chain, no matter how many children there are, there will be no space waste problem.

Applying this idea, we call this combination of array and linked list storage method Adjacency List.

This is how the adjacency list is handled.

1) The vertices in the graph are stored in a one-dimensional array, of course, it can also be stored in a singly linked list, but it is easier to read the vertex information with an array, which is more convenient. In addition, for the vertex array, each data element also needs to store a pointer to the first adjacent point in order to find the edge information of the vertex.

2) All the adjacent points of each vertex vi in ​​the graph form a linear table. Since the number of adjacent points is not fixed, it is stored in a singly linked list. The undirected graph is called the edge table of the vertex vi, and the directed graph is called vi. is the outgoing edge table of the arc tail.

The following figure is an adjacency list structure of an undirected graph:
Header files and structures

#include <stdio.h>
#include <malloc.h>
#define QUEUE_SIZE 10
#define true 1
#define false 0
int* visitedPtr;

/**
 * graph data structure
 */
typedef struct Graph{
	int** connections;
	int numNodes;
} *GraphPtr;

Initialization map

/**
 * initialize a graph
 */
GraphPtr initGraph(int paraSize, int** paraData) {
	int i, j;
	GraphPtr resultPtr = (GraphPtr)malloc(sizeof(struct Graph));
	resultPtr -> numNodes = paraSize;
	resultPtr -> connections = (int**)malloc(paraSize * sizeof(int*));
	for (i = 0; i < paraSize; i ++) {
		resultPtr -> connections[i] = (int*)malloc(paraSize * sizeof(int));
		for (j = 0; j < paraSize; j ++) {
			resultPtr -> connections[i][j] = paraData[i][j];
		}
	}
	
	return resultPtr;
}

Preparation of the queue

/**
 * queue data structure
 */
typedef struct GraphNodeQueue{
	int* nodes;
	int front;
	int rear;
}GraphNodeQueue, *QueuePtr;

/**
 * Initialize the queue
 */
QueuePtr initQueue(){
	QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct GraphNodeQueue));
	resultQueuePtr->nodes = (int*)malloc(QUEUE_SIZE * sizeof(int));
	resultQueuePtr->front = 0;
	resultQueuePtr->rear = 1;
	return resultQueuePtr;
}

/**
 * Check if the queue is full
 */
int isQueueEmpty(QueuePtr paraQueuePtr){
	if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) {
		return true;
	}
	return false;
}

/**
 * join the team
 */
void enqueue(QueuePtr paraQueuePtr, int paraNode){
	if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) {
		printf("Error, trying to enqueue %d. queue full.\r\n", paraNode);
		return;
	}
	paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode;
	paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;
}

/**
 * out of the team
 */
int dequeue(QueuePtr paraQueuePtr){
	if (isQueueEmpty(paraQueuePtr)) {
		printf("Error, empty queue\r\n");
		return NULL;
	}

	paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;

	return paraQueuePtr->nodes[paraQueuePtr->front];
}

Preparation of the adjacency list

/**
 * adjacency list node
 */
typedef struct AdjacencyNode {
	int column;
	struct AdjacencyNode* next;
}AdjacencyNode, *AdjacentNodePtr;

/**
 * adjacency list queue
 */
typedef struct AdjacencyList {
	int numNodes;
	AdjacencyNode* headers;
}AdjacencyList, *AdjacencyListPtr;

/**
 * Create an adjacency list queue
 */
AdjacencyListPtr graphToAdjacentList(GraphPtr paraPtr) {
	//application space
	int i, j, tempNum;
	AdjacentNodePtr p, q;
	tempNum = paraPtr->numNodes;
	AdjacencyListPtr resultPtr = (AdjacencyListPtr)malloc(sizeof(struct AdjacencyList));
	resultPtr->numNodes = tempNum;
	resultPtr->headers = (AdjacencyNode*)malloc(tempNum * sizeof(struct AdjacencyNode));
	
	//push data
	for (i = 0; i < tempNum; i ++) {
		//Initialize the head node
		p = &(resultPtr->headers[i]);
		p->column = -1;
		p->next = NULL;

		for (j = 0; j < tempNum; j ++) {
			if (paraPtr->connections[i][j] > 0) {
				//Create a new node
				q = (AdjacentNodePtr)malloc(sizeof(struct AdjacencyNode));
				q->column = j;
				q->next = NULL;

				//Link
				p->next = q;
				p = q;
			}
		}
	}

	return resultPtr;
}

/**
 * print adjacency list
 */
void printAdjacentList(AdjacencyListPtr paraPtr) {
	int i;
	AdjacentNodePtr p;
	int tempNum = paraPtr->numNodes;

	printf("This is the graph:\r\n");
	for (i = 0; i < tempNum; i ++) {
		p = paraPtr->headers[i].next;
		while (p != NULL) {
			printf("The node %d connects %d, ", i, p->column);
			p = p->next;
		}
		printf("\r\n");
	}
}

Breadth-first search using queues

/**
 * Breadth-first search
 */
void widthFirstTranverse(AdjacencyListPtr paraListPtr, int paraStart){
	printf("width first \r\n");
	//Use queues to store data
	int i, j, tempNode;
	AdjacentNodePtr p;
	i = 0;

	//Initialization data
	visitedPtr = (int*) malloc(paraListPtr->numNodes * sizeof(int));
	
	for (i = 0; i < paraListPtr->numNodes; i ++) {
		visitedPtr[i] = 0;
	}

	QueuePtr tempQueuePtr = initQueue();
	printf("%d\t", paraStart);
	visitedPtr[paraStart] = 1;
	enqueue(tempQueuePtr, paraStart);
	while (!isQueueEmpty(tempQueuePtr)) {
		tempNode = dequeue(tempQueuePtr);

		for (p = &(paraListPtr->headers[tempNode]); p != NULL; p = p->next) {
			j = p->column;
			if (visitedPtr[j]) 
				continue;

			printf("%d\t", j);
			visitedPtr[j] = 1;
			enqueue(tempQueuePtr, j);
		}
	}
	printf("\r\n");
}

Test function and program entry

/**
 * Traversal of the test graph
 */
void testGraphTranverse() {
	int i, j;
	int myGraph[5][5] = { 
		{0, 1, 0, 1, 0},
		{1, 0, 1, 0, 1}, 
		{0, 1, 0, 1, 1}, 
		{1, 0, 1, 0, 0}, 
		{0, 1, 1, 0, 0}};
	int** tempPtr;
	printf("Preparing data\r\n");
		
	tempPtr = (int**)malloc(5 * sizeof(int*));
	for (i = 0; i < 5; i ++) {
		tempPtr[i] = (int*)malloc(5 * sizeof(int));
	}
	 
	for (i = 0; i < 5; i ++) {
		for (j = 0; j < 5; j ++) {
			tempPtr[i][j] = myGraph[i][j];
		}
	}
 
	printf("Data ready\r\n");
	
	GraphPtr tempGraphPtr = initGraph(5, tempPtr);
	AdjacencyListPtr tempListPtr = graphToAdjacentList(tempGraphPtr);

	printAdjacentList(tempListPtr);

	widthFirstTranverse(tempListPtr, 4);
}

/**
 * Program entry
 */
int main(){
	testGraphTranverse();
	return 0;
}

output result

Preparing data
Data ready
This is the graph:
The node 0 connects 1, The node 0 connects 3,
The node 1 connects 0, The node 1 connects 2, The node 1 connects 4,
The node 2 connects 1, The node 2 connects 3, The node 2 connects 4,
The node 3 connects 0, The node 3 connects 2,
The node 4 connects 1, The node 4 connects 2,
width first
4       1       2       0       3

full code

#include <stdio.h>
#include <malloc.h>

int *visitedPtr;

typedef struct Graph {
	int **connections;
	int numNodes;
} *GraphPtr;

GraphPtr initGraph(int paraSize, int **paraData) {
	int i, j;
	GraphPtr resultPtr = (GraphPtr)malloc(sizeof(struct Graph));
	resultPtr->numNodes = paraSize;
	resultPtr->connections = (int **)malloc(5 * sizeof(int *));
	for (i = 0; i < paraSize; i++) {
		resultPtr->connections[i] = (int *)malloc(5 * sizeof(int));
		for (j = 0; j < 5; j++) {
			resultPtr->connections[i][j] = paraData[i][j];
		}
	}

	return resultPtr;
}

void initTranverse(GraphPtr paraGraphPtr) {
	int i;

	visitedPtr = (int *)malloc(paraGraphPtr->numNodes * sizeof(int));

	for (i = 0; i < paraGraphPtr->numNodes; i++) {
		visitedPtr[i] = 0;
	}
}

void depthFirstTranverse(GraphPtr paraGraphPtr, int paraNode) {
	int i;

	visitedPtr[paraNode] = 1;
	printf("%d\t", paraNode);

	for ( i = 0; i < paraGraphPtr->numNodes; i++) {
		if (paraGraphPtr->connections[paraNode][i] && visitedPtr[i] == 0) {
			depthFirstTranverse(paraGraphPtr, i);
		}
	}
}

void widthFirstTranverse(GraphPtr paraGraphPtr, int paraNode, int cnt) {
	int tempNode[paraGraphPtr->numNodes];
	int i, front = 0;
	visitedPtr[paraNode] = 1;
	tempNode[cnt] = paraNode;
	while ((cnt + 1) != paraGraphPtr->numNodes) {
		paraNode = tempNode[front];
		for (i = 0; i < paraGraphPtr->numNodes; i++) {
			if (visitedPtr[i])
				continue;
			if (paraGraphPtr->connections[paraNode][i] == 0)
				continue;
			visitedPtr[i] = 1;
			cnt++;
			tempNode[cnt] = i;
		}
		front++;
	}

	for (i = 0; i < paraGraphPtr->numNodes; i++) {
		printf("%d\t", tempNode[i]);
	}
}

void testGraphTranverse() {
	int i, j;

	int myGraph[5][5] = {
		{0, 1, 0, 1, 0},
		{1, 0, 1, 0, 1},
		{0, 1, 0, 1, 1},
		{1, 0, 1, 0, 0},
		{0, 1, 1, 0, 0}
	};
	int **tempPtr;
	printf("Preparing data\r\n");

	tempPtr = (int **)malloc(5 * sizeof(int *));
	for (i = 0; i < 5; i++) {
		tempPtr[i] = (int *)malloc(5 * sizeof(int));
	}

	for (i = 0; i < 5; i++) {
		for (j = 0; j < 5; j++) {
			tempPtr[i][j] = myGraph[i][j];
		}
	}

	printf("Data ready\r\n");

	GraphPtr tempGraphPtr = initGraph(5, tempPtr);
	printf("num nodes = %d \r\n", tempGraphPtr->numNodes);
	printf("Graph initialized\r\n");

	printf("Depth first visit:\r\n");
	initTranverse(tempGraphPtr);
	depthFirstTranverse(tempGraphPtr, 4);

	printf("\r\nWidth first visit:\r\n");
	initTranverse(tempGraphPtr);
	widthFirstTranverse(tempGraphPtr, 4, 0);
}
int main() {
	testGraphTranverse();
	return 0;
}

#include <stdio.h>
#include <malloc.h>
#define QUEUE_SIZE 10
#define true 1
#define false 0
int* visitedPtr;

/**
 * graph data structure
 */
typedef struct Graph{
	int** connections;
	int numNodes;
} *GraphPtr;

/**
 * initialize a graph
 */
GraphPtr initGraph(int paraSize, int** paraData) {
	int i, j;
	GraphPtr resultPtr = (GraphPtr)malloc(sizeof(struct Graph));
	resultPtr -> numNodes = paraSize;
	resultPtr -> connections = (int**)malloc(paraSize * sizeof(int*));
	for (i = 0; i < paraSize; i ++) {
		resultPtr -> connections[i] = (int*)malloc(paraSize * sizeof(int));
		for (j = 0; j < paraSize; j ++) {
			resultPtr -> connections[i][j] = paraData[i][j];
		}
	}
	
	return resultPtr;
}

/**
 * queue data structure
 */
typedef struct GraphNodeQueue{
	int* nodes;
	int front;
	int rear;
}GraphNodeQueue, *QueuePtr;

/**
 * Initialize the queue
 */
QueuePtr initQueue(){
	QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct GraphNodeQueue));
	resultQueuePtr->nodes = (int*)malloc(QUEUE_SIZE * sizeof(int));
	resultQueuePtr->front = 0;
	resultQueuePtr->rear = 1;
	return resultQueuePtr;
}

/**
 * Check if the queue is full
 */
int isQueueEmpty(QueuePtr paraQueuePtr){
	if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) {
		return true;
	}
	return false;
}

/**
 * join the team
 */
void enqueue(QueuePtr paraQueuePtr, int paraNode){
	if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) {
		printf("Error, trying to enqueue %d. queue full.\r\n", paraNode);
		return;
	}
	paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode;
	paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;
}

/**
 * out of the team
 */
int dequeue(QueuePtr paraQueuePtr){
	if (isQueueEmpty(paraQueuePtr)) {
		printf("Error, empty queue\r\n");
		return NULL;
	}

	paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;

	return paraQueuePtr->nodes[paraQueuePtr->front];
}

/**
 * adjacency list node
 */
typedef struct AdjacencyNode {
	int column;
	struct AdjacencyNode* next;
}AdjacencyNode, *AdjacentNodePtr;

/**
 * adjacency list queue
 */
typedef struct AdjacencyList {
	int numNodes;
	AdjacencyNode* headers;
}AdjacencyList, *AdjacencyListPtr;

/**
 * Create an adjacency list queue
 */
AdjacencyListPtr graphToAdjacentList(GraphPtr paraPtr) {
	//application space
	int i, j, tempNum;
	AdjacentNodePtr p, q;
	tempNum = paraPtr->numNodes;
	AdjacencyListPtr resultPtr = (AdjacencyListPtr)malloc(sizeof(struct AdjacencyList));
	resultPtr->numNodes = tempNum;
	resultPtr->headers = (AdjacencyNode*)malloc(tempNum * sizeof(struct AdjacencyNode));
	
	//push data
	for (i = 0; i < tempNum; i ++) {
		//Initialize the head node
		p = &(resultPtr->headers[i]);
		p->column = -1;
		p->next = NULL;

		for (j = 0; j < tempNum; j ++) {
			if (paraPtr->connections[i][j] > 0) {
				//Create a new node
				q = (AdjacentNodePtr)malloc(sizeof(struct AdjacencyNode));
				q->column = j;
				q->next = NULL;

				//Link
				p->next = q;
				p = q;
			}
		}
	}

	return resultPtr;
}

/**
 * print adjacency list
 */
void printAdjacentList(AdjacencyListPtr paraPtr) {
	int i;
	AdjacentNodePtr p;
	int tempNum = paraPtr->numNodes;

	printf("This is the graph:\r\n");
	for (i = 0; i < tempNum; i ++) {
		p = paraPtr->headers[i].next;
		while (p != NULL) {
			printf("The node %d connects %d, ", i, p->column);
			p = p->next;
		}
		printf("\r\n");
	}
}

/**
 * Breadth-first search
 */
void widthFirstTranverse(AdjacencyListPtr paraListPtr, int paraStart){
	printf("width first \r\n");
	//Use queues to store data
	int i, j, tempNode;
	AdjacentNodePtr p;
	i = 0;

	//Initialization data
	visitedPtr = (int*) malloc(paraListPtr->numNodes * sizeof(int));
	
	for (i = 0; i < paraListPtr->numNodes; i ++) {
		visitedPtr[i] = 0;
	}

	QueuePtr tempQueuePtr = initQueue();
	printf("%d\t", paraStart);
	visitedPtr[paraStart] = 1;
	enqueue(tempQueuePtr, paraStart);
	while (!isQueueEmpty(tempQueuePtr)) {
		tempNode = dequeue(tempQueuePtr);

		for (p = &(paraListPtr->headers[tempNode]); p != NULL; p = p->next) {
			j = p->column;
			if (visitedPtr[j]) 
				continue;

			printf("%d\t", j);
			visitedPtr[j] = 1;
			enqueue(tempQueuePtr, j);
		}
	}
	printf("\r\n");
}

/**
 * Traversal of the test graph
 */
void testGraphTranverse() {
	int i, j;
	int myGraph[5][5] = { 
		{0, 1, 0, 1, 0},
		{1, 0, 1, 0, 1}, 
		{0, 1, 0, 1, 1}, 
		{1, 0, 1, 0, 0}, 
		{0, 1, 1, 0, 0}};
	int** tempPtr;
	printf("Preparing data\r\n");
		
	tempPtr = (int**)malloc(5 * sizeof(int*));
	for (i = 0; i < 5; i ++) {
		tempPtr[i] = (int*)malloc(5 * sizeof(int));
	}
	 
	for (i = 0; i < 5; i ++) {
		for (j = 0; j < 5; j ++) {
			tempPtr[i][j] = myGraph[i][j];
		}
	}
 
	printf("Data ready\r\n");
	
	GraphPtr tempGraphPtr = initGraph(5, tempPtr);
	AdjacencyListPtr tempListPtr = graphToAdjacentList(tempGraphPtr);

	printAdjacentList(tempListPtr);

	widthFirstTranverse(tempListPtr, 4);
}

/**
 * Program entry
 */
int main(){
	testGraphTranverse();
	return 0;
}