#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include"queue.h"
#define TYPE char
#define MAX_VERTER 50

typedef struct Graph
{
	TYPE* verter;
	size_t size;
	int edge[MAX_VERTER][MAX_VERTER];
}Graph;	

//创建图
Graph* creat_graph(size_t size)
{
	Graph* gra = malloc(sizeof(Graph));
	gra->verter = malloc(sizeof(TYPE)* size);
	gra->size = size;
	for(int i = 0 ; i < size ; i++)
	{
		gra->verter[i] = 0;
		for(int j = 0 ; j < size ; j++)
		{
			gra->edge[i][j] = 0;	
		}
	}
	//memset(gra->edge,0,sizeof(int)*MAX_VERTER*MAX_VERTER);
	return gra;
}
//添加点
bool add_verter(Graph* gra,size_t i,TYPE ver)
{
	if(i >= gra->size) return false;

	return gra->verter[i] = ver;	
}
//添加边
bool add_edge(Graph* gra,int begin,int end)
{
	if(begin == end || begin < 0 || begin >= gra->size || end < 0 || end >= gra->size || 1 == gra->edge[begin][end])
		return false;
	return gra->edge[begin][end] = 1;
}

void show_edge(Graph* gra)
{
	printf("  ");
	for(int i = 0 ; i < gra->size ; i++)
	{
		printf("%c ",gra->verter[i]);
	}
	printf("\n");
	for(int i = 0 ; i < gra->size ; i++)
	{
		printf("%c ",gra->verter[i]);
		for(int j = 0 ; j < gra->size ; j++)
		{
				printf("%d ",gra->edge[i][j]);
		}
		printf("\n");
	}
}

//深度遍历
void _dfs_ergodic(Graph* gra, int i,bool* flag)
{
	if(flag[i]) return;
	printf("%c ",gra->verter[i]);
	flag[i] = true;
	
	for(int j = 0 ; j < gra->size; j++)	//如果某一行被打印  则按列继续查找这一行中为1的下标
	{
		if(gra->edge[i][j])
		_dfs_ergodic(gra,j,flag);
	}
}
void dfs_ergodic(Graph* gra)
{
	bool flag[gra->size];
	for(int i = 0 ; i < gra->size ; i++)
	{
		flag[i] = 0;	
	}
	for(int  i = 0 ; i < gra->size ; i++)	//防止没有关联的顶点没有打印
	{
		_dfs_ergodic(gra,i,flag);
	}
	printf("\n");
}

//广度遍历
void bfs_ergodic(Graph* gra)
{
	Queue* queue = creat_queue();
	bool flag[gra->size];
	for(int i = 0 ; i < gra->size ; i++)
		flag[i] = false;

	for(int j = 0 ; j < gra->size ; j++)
	{
		if(!flag[j])
			push_queue(queue,j);
		while(!empty_queue(queue))
		{
			int k = *head_queue(queue);
			if(!flag[k])
			{
				printf("%c ",gra->verter[k]);
				flag[k] = true;
			}
			for(int l = 0 ; l < gra->size ; l++)
			{
				if(gra->edge[k][l])
					push_queue(queue,l);
			}
			pop_queue(queue);
		}
	}
}

int main()
{
	Graph* gra = creat_graph(5);
	for(int i = 0 ; i < 5 ; i++)
	{
		add_verter(gra,i,'A'+i);
	}
	add_edge(gra,0,1);
	add_edge(gra,0,2);
	add_edge(gra,0,4);
	show_edge(gra);
	printf("深度:");
	dfs_ergodic(gra);
	printf("广度:");
	bfs_ergodic(gra);
	return 0;	
}