dfs.c

图的用法

//由邻接表方式存储的图的深度优先遍历

#include<stdlib.h>
#include<stdio.h>
#define SIZE 100
struct node               //图的顶点结构
{
	int vertex;           //顶点数据
	struct node *nextnode;
};
typedef struct node *graph;        //图的结构新类型
struct node head[9];               //图顶点结构数组
int yjj_visited[9];                    //遍历记录数组
int **yjj_node;                        //保存用户输入的数据（起点。终点。权值）
int yjj_cost[SIZE][SIZE];                  //保存权值
/* --------------------------*/
/*      create the graph       */
/* --------------------------*/
void creategraph(int **node,int num)
{
	graph newnode;           //新顶点指针
	graph ptr;
	int from;                //边的起点
	int to;                  //边的终点
	int i;

	for(i = 0;i < num;i++)    //读取边的循环
	{
		from = node[i ][0];                               //边的起点
		to = node[i ][ 1];                                //边的终点
		yjj_cost[from][to] = node[i ][ 2];                    //边的权值
		/* create newnode */
		newnode = (graph )malloc(sizeof(struct node));
		newnode->vertex = to;
		newnode->nextnode = NULL;
		ptr = &(head[from]);
		while(ptr->nextnode != NULL)
			ptr = ptr->nextnode;                          //下一个顶点
		ptr->nextnode = newnode;                          //插入结尾
	}
}
/* --------------------------*/
/*        creta the dfs      */
/* --------------------------*/

void dfs(int current)                         //从当前点current开始深度遍历
{
	graph ptr;
	yjj_visited[current] = 1;
	printf("-->point [%d]",current);           //输出遍历顶点值
	ptr = head[current].nextnode;              //顶点位置
	while (ptr != NULL)
	{
		if(yjj_visited[ptr->vertex] == 0)
			dfs(ptr -> vertex);               //遍历递归调用
		ptr = ptr ->nextnode;                 //下一个顶点
	}
}

/* --------------------------*/
/*      the main fuction     */
/* --------------------------*/

void main()
{
	graph ptr;
	int m,n=3;            //控制动态二维数据的声请
    int i;
	clrscr();
	/* 建立二维数组保存用户的输入：包括（起点，终点，以及权值）*/
	printf("Please input one number:\n");
	scanf("%d",&m);
	yjj_node = (int **) malloc(m*sizeof(int *));
	for(i = 0;i < m;i ++)
		yjj_node[i] = (int *)malloc(n*sizeof(int));
	for(i = 0;i < m;i ++)
		{
			printf("Please input datas:\n");
			scanf ("%d,%d,%d",&yjj_node[i][0],&yjj_node[i][1], &yjj_node[i][2]) ;
		}

	for(i = 1;i <= SIZE;i++ )                //注意这里的大小一定要足够哦！
	{
		head[i].vertex = i;                 //设置顶点值:有哪些顶点
		head[i].nextnode = NULL;
	    yjj_visited[i] = 0;
	}
	creategraph(yjj_node,m);                      //create graph
	printf("dfs:\n");
	dfs(1);
	printf("\n");
}