图的两种遍历方式dfs/bfs

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

int visited[100];

typedef struct {
	int** connection;
	int nodesize;
}Graph,*GraphPtr;

GraphPtr Init(int** matrix,int size) {
	GraphPtr G = (GraphPtr)malloc(sizeof(Graph));
	G->connection = (int**)malloc(sizeof(int*) * size);
	for (int i = 0; i < size; i++) {
		G->connection[i] = (int*)malloc(sizeof(int) * size);
	}
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			G->connection[i][j] = matrix[i][j];
		}
	}
	G->nodesize = size;
	memset(visited, 0, sizeof(int) * 100);
	return G;
}

void DFS(GraphPtr G, int N) {
	visited[N] = 1;
	printf("%d\n", N);
	for (int i = 0; i < G->nodesize; i++) {
		if ((!visited[i]) && G->connection[N][i]) DFS(G, i);
	}
	return;
}

#define max_size 10

typedef struct {
	int front, rear;
	int data[max_size];
}CircleQue,*CircleQuePtr;

CircleQuePtr InitQ() {
	CircleQuePtr C_Que = (CircleQuePtr)malloc(sizeof(CircleQue) * max_size);
	C_Que->front = 0;
	C_Que->rear = 0;
	return C_Que;
}

void enque(CircleQuePtr C_Que,int data) {
	if ((C_Que->rear + 1) % max_size == C_Que->front) {
		printf("no space \n");
		return;
	}
	C_Que->data[C_Que->rear%max_size] = data;
	C_Que->rear++;
}

int deque(CircleQuePtr C_Que) {
	if (C_Que->front == C_Que->rear) {
		printf("NULL\n");
		return -1;
	}
	int tempdata = C_Que->data[C_Que->front%max_size];
	C_Que->front++;
	return tempdata;
}


void BFS(GraphPtr G, int N) {
	CircleQuePtr Q = InitQ();
	enque(Q, N);
	visited[N] = 1;
	int a;
	while (Q->front != Q->rear) {
		a = deque(Q);
		printf("%d", a);
		for (int i = 0; i < G->nodesize; i++) {
			if ((!visited[i]) && G->connection[a][i]) {
				enque(Q, i);
				visited[i] = 1;//应该入队就赶紧标记
			}
		}

	}
}


int main() {
	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;

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

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			tempPtr[i][j] = myGraph[i][j];
		}
	}
	GraphPtr G = Init(tempPtr, 5);
	//DFS(G, 4);
	BFS(G, 4);

	return 0;

}