今天刚做完的作业，希望大家能提出更好的建议（比如单独打印出树）
#include "Stdio.h"
#include "Conio.h"

#define MAX 30
#define MAX_VERTEX_NUM 20
#define INT_MAX 20000

int visited[MAX]={
0,0,0,0,0,0,
0,0,0,0,0,0,
0,0,0,0,0,0,
0,0,0,0,0,0,
0,0,0,0,0,0
};

/*------------------------------队列----------------------------*/
struct QNode
{
int data;
struct QNode *next;
};
struct Queue
{
struct QNode *rear;
};

/*------------------------------图----------------------------*/
typedef struct
{
char vex[MAX];
int arc[MAX][MAX];
int vexnum,arcnum;
}MGraphy; /*邻接矩阵*/

/*------------------------------树----------------------------*/
typedef struct Node
{
char data;
struct Node *lchild,*rchild; /*左右孩子指针*/

}Node,*BiTree;

/*------------------------------队列----------------------------*/

InitQueue(struct Queue *Q)
{ /*初始化链表队列*/
Q->rear=(struct QNode *)malloc(sizeof(struct QNode));
if (!Q->rear) printf("Application failed!");
Q->rear->next=Q->rear;
}

int EmptyQueue(struct Queue *Q)
{ /*判断队列是否为空*/
if (Q->rear->next==Q->rear)
return 1;
return 0;
}

EnQueue(struct Queue *Q,int e)
{ /*入队操作*/
struct QNode *p;
p=(struct QNode *)malloc(sizeof(struct QNode));

p->data=e;
p->next=Q->rear->next;
Q->rear->next=p;
Q->rear=p;

}

int DeQueue(struct Queue *Q)
{ /*出队操作*/
int back;
struct QNode *head=Q->rear->next;
struct QNode *p;

if (Q->rear->next==Q->rear)
printf("The queue is empty!");

back=head->next->data;
p=head->next;
head->next=p->next;

if (head->next==head)
Q->rear=head;

free(p);

return back;
}

/*----------------邻接矩阵的创建-------------------*/
CreateMGraphy(MGraphy *G)
{
int i=0,j=0,k=0,m,n;
char v1,v2;

printf("Please input vexnum and arcnum:\n");
scanf("%d",&(G->vexnum));
scanf("%d",&(G->arcnum));
printf("Please input vex string:");
for (i=0;i<G->vexnum;i++)
{
scanf("\n%c",&(G->vex[i]));
printf("%c ",G->vex[i]);
}
printf("\n");
for (i=0;i<G->vexnum;i++)
for (j=0;j<G->vexnum;j++)
G->arc[i][j]=0; /*弧的初始化*/
for (k=0;k<G->arcnum;k++)
{
printf("input the edge to create the graphy:\n");
scanf("%d,%d",&i,&j);
G->arc[i][j]=1; /*给已确定的弧做标记*/
G->arc[j][i]=1; /*这句表示创建的是无向图*/
}
for (i=0;i<G->vexnum;i++)
{ /*打印出弧关系矩阵*/
for (j=0;j<G->vexnum;j++)
printf("%d ",G->arc[i][j]);
printf("\n");
}

}

int LocateVex(MGraphy *G,char *v)
{
int i;
for (i=0;i<G->vexnum;i++)
if (G->vex[i]==*v)
{
printf("^^%c,%d\n",G->vex[i],i);
return i;
}

}

void DFST(MGraphy *G,int locate)
{ /*邻接矩阵深度优先遍历*/
int n;
printf("%c(%d)==>",G->vex[locate],locate);
visited[locate]=1;
for (n=0;n<G->vexnum;n++)
if (G->arc[locate][n]==1 && !visited[n])
{
DFST(G,n);
}
}

void WST(MGraphy *G,int locate)
{ /*邻接矩阵广度优先遍历*/
struct Queue Q;
int i,j;
InitQueue(&Q);
printf("\n\n=========WSTraverse:=========\n");
for (j=0;j<G->vexnum;j++)
visited[j]=0;
printf("The order is:");
printf("%c(%d)==>",G->vex[locate],locate);
visited[locate]=1;
EnQueue(&Q,locate);
while (!EmptyQueue(&Q))
{
i=DeQueue(&Q);
for (j=0;j<G->vexnum;j++)
if (G->arc[i][j]==1 && !visited[j])
{
printf("%c(%d)==>",G->vex[j],j);
visited[j]=1;
EnQueue(&Q,j);
}
}
}

void CreateTree(MGraphy *G,int locate,BiTree T)
{ /*图广度生成树*/
int i,j;
struct Queue Q;
InitQueue(&Q);
T=(BiTree)malloc(sizeof(Node));
for (j=0;j<G->vexnum;j++)
visited[j]=0;
printf("\n\n=====Graphy change to tree:=====");
T->data=G->vex[locate];
printf("\nRoot:%c \n",T->data);
visited[locate]=1;
EnQueue(&Q,locate);
printf("Child:");
while (!EmptyQueue(&Q))
{
i=DeQueue(&Q);
for (j=0;j<G->vexnum;j++)
if (G->arc[i][j]==1 && !visited[j])
{
T->lchild=(BiTree)malloc(sizeof(Node));
T->lchild->data=G->vex[j];
printf("%c ",T->lchild->data);
visited[j]=1;
EnQueue(&Q,j);
}
}
}

int main(void)
{
int i;
MGraphy *G;
BiTree T;
G=(MGraphy *)malloc(sizeof(MGraphy));
CreateMGraphy(G);
printf("========DFSTraverse:========\n");
printf("The order is:");
DFST(G,1);
WST(G,1);
CreateTree(G,1,T);
getch();
return 0;
}

aWPwJzcX.txt (4.83 KB) [原创]图的深度和广度优先遍历及其生成树！

int LocateVex(MGraphy *G,char *v)
{
int i;
for (i=0;i<G->vexnum;i++)
if (G->vex[i]==*v)
{
printf("^^%c,%d\n",G->vex[i],i);
return i;
}

}

在这里用不上