对图的深度优先搜索遍历DFS(或BFS)算法稍作修改，就可得到构造图的DFS生成树算法。
在算法中，树的存储结构采用孩子—兄弟表示法。首先建立从某个顶点V出发，建立一个树结点，然后再分别以V的邻接点为起始点，建立相应的子生成树，并将其作为V 结点的子树链接到V结点上。显然，算法是一个递归算法。
(1) DFStree算法
typedef struct CSNode
{
ElemType data ;
struct CSNode *firstchild , *nextsibling ;
}CSNode ;
CSNode *DFStree(ALGraph *G , int v)
{
CSNode *T , *ptr , *q ;
LinkNode *p ;
int w ;
Visited[v]=TRUE ;
T=(CSNode *)malloc(sizeof(CSNode)) ;
T->data=G->AdjList[v].data ;
T->firstchild=T->nextsibling=NULL ; // 建立根结点
q=NULL ;
p=G->AdjList[v].firstarc ;
while (p!=NULL)
{
w=p->adjvex ;
if (!Visited[w])
{
ptr=DFStree(G,w) ; /* 子树根结点 */
if (q==NULL) T->firstchild=ptr ;
else q->nextsibling=ptr ;
q=ptr ;
}
p=p->nextarc ;
}
return(T) ;
}
(2) BFStree算法
typedef struct Queue
{
int elem[MAX_VEX] ;
int front , rear ;
}Queue ; /* 定义一个队列保存将要访问顶点 */
CSNode *BFStree(ALGraph *G ,int v)
{
CSNode *T , *ptr , *q ;
LinkNode *p ;
Queue *Q ;
int w , k ;
Q=(Queue *)malloc(sizeof(Queue)) ;
Q->front=Q->rear=0 ; /*建立空队列并初始化*/
Visited[v]=TRUE ;
T=(CSNode *)malloc(sizeof(CSNode)) ;
T->data=G->AdjList[v].data ;
T->firstchild=T->nextsibling=NULL ; // 建立根结点
Q->elem[++Q->rear]=v ; /* v入队 */
while (Q->front!=Q->rear)
{
w=Q->elem[++Q->front] ;
q=NULL ;
p=G->AdjList[w].firstarc ;
while (p!=NULL)
{
k=p->adjvex ;
if (!Visited[k])
{
Visited[k]=TRUE ;
ptr=(CSNode *)malloc(sizeof(CSNode)) ;
ptr->data=G->AdjList[k].data ;
ptr->firstchild=T->nextsibling=NULL ;
if (q==NULL) T->firstchild=ptr ;
else q->nextsibling=ptr ;
q=ptr ;
Q->elem[++Q->rear]=k ; /* k入对 */
} /* end if */
p=p->nextarc ;
} /* end while p */
} /* end whil Q */
return(T) ;
} /*求图G广度优先生成树算法BFStree*/
(3) 图的生成森林算法
CSNode *DFSForest(ALGraph *G)
{
CSNode *T , *ptr , *q ;
int w ;
for (w=0; w<G->vexnum; w++)
Visited[w]=FALSE;
T=NULL ;
for (w=0 ; w<G->vexnum ; w++)
if (!Visited[w])
{
ptr=DFStree(G, w) ;
if (T==NULL) T=ptr ;
else q->nextsibling=ptr ;
q=ptr ;
}
return(T) ;
}