对于用邻接表储存有向图或无向图，基于深度优先遍历算法生成树和生成森林，储存在孩子兄弟链表中：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXVERTEXNUM 100
typedef char VertexType;
typedef int EdgeType;
typedef char DataType;
typedef char ElemType;
typedef struct Edgenode{
int adjvex;
struct Edgenode *next;
DataType *info;
}Edgenode;
typedef struct VertexNode{
VertexType vertex;
Edgenode *firstedge;
}VertexNode;
typedef VertexNode Adjlist[MAXVERTEXNUM+1];
typedef struct{
Adjlist adjlist;
int n,e;
}ALGraph;
typedef struct Tree{
int data;
struct Tree *lchild;
struct Tree *nextsibling;
}CSNode,*CSTree;
typedef enum {
False,True
}Bool;
Boolvisited[MAXVERTEXNUM+1],inStack[MAXVERTEXNUM+1];
void CreateMGragh2(ALGraph *G)
{
int i,j,k;
Edgenode *s;
printf("请输入顶点数和边数（输入格式为：顶点数，边数）：");
scanf("%d%d",&(G->n),&(G->e));
printf("请输入顶点信息（输入格式为：顶点号<CR>):");
fflush(stdin);
for(i=1;i<=G->n;i++)
{
scanf("%c",&(G->adjlist[i].vertex));
G->adjlist[i].firstedge=NULL;
}
printf("请输入边的信息（输入格式为：i，j）:\n");
for(k=1;k<=G->e;k++)
{
scanf("%d%d",&i,&j);
s=malloc(sizeof(Edgenode));
s->adjvex=j;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
}
}
void DFSTree(ALGraph G,int v,CSTree T)
{
CSTree q;
Bool first=True;
Edgenode *record=G.adjlist[v].firstedge;
visited[v]=True;
while(record)
{
if(!visited[record->adjvex])
{
CSTree p=malloc(sizeof(CSNode));
p->data=record->adjvex;
p->lchild=NULL;
p->nextsibling=NULL;
if(first)
{
T->lchild=p;
first=False;
}
else
{
q->nextsibling=p;
}
q=p;
DFSTree(G,record->adjvex,q);
}
record=record->next;
}
}
void DFSForest(ALGraph G,CSTree *T)
{
int v;
CSTree q,p;
for(v=1;v<=G.n;v++)
{
visited[v]=False;
}
for(v=1;v<=G.n;v++)
{
if(!visited[v])
{
p=malloc(sizeof(CSNode));
p->data=v;
p->lchild=NULL;
p->nextsibling=NULL;
if(*T==NULL)
*T=p;
else
q->nextsibling=p;
q=p;
DFSTree(G,v,q);
}
}
}
void PreOrder(CSTree bt,void(*visit)(ElemType),ALGraph G)
{
if(bt==NULL) return;
(*visit)(G.adjlist[bt->data].vertex);
PreOrder(bt->lchild,visit,G);
PreOrder(bt->nextsibling,visit,G);
}
void visit(ElemType data)
{
printf("%c ",data);
}
int main(void)
{
ALGraph G2; //声明一个邻接表结构
CSTree T=NULL; //声明孩子兄弟链表
CreateMGragh2(&G2); //构建邻接表储存图数据。
DFSForest(G2,&T); //由图生成树后森林并用孩子兄弟链表储存起来。
PreOrder(T,visit,G2); //先根遍历。
return0;
}
运行结果：
