// algo7-3.cpp 調用算法7.7和7.8
 #include"c1.h"
 #include"func7-1.cpp" // 包括頂點信息類型的定義及對它的操作
 #include"func7-4.cpp" // 弧(邊)的相關信息類型的定義及對它的操作
 typedef VertexType TElemType; // 定義樹的元素類型為圖的頂點類型
 #include"c6-4.h" // 孩子-兄弟二叉鏈表存儲結構
 #include"bo6-6.cpp" // 孩子-兄弟二叉鏈表存儲結構的先根遍歷操作
 #include"c7-2'.h" // 圖的鄰接表存儲結構(與單鏈表的變量類型建立聯系)
 Boolean visited[MAX_VERTEX_NUM]; // 訪問標志數組(全局量)
 #include"bo7-2.cpp" // 圖的鄰接表的基本操作
 typedef ALGraph Graph; // 定義圖的存儲結構為鄰接表

 void DFSTree(Graph G,int v,CSTree &T)
 { // 從第v個頂點出發深度優先遍歷圖G，建立以T為根的生成樹。算法7.8
   Boolean first=TRUE; // 樹T還沒有第1個孩子結點的標志
   int w;
   CSTree p,q; // 孩子-兄弟二叉鏈表結點的指針類型
   visited[v]=TRUE; // 頂點v已被訪問的標志
   for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) // w依次為v的鄰接頂點
     if(!visited[w]) // 頂點w尚未被訪問
     { p=(CSTree)malloc(sizeof(CSNode)); // 分配孩子結點給p
       p->data=GetVex(G,w); // 將頂點w的值賦給孩子結點的data域
       p->firstchild=NULL; // 孩子結點的firstchild域和nextsibling域賦空
       p->nextsibling=NULL;
       if(first) // 頂點w是頂點v的第1個未被訪問的鄰接頂點
       { T->firstchild=p; // 頂點w是根的第1個孩子結點
         first=FALSE; // 樹T有第1個孩子結點的標志
       }
       else // 頂點w是頂點v的其他未被訪問的鄰接頂點
         q->nextsibling=p; // 是上一鄰接頂點的兄弟姐妹結點
                           // for循環的第1次不通過此處，以后q已賦值
       q=p; // q指向p所指結點
       DFSTree(G,w,q); // 從第w個頂點出發深度優先遍歷圖G，建立子生成樹q
     }
 }

 void DFSForest(Graph 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) // 對所有頂點v
     if(!visited[v]) // 第v個頂點不曾被訪問
     { // 第v個頂點為新的生成樹的根結點
       p=(CSTree)malloc(sizeof(CSNode)); // 動態生成根結點
       p->data=GetVex(G,v); // 給根結點賦值
       p->firstchild=NULL; // 結點的firstchild域和nextsibling域賦空
       p->nextsibling=NULL; // 以下將p所指結點插到樹T中
       if(!T) // p所指結點是第1棵生成樹T的根結點
         T=p; // T指向p所指結點
       else // p是其他生成樹的根(前一棵樹根的“兄弟”)
         q->nextsibling=p; // for循環的第1次，T=NULL，不通過此處，以后q已由下句賦值
       q=p; // q指示當前生成樹的根
       DFSTree(G,v,p); // 建立以p為根的生成樹
     }
 }

 void main()
 {
   Graph g;
   CSTree t;
   printf("請選擇無向圖\n");
   CreateGraph(g); // 構造無向圖g
   Display(g); // 輸出無向圖g
   DFSForest(g,t); // 建立無向圖g的深度優先生成森林的孩子-兄弟鏈表t
   printf("先序遍歷生成森林：\n");
   PreOrderTraverse(t,Visit); // 先序遍歷生成森林的孩子-兄弟鏈表t
   printf("\n");
 }