/* 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;
}