gra.c

关于图的深度搜索的C语言代码实现

#include <stddef.h>
#include "assert.h"
#include "mem.h"
#include "list.h"
#include "vlist.h"
#include "queue.h"
#include "gra.h"

#define T Gra_T


struct T
{
	int vertex;
	int edge;
	VList_T *list;
};


T Gra_init(int v, int e)
{
	int i;
	T gra;
	assert(v > 0 && e >= 0);
	gra = ALLOC(sizeof(*gra) + v * sizeof(*gra->list[0]));
	gra->vertex = v;
	gra->edge = e;
	gra->list = (VList_T *)(gra + 1);
	for(i = 0; i < gra->vertex; i++)
		gra->list[i] = NULL;
	return gra;
}

T Gra_create(T gra)
{
	int i;
	List_T list;
	assert(gra);

	for(i = 0; i < gra->vertex; i++)
		gra->list[i] = VList_pushinit(gra->list[i], 0, 0);
	list = List_push(NULL, 1, 1);
	list = List_push(list, 3, 1);
	gra->list[0]->rest = (VList_T)list;


	list = List_push(NULL, 3, 1);
	list = List_push(list, 4, 1);
	gra->list[1]->rest = (VList_T)list;

	list = List_push(NULL, 0, 1);
	list = List_push(list, 5, 1);
	gra->list[2]->rest = (VList_T)list;


	list = List_push(NULL, 2, 1);
	list = List_push(list, 4, 1);
	list = List_push(list, 5, 1);
	list = List_push(list, 6, 1);
	gra->list[3]->rest = (VList_T)list;
	
	list = List_push(NULL, 6, 1);
	gra->list[4]->rest = (VList_T)list;
	

	list =NULL;
	gra->list[5]->rest = (VList_T)list;

	list = List_push(NULL, 5, 1);
	gra->list[6]->rest = (VList_T)list;
	return gra;
}



int Gra_edgeinit(T gra)
{
	int i, cont;
	assert(gra);
	for(gra->edge = 0, i = 0; i < gra->vertex; i++)
	{
		if((cont = List_length((List_T)gra->list[i]->rest)) > 0)
			gra->edge += cont;
	}
	return gra->edge;
}


void Gra_countentry(T gra)
{
	int i, j;
	assert(gra);
	for(i = 0; i < gra->vertex; i++)
		for(j = 0; j < gra->vertex; j++)
		{
			if(i == j)
				continue;
			if(List_findnumber((List_T)gra->list[j]->rest, i))
				gra->list[i]->number++;
		}
}


void Gra_shortest1(T gra, int s)
{
	int i, j;
	assert(gra);
	assert(s >= 0 && s < gra->vertex);
	gra->list[s]->dist = 0;
	for(i = 0; i < gra->vertex; i++)
		for(j = 0; j < gra->vertex; j++)
			if(gra->list[j]->dist == i)
			{
				List_T list;
				gra->list[j]->known = 1;
				for(list = (List_T)gra->list[j]->rest; list; 
					list = list->rest)
					if(gra->list[list->number]->known == 0)
					{
						gra->list[list->number]->dist = i + 1;
						gra->list[list->number]->path = j;
						gra->list[list->number]->known = 1;

					}
			}
}





void Gra_shortest(T gra, int s)
{
	int i, j;
	assert(gra);
	assert(s >= 0 && s < gra->vertex);
	gra->list[s]->dist = 0;
	for(i = 0; i < gra->vertex; i++)
		for(j = 0; j < gra->vertex; j++)
			if(gra->list[j]->known == 0 && gra->list[j]->dist == i)
			{
				List_T list;
				gra->list[j]->known = 1;
				for(list = (List_T)gra->list[j]->rest; list; 
					list = list->rest)
					if(gra->list[list->number]->dist == -1)
					{
						gra->list[list->number]->dist = i + 1;
						gra->list[list->number]->path = j;	
					}
			}
}

