原創(chuàng)作品，作者：飛陽。轉(zhuǎn)載請注明出處，謝謝。
http://hi.baidu.com/burtcn

有人說，沒有收獲的實踐，還不如不實踐呢。。
不要讓重復(fù)勞作變得毫無意義。。

接下來說正題，深度優(yōu)先搜索，其實很簡單。。
我同學(xué)問我有沒有寫過，我說我懂原理，但是沒寫過。
今天有時間就弄了一下。

而廣度優(yōu)先搜索好像要用到隊列。。等下試試

深度優(yōu)先搜索 depth first search

測試數(shù)據(jù)如下
===================下面一行開始
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#
===================上面一行結(jié)束

#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;

//函數(shù)聲明
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){
             //先輸入頂點名字，然后按格式輸入后面的鏈表節(jié)點
             //格式為:name index
             //輸入#結(jié)束鏈表節(jié)點的輸入,轉(zhuǎn)入其他頂點
             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");
             }
}