#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef struct edge {
int vex;
edge *next;
}Edge;
typedef struct vex {
int data;
Edge *firstchild;
}Vex;
typedef struct vexedge {
int vexnum, edgenum;
Vex v[100];
}Vexedge;
typedef struct zhan {
Vex vx[100];
int top, tail;
}Zhan;
void create(Vexedge *ve) {
Edge *e;
int i, j, k;
printf("请输入结点数和边的条数:");
scanf("%d%d", &ve->vexnum, &ve->edgenum);
//初始化顶点表
for (i = 0; i<ve->vexnum; i++) {
printf("请输入顶点值:");
scanf("%d", &ve->v[i].data);
ve->v[i].firstchild = NULL;
}
//初始化边表
for (k = 0; k<ve->edgenum; k++) {
printf("请输入边的两个顶点:");
scanf("%d%d", &i, &j);
e = (Edge *)malloc(sizeof(Edge));
e->vex = j;
e->next = ve->v[i].firstchild;
ve->v[i].firstchild = e;
e = (Edge *)malloc(sizeof(Edge));
e->vex = i;
e->next = ve->v[j].firstchild;
ve->v[j].firstchild = e;
}
}
//深度遍历
int invited[100];
void dfs(Vexedge ve, int i) {
printf("%d ", ve.v[i].data);
Edge *e;
e = ve.v[i].firstchild;
invited[i] = 1;//表示该点已访问;
while (e)
{
if (invited[e->vex] == 0) {
dfs(ve, e->vex);
}
e = e->next;
}
}
void bianli(Vexedge ve) {
int i, j;
for (i = 0; i<ve.vexnum; i++) {
invited[i] = 0;
}
for (i = 0; i<ve.vexnum; i++) {
if (invited[i] == 0)
dfs(ve, i);
}
}
//广度遍历
Zhan z;
void push(Vexedge ve, int i) {
z.vx[z.top++] = ve.v[i];
}
Edge * pop() {
return z.vx[z.tail++].firstchild;
}
int invited1[100];
void bfs(Vexedge ve) {
int i, j, k;
Edge *e;
for (i = 0; i<ve.vexnum; i++) {
invited1[i] = 0;
}
for (i = 0; i<ve.vexnum; i++) {
while (invited1[i] == 0) {
invited1[i] = 1;
printf("%d ", ve.v[i].data);
push(ve, i);
while (z.top != z.tail) {
e = pop();
while (e) {
if (invited1[e->vex] == 0) {
invited1[e->vex] = 1;
printf("%d ", ve.v[e->vex].data);
push(ve, e->vex);
}
e = e->next;
}
}
}
}
}
int main() {
z.top = 0;
z.tail = 0;
Vexedge ve;
create(&ve);
bianli(ve);
printf("
");
bfs(ve);
getch();
return 0;
}