# Makefile 
CC=gcc
CFLAGS= -g -Wall
SRCS=test.c graph.c link_queue.c
OBJS=$(SRCS:.c=.o)                   #variable replace     
APP=test

all:$(OBJS)                         #指定一个目标， 不然默认目标不会检查依赖文件的时间戳
	$(CC) $(SRCS) -o $(APP)
.PHONY:clean
clean:
	rm ./*.o $(APP)

/* graph .h */
#ifndef _GRAPH_H_
#define _GRAPH_H_

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

#define MAXN 128

typedef int element_type;
typedef struct {
	element_type vertex[MAXN];
	element_type edge[MAXN][MAXN];
	int reality_num;
}graph_t;

graph_t *graph_create(int n, element_type a[][n]);
int graph_release(graph_t *g);
void vertex_edge_show(graph_t *g);
void DFS(graph_t *g, int v);
void BFS(graph_t *g, int v);

#endif

/* graph .c */
#include "graph.h"
#include "link_queue.h"

/*
*brife: create graph
*/
graph_t *graph_create(int n, element_type a[][n])
{
	if(a == NULL) {
		printf("%s, param is invalid\n", __func__);
		return NULL;
	}

	graph_t *g = (graph_t *)malloc(sizeof(graph_release));
	if(g == NULL) {
		printf("%s, malloc failed\n", __func__);
		return NULL;
	}

	int i, j;
	for(i = 0; i < n; i++) {
		g->vertex[i] = i;					
		for(j = 0; j < n; j++) {
			g->edge[i][j] = a[i][j];
		}
	}

	g->reality_num = n;

	return g;
}

/*
*brife: release graph
*/
int graph_release(graph_t *g)
{
	if(g == NULL) {
		printf("%s, param is invalid\n", __func__);
		return -1;
	}
	
	memset(g, 0, sizeof(graph_t));
	free(g);
	
	return 0;
}

/*
* brife: check vertex and edge
*/
void vertex_edge_show(graph_t *g)
{
	if(g == NULL) {
		printf("%s, param is invalid\n", __func__);
		return;
	}

	int i, j;

	printf("vertex:\n");
	for(i = 0; i < g->reality_num; i++) {
		printf("%d ", g->vertex[i]);
	}
	puts("");

	printf("edge:\n");
	for(i = 0; i < g->reality_num; i++) {
		for(j = 0; j < g->reality_num; j++) {
			printf("%d ", g->edge[i][j]);
		}
		puts("");
	}
	puts("");

	return;
}


/*brife: 深度优先遍历
 *
 * */
void DFS(graph_t *g, int v)
{
	if(g == NULL) {
		printf("%s, param is NULL\n", __func__);
		return ;
	}

	/* 每一次递归使用的就是同一个记录数组 */
	static int visited[MAXN];                /* 数组标记的方法判断某些问题 */
	int i;

	printf("V%d ", v);
	visited[v] = 1;

	for(i = 0; i < g->reality_num; i++) {
		if(g->edge[v][i] == 1 && visited[i] == 0)
			DFS(g, i);
	}

	return ;
}


/*brife: graph breadth foreach
 *
 * */
void BFS(graph_t *g, int v)
{	
	if(g == NULL) {
		printf("%s, param is NULL\n", __func__);
		return ;
	}

	int i, visited[MAXN] = {0};
	
	linkqueue_t *lq;
	if((lq = link_queue_create()) == NULL) {
		printf("%s, link queue create failed\n", __func__);
		return;
	}
	printf("V%d ", v);
	visited[v] = 1;
	
	link_queue_entry(lq, v);

	while(!link_queue_isempty(lq)) {
		v = link_queue_departure(lq);
		for(i = 0; i < g->reality_num; i++) {
			if(g->edge[v][i] == 1 && visited[i] == 0) {
				printf("V%d ", g->vertex[i]);
				visited[i] = 1;
				link_queue_entry(lq, i);
			}
		}
	}

	return;
}

/* test.c */
#include "graph.h"

int main(int argc, const char *argv[])
{
	element_type matrix[4][4] = {
		{0, 1, 1, 0},
		{1, 0, 1, 1},
		{1, 1, 0, 1},
		{0, 1, 1, 0},
	};

	/* matrix address, vertex nums */
	graph_t *g = graph_create(4, matrix);
	if(g == NULL) {
		printf("%s, graph create failed\n", __func__);
		return -1;
	}

	vertex_edge_show(g);

	puts("DFS: ");
	DFS(g, 0);
	puts("");


	puts("BFS: ");
	BFS(g, 0);
	puts("");


	return 0;
}