//this is different from the "Gra_toshortest", the scan is different
void Gra_toshortest(T gra, int s)
{
	int v;
	Queue_T que;
	assert(gra);
	assert(s >= 0 && s < gra->vertex);
	gra->list[s]->dist = 0;
	que = Queue_new(gra->vertex);
	Queue_push(que, &s);
	while(!Queue_empty(que))
	{
		List_T list;
		v = *((int *)Queue_pop(que));
		gra->list[v]->known = 1;
		for(list = (List_T)gra->list[v]->rest; list; 
			list = list->rest)
			if(gra->list[list->number]->dist == -1)
			{
				gra->list[list->number]->dist = gra->list[v]->dist + 1;
				gra->list[list->number]->path = v;
				Queue_push(que, &list->number);
			}
	}
	Queue_free(&que);
}


#include <stdio.h>
void Gra_print(T gra)
{
	int i;
	assert(gra);
	printf("gra->vertex = %d, gra->edge = %d\n", gra->vertex, gra->edge);
	for(i = 0; i < gra->vertex; i++)
	{
		printf("gra->list[%d]:\t", i);
		if(gra->list[i])
		{
			printf("number = %d, value = %d, dist = %d, " 
				"path = %d, known = %d\n", 
				gra->list[i]->number, gra->list[i]->value,
				gra->list[i]->dist, gra->list[i]->path, 
				gra->list[i]->known);
			List_print((List_T)gra->list[i]->rest);
			printf("\n");
		}
		else
			printf("%d\n\n", gra->list[i]);
	}
}





//test the function
#include <stdio.h>
int main(void)
{	
	int i;
	
	i=1;
	printf("======T Gra_init(int v, int e)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T gra;
		int v, e;
		v = 7;
		e = 0;
		gra = Gra_init(v, e);
		Gra_print(gra);
	}
	printf("\n");
	printf("\n\n\n\n");




	i=1;
	printf("======T Gra_create(T gra)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T gra;
		int v, e;
		v = 7;
		e = 0;
		gra = Gra_init(v, e);
		gra = Gra_create(gra);
		Gra_print(gra);
	}
	printf("\n");
	printf("\n\n\n\n");





	

	i=1;
	printf("======int Gra_edgeinit(T gra)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T gra;
		int edge;
		int v, e;
		v = 7;
		e = 0;
		gra = Gra_init(v, e);
		gra = Gra_create(gra);
		edge = Gra_edgeinit(gra);
		printf("gra->edge = %d\n", edge);
		Gra_print(gra);
	}
	printf("\n");
	printf("\n\n\n\n");





	
	
	i=1;
	printf("======void Gra_countentry(T gra)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T gra;
		int v, e;
		v = 7;
		e = 0;
		gra = Gra_init(v, e);
		gra = Gra_create(gra);
		Gra_countentry(gra);
		Gra_print(gra);
	}
	printf("\n");
	printf("\n\n\n\n");





	




	i=1;
	printf("======void Gra_shortest(T gra, int s)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T gra;
		int v, e;
		v = 7;
		e = 0;
		gra = Gra_init(v, e);
		gra = Gra_create(gra);
		Gra_countentry(gra);
		Gra_shortest(gra, 2);
		Gra_print(gra);
	}
	printf("\n");
	printf("\n\n\n\n");



	i=1;
	printf("======void Gra_shortest1(T gra, int s)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T gra;
		int v, e;
		v = 7;
		e = 0;
		gra = Gra_init(v, e);
		gra = Gra_create(gra);
		Gra_countentry(gra);
		Gra_shortest1(gra, 2);
		Gra_print(gra);
	}
	printf("\n");
	printf("\n\n\n\n");






	i=1;
	printf("======void Gra_toshortest(T gra, int s)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T gra;
		int v, e;
		v = 7;
		e = 0;
		gra = Gra_init(v, e);
		gra = Gra_create(gra);
		Gra_countentry(gra);
		Gra_toshortest(gra, 2);
		Gra_print(gra);
	}
	printf("\n");


	printf( "the (%d) th to test: \n", i++ );
	{
		T gra;
		int v, e;
		v = 7;
		e = 0;
		gra = Gra_init(v, e);
		gra = Gra_create(gra);
		Gra_countentry(gra);
		Gra_toshortest(gra, 0);
		Gra_print(gra);
	}
	printf("\n");
	printf("\n\n\n\n");

	return 0;
}