DFS生成森林

生成【非连通图】的【深度优先生成森林】

【存储方式】孩子兄弟链表

  1. typedef struct CSNode{
  2.     TElemType data;
  3.     struct CSNode *firstchild, *nextsibling;
  4. }CSNode, *CSTree;
  7. // 建立无向图G的深度优先生成森林的 （最左）孩子（右）兄弟链表T
  8. void DFSForest(Graph G, CSTree &T) {
  9.     T = NULL;
  10.     for (v=0; v<G.vexnum; ++v) {
  11.         visited[v] = FALSE;
  12.     }
  13.     for (v=0; v<G.vexnum; ++v) {
  14.         if (!visited[v]) { //第v顶点为新的生成树的根结点
  15.             p = (CSTree)malloc(sizeof(CSNode) ); //分配根结点
  16.             *p = {GetVex(G,v), NULL, NULL}; //给该结点赋值
  17.             if (!T) T=p; //是第一棵生成树的根(T的根)
  18.             else q->nextsibling = p; //是其他生成树的根（前一棵的根的"兄弟"）
  19.             q = p; //q指示当前生成树的根
  20.             DFSTree(G, v, p); //建立以P为根的生成树
  21.         }
  22.     }
  23. }
  25. // 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树
  26. void DFSTree(Graph G, int v, CSTree &T) {
  27.     visited[v] = True;
  28.     first = True;
  29.     for (w=FirstAdjvex(G, v); w>=0; w=NextAdjvex(G, v, w)) {
  30.         if (!visited[w]) {
  31.             p = (CSTree)malloc(sizeof(CSNode)); //分配孩子结点
  32.             *p = {GetVex(G, w), NULL, NULL};
  33.             if (first) { //w是v的第一个未访问的邻接顶点
  34.                 T->lchild = p; //是根的左孩子结点
  35.                 first = False;
  36.             } else { //w是v的其他未被访问的邻接顶点
  37.                 q->nextsibling = p; //是上一邻接顶点的右兄弟结点
  38.             }
  39.             q = p;
  40.             DFSTree(G, w, q);  //从第w个顶点出发深度优先遍历图G，建立子生成树q
  41.         }
  42.     }
  43. }