/* algo7-1.c 調用算法7.7、7.8 */
 #include"c1.h"
 #define MAX_NAME 2 /* 頂點字符串的最大長度+1 */
 typedef char ElemType[MAX_NAME];
 typedef ElemType TElemType;
 #include"c6-5.h"
 typedef int InfoType;
 typedef char VertexType[MAX_NAME];
 #include"c7-2.h"
 #include"bo7-2.c"

 void DFSTree(ALGraph G,int v,CSTree *T)
 { /* 從第v個頂點出發深度優先遍歷圖G,建立以T為根的生成樹。算法7.8 */
   Boolean first=TRUE;
   int w;
   CSTree p,q;
   VertexType v1,w1;
   visited[v]=TRUE;
   strcpy(v1,*GetVex(G,v));
   for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w)))) /* w依次為v的鄰接頂點 */
     if(!visited[w]) /* w頂點不曾被訪問 */
     {
       p=(CSTree)malloc(sizeof(CSNode)); /* 分配孩子結點 */
       strcpy(p->data,*GetVex(G,w));
       p->firstchild=NULL;
       p->nextsibling=NULL;
       if(first)
       { /* w是v的第一個未被訪問的鄰接頂點 */
         (*T)->firstchild=p;
         first=FALSE; /* 是根的第一個孩子結點 */
       }
       else /* w是v的其它未被訪問的鄰接頂點 */
	 q->nextsibling=p; /* 是上一鄰接頂點的兄弟姐妹結點 */
       q=p;
       DFSTree(G,w,&q); /* 從第w個頂點出發深度優先遍歷圖G,建立子生成樹q */
     }
 }

 void DFSForest(ALGraph G,CSTree *T)
 { /* 建立無向圖G的深度優先生成森林的(最左)孩子(右)兄弟鏈表T。算法7.7 */
   CSTree p,q;
   int v;
   *T=NULL;
   for(v=0;v<G.vexnum;++v)
     visited[v]=FALSE; /* 賦初值 */
   for(v=0;v<G.vexnum;++v) /* 從第0個頂點找起 */
     if(!visited[v])
     { /* 第v頂點為新的生成樹的根結點 */
       p=(CSTree)malloc(sizeof(CSNode)); /* 分配根結點 */
       strcpy(p->data,*GetVex(G,v));
       p->firstchild=NULL;
       p->nextsibling=NULL;
       if(!*T) /* 是第一棵生成樹的根(T的根) */
         *T=p;
       else /* 是其它生成樹的根(前一棵的根的＂兄弟＂) */
         q->nextsibling=p;
       q=p; /* q指示當前生成樹的根 */
       DFSTree(G,v,&p); /* 建立以p為根的生成樹 */
     }
 }

 void PreOrderTraverse(CSTree T,void(*Visit)(TElemType))
 { /* 先根遍歷孩子－兄弟二叉鏈表結構的樹T(bo6-5.c改) */
   if(T)
   {
     Visit(T->data); /* 先訪問根結點 */
     PreOrderTraverse(T->firstchild,Visit); /* 再先根遍歷長子子樹 */
     PreOrderTraverse(T->nextsibling,Visit); /* 最后先根遍歷下一個兄弟子樹 */
   }
 }

 void print(char *i)
 {
   printf("%s ",i);
 }

 void main()
 {
   ALGraph g;
   CSTree t;
   printf("請選擇無向圖\n");
   CreateGraph(&g);
   Display(g);
   DFSForest(g,&t);
   printf("先根遍歷生成森林：\n");
   PreOrderTraverse(t,print);
   printf("\n");
 }