#include
#include
#define MAX_VERTEX_NUM 30 /*无向图最大顶点数*/
#define MAX_LEN 20 /*数据最大长度 */
int visited[MAX_VERTEX_NUM]; /*全局变量，访问标志数组 */
typedef struct EBox /*边结点类型*/
{
int mark; /*访问标记 */
int ivex,jvex; /*该边依附的两个顶点位置*/
struct EBox *ilink,*jlink; /*分别指向依附这两个顶点的下一条边 */
}EBox;
typedef struct VexBox /*顶点结点类型*/
{
char data[MAX_LEN];
EBox *fistedge; /*指向第一条依附该顶点的边*/
}VexBox;
typedef struct
{
VexBox list[MAX_VERTEX_NUM];
int vexnum,edgenum; /*无向图当前顶点数和边数 */
}AMLGraph;
void CreateGraph(AMLGraph *p) /*创建无向图 */
{
int i,j,k;
EBox *q;
printf("\n\t\t\t请输入图的结点个数和边的个数:"); /*输入图的结点数和边数 */
scanf("%d%d",&p->vexnum,&p->edgenum);
for(i=1;ivexnum;i++)
{ printf("\n\t\t\t请输入结点%d的名称:",i); /*输入顶点数据信息*/
scanf("%s",p->list[i].data);
p->list[i].fistedge=NULL; /*初始化指针*/
}
for(k=0;k
edgenum;k++) /*输入各边并构造多重链表*/
{
printf("\n\t\t\t请输入互相有关联的两个结点:");
scanf("%d,%d",&i,&j);
q=(EBox *)malloc(sizeof(EBox));
q->mark=0; /*对边结点赋值*/
q->ivex=i;
q->ilink=p->list[i].fistedge;
q->jvex=j;
q->jlink=p->list[j].fistedge;
p->list[i].fistedge=p->list[j].fistedge=q; /*完成边在链头的插入*/
}
printf("\n");
}
void DFS(AMLGraph *p, int v)
{ /*对第v个顶点的深度优先遍历 */
int w;
EBox *q;
visited[v]=1; /*标记已访问结点 */
printf("%s ",p->list[v].data);
for(q=p->list[v].fistedge;q!=NULL;)
{
if(q->ivex==v)
{w=q->jvex; q=q->jlink;}
else
{w=q->ivex; q=q->ilink;}
if(!visited[w]) DFS(p,w); /*对尚未访问的点调用DFS*/
}
}
void DFSTraverse(AMLGraph *p,int n)
{ /*深度优先遍历 */
int v;
printf("\n\t\t\t");
for(v=1;vvexnum;v++)
visited[v]=0; /*
访问标志数组初始化*/
DFS(p,n); /*对起始顶点调用DFS*/
for(v=1;vvexnum;v++)
if(!visited[v]) DFS(p,v); /*对尚未访问的顶点调用DFS*/
printf("\n");
}
void BFS(AMLGraph *p,int v)
{ /*对第v个顶点进行广度优先遍历*/
int u,w;
EBox *x;
typedef struct queue
{
int m;
struct queue *next;
}Q; /*辅助队列Q*/
Q *head,*tail,*q;
head=tail=(Q *)malloc(sizeof(Q));
tail->next=NULL;
visited[v]=1; /*标记已访问结点 */
printf("%s ",p->list[v].data);
tail->m=v; /*v入队列 */
tail->next=(Q *)malloc(sizeof(Q));
tail=tail->next;
tail->next=NULL;
while(head!=tail)
{
q=head;
head=head->next;
u=q->m; /*对头元素出队并置为u*/
free(q);
for(x=p->list[u].fistedge;x!=NULL;)
{
if(x->ivex==u)
{w=x->jvex;x=x->ilink;}
else
{w=x->ivex;x=x->jlink;}
if(!visited[w])
{
visited[w]=1;
printf("%s ",p->list[w].data);
tail->m=w; /*入队列*/
tail=tail->next=(Q *)malloc(sizeof(Q));
tail->next=NULL;
} /*if*/
} /*for */
} /*while*/
} /*BFS*/
void BFSTraverse(AMLGraph *p,int n)
{
printf("\n\t\t\t"); /*广度优先遍历*/
int v;
for(v=1;vvexnum;v++)
visited[v]=0; /*访问标志数组初始化*/
BFS(p,n); /*对起始顶点调用BFS*/
for(v=1;vvexnum;v++)
if(!visited[v]) BFS(p,v);
printf("\n"); /*对未访问顶点调用BFS*/
}
main() /*主函数 */
{
int x,n;
AMLGraph graph,*p;
p=&graph;
printf("\t\t\t****** 图的深度和广度优先遍历 *******\n");
while(1)
{
printf("\t\t\t ~~~~~~~~ 功能菜单 ~~~~~~~ \n");
printf("\t\t\t*********************************************\n");
printf("\t\t\t* 1.创建图 *\n");
printf("\t\t\t* 2.深度优先遍历图 *\n");
printf("\t\t\t* 3.广度优先遍历图 *\n");
printf("\t\t\t* 4.退出系统
*\n");
printf("\t\t\t*********************************************\n");
printf("\n\t\t\t请输入选择的功能编号（1-4）：");
scanf("%d",&n);
if(n4)
{
printf("\n\n\t\t\t你输入的功能号错误，请重新输入，按Enter键继续！！");
getchar();
getchar();
continue;
}
switch(n)
{
case 1:
CreateGraph(p);break;
case 2: {
printf("\n\t\t\t请输入起始遍历结点:");
scanf("%d",&x);
printf("\n\t\t\t深度优先遍历结果为:");
printf("\n");
DFSTraverse(p,x);
printf("\n");
} break;
case 3: {
printf("\n\t\t\t请输入起始遍历结点:");
scanf("%d",&x);
printf("\n\t\t\t广度优先遍历结果为:");
printf("\n");
BFSTraverse(p,x);
printf("\n");
} break;
case 4: printf("\n\n\t\t\t谢谢你的使用！\n\n\n");
exit(0);
}/*switch */
} /*while */
} /*main */
#include
#include
#define MAX_VERTEX_NUM 30 /*无向图最大顶点数*/
#define MAX_LEN 20 /*数据最大长度 */
int visited[MAX_VERTEX_NUM]; /*全局变量，访问标志数组 */
typedef struct EBox /*边结点类型*/
{
int mark; /*访问标记 */
int ivex,jvex; /*该边依附的两个顶点位置*/
struct EBox *ilink,*jlink; /*分别指向依附这两个顶点的下一条边 */
}EBox;
typedef struct VexBox /*顶点结点类型*/
{
char data[MAX_LEN];
EBox *fistedge; /*指向第一条依附该顶点的边*/
}VexBox;
typedef struct
{
VexBox list[MAX_VERTEX_NUM];
int vexnum,edgenum; /*无向图当前顶点数和边数 */
}AMLGraph;
void CreateGraph(AMLGraph *p) /*创建无向图 */
{
int i,j,k;
EBox *q;
printf("\n\t\t\t请输入图的结点个数和边的个数:"); /*输入图的结点数和边数 */
scanf("%d%d",&p->vexnum,&p->edgenum);
for(i=1;ivexnum;i++)
{ printf("\n\t\t\t请输入结点%d的名称:",i); /*输入顶点数据信息*/
scanf("%s",p->list[i].data);
p->list[i].fistedge=NULL; /*初始化指针*/
}
for(k=0;k
edgenum;k++) /*输入各边并构造多重链表*/
{
printf("\n\t\t\t请输入互相有关联的两个结点:");
scanf("%d,%d",&i,&j);
q=(EBox *)malloc(sizeof(EBox));
q->mark=0; /*对边结点赋值*/
q->ivex=i;
q->ilink=p->list[i].fistedge;
q->jvex=j;
q->jlink=p->list[j].fistedge;
p->list[i].fistedge=p->list[j].fistedge=q; /*完成边在链头的插入*/
}
printf("\n");
}
void DFS(AMLGraph *p, int v)
{ /*对第v个顶点的深度优先遍历 */
int w;
EBox *q;
visited[v]=1; /*标记已访问结点 */
printf("%s ",p->list[v].data);
for(q=p->list[v].fistedge;q!=NULL;)
{
if(q->ivex==v)
{w=q->jvex; q=q->jlink;}
else
{w=q->ivex; q=q->ilink;}
if(!visited[w]) DFS(p,w); /*对尚未访问的点调用DFS*/
}
}
void DFSTraverse(AMLGraph *p,int n)
{ /*深度优先遍历 */
int v;
printf("\n\t\t\t");
for(v=1;vvexnum;v++)
visited[v]=0; /*
访问标志数组初始化*/
DFS(p,n); /*对起始顶点调用DFS*/
for(v=1;vvexnum;v++)
if(!visited[v]) DFS(p,v); /*对尚未访问的顶点调用DFS*/
printf("\n");
}
void BFS(AMLGraph *p,int v)
{ /*对第v个顶点进行广度优先遍历*/
int u,w;
EBox *x;
typedef struct queue
{
int m;
struct queue *next;
}Q; /*辅助队列Q*/
Q *head,*tail,*q;
head=tail=(Q *)malloc(sizeof(Q));
tail->next=NULL;
visited[v]=1; /*标记已访问结点 */
printf("%s ",p->list[v].data);
tail->m=v; /*v入队列 */
tail->next=(Q *)malloc(sizeof(Q));
tail=tail->next;
tail->next=NULL;
while(head!=tail)
{
q=head;
head=head->next;
u=q->m; /*对头元素出队并置为u*/
free(q);
for(x=p->list[u].fistedge;x!=NULL;)
{
if(x->ivex==u)
{w=x->jvex;x=x->ilink;}
else
{w=x->ivex;x=x->jlink;}
if(!visited[w])
{
visited[w]=1;
printf("%s ",p->list[w].data);
tail->m=w; /*入队列*/
tail=tail->next=(Q *)malloc(sizeof(Q));
tail->next=NULL;
} /*if*/
} /*for */
} /*while*/
} /*BFS*/
void BFSTraverse(AMLGraph *p,int n)
{
printf("\n\t\t\t"); /*广度优先遍历*/
int v;
for(v=1;vvexnum;v++)
visited[v]=0; /*访问标志数组初始化*/
BFS(p,n); /*对起始顶点调用BFS*/
for(v=1;vvexnum;v++)
if(!visited[v]) BFS(p,v);
printf("\n"); /*对未访问顶点调用BFS*/
}
main() /*主函数 */
{
int x,n;
AMLGraph graph,*p;
p=&graph;
printf("\t\t\t****** 图的深度和广度优先遍历 *******\n");
while(1)
{
printf("\t\t\t ~~~~~~~~ 功能菜单 ~~~~~~~ \n");
printf("\t\t\t*********************************************\n");
printf("\t\t\t* 1.创建图 *\n");
printf("\t\t\t* 2.深度优先遍历图 *\n");
printf("\t\t\t* 3.广度优先遍历图 *\n");
printf("\t\t\t* 4.退出系统
*\n");
printf("\t\t\t*********************************************\n");
printf("\n\t\t\t请输入选择的功能编号（1-4）：");
scanf("%d",&n);
if(n4)
{
printf("\n\n\t\t\t你输入的功能号错误，请重新输入，按Enter键继续！！");
getchar();
getchar();
continue;
}
switch(n)
{
case 1:
CreateGraph(p);break;
case 2: {
printf("\n\t\t\t请输入起始遍历结点:");
scanf("%d",&x);
printf("\n\t\t\t深度优先遍历结果为:");
printf("\n");
DFSTraverse(p,x);
printf("\n");
} break;
case 3: {
printf("\n\t\t\t请输入起始遍历结点:");
scanf("%d",&x);
printf("\n\t\t\t广度优先遍历结果为:");
printf("\n");
BFSTraverse(p,x);
printf("\n");
} break;
case 4: printf("\n\n\t\t\t谢谢你的使用！\n\n\n");
exit(0);
}/*switch */
} /*while */
} /*main */