# 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.

```#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++) {
}
}

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];
}
}

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
num nodes = 5
Graph initialized
Depth first visit:
4       1       0       3       2
Width first visit:
4       1       2       0       3

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 ++) {
}
}

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

```/**
*/
int column;

/**
*/
int numNodes;

/**
* Create an adjacency list queue
*/
//application space
int i, j, tempNum;
tempNum = paraPtr->numNodes;
resultPtr->numNodes = tempNum;

//push data
for (i = 0; i < tempNum; i ++) {
p->column = -1;
p->next = NULL;

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

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

return resultPtr;
}

/**
*/
int i;
int tempNum = paraPtr->numNodes;

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

```/**
*/
printf("width first \r\n");
//Use queues to store data
int i, j, tempNode;
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];
}
}

GraphPtr tempGraphPtr = initGraph(5, tempPtr);

widthFirstTranverse(tempListPtr, 4);
}

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

### output result

Preparing data
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++) {
}
}

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];
}
}

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 ++) {
}
}

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];
}

/**
*/
int column;

/**
*/
int numNodes;

/**
* Create an adjacency list queue
*/
//application space
int i, j, tempNum;
tempNum = paraPtr->numNodes;
resultPtr->numNodes = tempNum;

//push data
for (i = 0; i < tempNum; i ++) {
p->column = -1;
p->next = NULL;

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

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

return resultPtr;
}

/**
*/
int i;
int tempNum = paraPtr->numNodes;

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

/**
*/
printf("width first \r\n");
//Use queues to store data
int i, j, tempNode;
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];
}
}

GraphPtr tempGraphPtr = initGraph(5, tempPtr);

widthFirstTranverse(tempListPtr, 4);
}

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

Tags: data structure

Posted by artcalv on Thu, 02 Jun 2022 04:46:02 +0530