飞花如梦，阳光灿烂的日子

原创作品，作者：飞阳。转载请注明出处，谢谢。
http://hi.baidu.com/burtcn

有人说，没有收获的实践，还不如不实践呢。。
不要让重复劳作变得毫无意义。。

接下来说正题，深度优先搜索，其实很简单。。
我同学问我有没有写过，我说我懂原理，但是没写过。
今天有时间就弄了一下。

而广度优先搜索好像要用到队列。。等下试试

深度优先搜索 depth first search

测试数据如下
===================下面一行开始
a b 1 c 2 d 3#
b c 4#
c d 3#
d e 4#
e f 5 h 7#
f i 8#
g #
h e 4 g 6#
i g 6 h 7#
===================上面一行结束

 

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

#define alloc(type) (type*)malloc(sizeof(type))
#define NODE_NUM 9
#define TRUE 1
#define FALSE 0

struct adj_list{
             int index;
             char name[10];
             struct adj_list *next;
};
typedef struct adj_list Node;

//函数声明
void generate(Node[],int);
void printnode(Node*);
void showtable(Node[],int);
void travel_dfs(Node[],int[],int);
void dfs(Node[],int,int,int[],int[],int&);

int main(){
             Node node[NODE_NUM];
             generate(node,NODE_NUM);
             printf("你刚才输入的邻接表为:\n");
             showtable(node,NODE_NUM);
             int tra[NODE_NUM];
             travel_dfs(node,tra,NODE_NUM);
             printf("输出遍历的顺序\n");
             for(int i=0;i<NODE_NUM;i++)
                       if(tra[i]!=-1)
                                 printf("%s=>",node[tra[i]].name);
             printf("\n");
             return 0;
}

void travel_dfs(Node node[],int tra[],int size){
             int *isused=new int[size];
             for(int i=0;i<size;i++){
                       isused[i]=FALSE;
                       tra[i]=-1;
             }
             int count=0;
             for(i=0;i<size;i++)
                       if(isused[i]==FALSE)
                                 dfs(node,size,i,isused,tra,count);
             delete isused;
}

void dfs(Node node[],int size,int current,int isused[],int tra[],int &count){          
             isused[current]=TRUE;
             tra[count++]=current;

             Node *pos=node[current].next;
             while(pos!=NULL){                    
                       if(isused[pos->index]==FALSE)
                                 dfs(node,size,pos->index,isused,tra,count);
                       pos=pos->next;
             }
}

void generate(Node node[],int size){
             //先输入顶点名字，然后按格式输入后面的链表节点
             //格式为:name index
             //输入#结束链表节点的输入,转入其他顶点
             for(int i=0;i<size;i++){                              
                       scanf("%s",node[i].name);
                       node[i].index=i;
                       node[i].next=NULL;
                       Node *pos=&node[i];
                       char name[10];
                       int index=0;
                       while(true){                              
                                 scanf("%s",name);
                                 if(strcmp(name,"#")==0) break;
                                 scanf("%d",&index);                              
                                 Node *no=alloc(Node);
                                 strcpy(no->name,name);
                                 no->index=index;
                                 no->next=NULL;                              
                                 pos->next=no;
                                 pos=pos->next;
                       }
             }
}

void printnode(Node *node){
             printf("(%d,%s)",node->index,node->name);
}

void showtable(Node node[],int size){          
             for(int i=0;i<size;i++){
                       printnode(node+i);
                       Node *pos=node[i].next;
                       while(pos!=NULL){
                                 printf("->");
                                 printnode(pos);
                                 pos=pos->next;
                       }          
                       printf("\n");
             }
}