dfs.c

该文件夹中包含了大部分经典的算法的源程序代码

/* file name: dfs.c */
/*图的遍历一邻接表与深度优先搜索法（DFS）*/

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

#define MAX_V 100  /*最大节点数*/
#define TRUE 1
#define FALSE 0

/*定义数据结构*/
typedef struct node_tag {
	int vertex;
	struct node_tag *link;
} Node;

Node *adjlist[MAX_V+1];  /*宣告邻接表*/
int visited[MAX_V+1];  /*记录顶点是否已访问*/
int total_vertex;


void build_adjlist();
void show_adjlist();
void dfs(int);
Node *searchlast(Node *);

void main()
{
	build_adjlist(); /*以邻接表表示图*/
	show_adjlist();  /*显示表之数据*/
	puts("\n------Depth Fisrt Search------");
	dfs(1);     /*图之踪向优先搜索，以顶点1为启始顶点*/
}

void build_adjlist()
{
	FILE *fptr;
	Node *node,*lastnode;
	int vi,vj ,weight;

	fptr = fopen("dfs.dat","r");
	if ( fptr == NULL )
	{
		perror("dfs.dat");
		exit(0);
	}

	/*读取节点总数*/
	fscanf(fptr,"%d",&total_vertex);
	for ( vi = 1; vi <= total_vertex; vi++)
	{
		/*设定数组及各表启始值*/
		visited[vi] = FALSE;
		adjlist[vi] = (Node *)malloc(sizeof(Node));
		adjlist[vi]->vertex = vi;
		adjlist[vi]->link = NULL;
	}

	/*读取节点数据*/
	for ( vi = 1; vi <= total_vertex; vi++ )
		for ( vj = 1; vj <= total_vertex; vj++ )
		{
			fscanf(fptr,"%d",&weight);
			/* 数据文件以邻接矩阵格式储存,以1代表邻接
               0 代表不邻接，将邻接顶点链接在各表后 */
			if ( weight != 0 )
			{
				node = (Node *)malloc(sizeof(Node));
				node->vertex = vj;
				node->link = NULL;
				lastnode = searchlast(adjlist[vi]);
				lastnode->link = node;
			}
		}
	fclose(fptr);
}

/*显示各邻接表之数据*/
void show_adjlist()
{
	int index;
	Node *ptr;

	puts("Head    adjacency nodes");
	puts("------------------------------");
	for (index = 1; index <= total_vertex; index++)
	{
		printf("V%-2d ",adjlist[index]->vertex);
		ptr = adjlist[index]->link;
		while ( ptr != NULL )
		{
			printf("--> V%d ",ptr->vertex);
			ptr = ptr->link;
		}
		printf("\n");
	}
}

/*图的深度优先搜索*/
void dfs(int v)
{
	Node *ptr;
	int w;

	printf("V%d ",adjlist[v]->vertex);
	visited[v] = TRUE;          /*设定v顶点为已访问过*/
    ptr = adjlist[v]->link;     /*访问邻接顶点*/

	do
	{
		/* 若顶点尚未走访，则以此顶点为新启始点继续
   做踪向优先搜索法走访，否则找与其邻接的顶点
   直到所有相连接的节点都已走访          */
		w = ptr->vertex;
		if ( !visited[w] )
			dfs(w);
		else
			ptr = ptr->link;
	} while ( ptr != NULL);
}

/*搜索表最后节点函数*/
Node *searchlast( Node *linklist )
{
	Node *ptr;

	ptr = linklist;
	while ( ptr->link != NULL ) ptr = ptr->link;
	return ptr;
}