本文共 2562 字,大约阅读时间需要 8 分钟。
标签:dfs bfs
#include#include #include using namespace std;#define M 20 //预定义图的最大顶点数int visited[M];typedef char DataType; //顶点信息数据类型typedef struct node{ //边表结点 int adjvex; struct node *next;}EdgeNode;typedef struct vnode{ //头结点 DataType vertex; EdgeNode *FirstEdge;}VertexNode;typedef struct{ //邻接表类型 VertexNode adjlist[M]; //存放头结点的顺序表 int n, e; //图的顶点数与边数}LinkedGraph;void creat(LinkedGraph *g){ freopen("g11.txt", "r", stdin); EdgeNode *s; scanf("%d %d", &g->n, &g->e); for(int i = 0; i < g->n; i++){ scanf("%1s", &g->adjlist[i].vertex); //读入顶点信息 g->adjlist[i].FirstEdge = NULL; //边表置为空表 } for(int k = 0; k < g->e; k++){ //循环e次建立边表 int i, j; scanf("%d %d",&i,&j); s = (EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex = j; //邻接点序号为j s->next = g->adjlist[i].FirstEdge; g->adjlist[i].FirstEdge = s; //将新结点*s插入顶点vi的边表头部 s = (EdgeNode *)malloc(sizeof(EdgeNode)); //无向图 s->adjvex = i; //邻接点序号为i s->next = g->adjlist[j].FirstEdge; g->adjlist[j].FirstEdge = s; //将新结点*s插入顶点vj的边表头部 }}void print(LinkedGraph g){ for(int i = 0; i < g.n; i++){ printf("%c", g.adjlist[i].vertex); EdgeNode *p = g.adjlist[i].FirstEdge; while(p){ printf("-->%d", p->adjvex); p = p->next; } printf("\n"); }}void dfs(LinkedGraph g,int i){ visited[i] = 1; printf("%c", g.adjlist[i].vertex); for(EdgeNode *p = g.adjlist[i].FirstEdge; p; p = p->next) if(!visited[p->adjvex]) dfs(g, p->adjvex);}void DfsTraverse(LinkedGraph g){ for(int i = 0; i < g.n; i++) visited[i] = 0; for(int i = 0; i < g.n; i++) if(!visited[i]) dfs(g, i);}queue q;void bfs(LinkedGraph g, int i){ visited[i] = 1; printf("%c", g.adjlist[i].vertex); q.push(i); while(!q.empty()){ EdgeNode *u = g.adjlist[q.front()].FirstEdge; q.pop(); for(EdgeNode *p = u; p; p = p->next) if(!visited[p->adjvex]){ visited[p->adjvex] = 1; printf("%d", p->adjvex); q.push(p->adjvex); } }}void BfsTraverse(LinkedGraph g){ for(int i = 0; i < g.n; i++) visited[i] = 0; for(int i = 0; i < g.n; i++) if(!visited[i]) bfs(g, i);}int main(){ LinkedGraph g; creat(&g); printf("The graph is:\n"); print(g); printf("\n"); DfsTraverse(g); printf("\n"); BfsTraverse(g); printf("\n"); return 0;}
数据文件
输出结果