数据结构图的遍历.doc

#include stdlib.h #include stdio.h #include malloc.h #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int *info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int *info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;ig-vexnum;i++) if(g-vexs[i]==v){k=i;i=g-vexnum;} return(k);} mgraph_hc*createudg_hc() {mgraph_hc*g; char v1,v2; int i,j,incinfo; g=(mgraph_hc*)malloc(sizeof(mgraph_hc)); g-kind=UDG; printf(请输入图顶点数、边数及该边相关信息:); scanf(%d %d %d,g-vexnum,g-arcnum,incinfo); printf(请输入顶点信息:);flushall(); for(i=0;ig-vexnum;++i)scanf(%c,g-vexs[i]); for(i=0;ig-vexnum;++i) for(j=0;jg-vexnum;++j) g-arcs[i][j].adj=0; printf(输入一条边依附的顶点:\n); flushall();scanf(%c%c,v1,v2); while(v1!=#v2!=#) {i=locatevex_hc(g,v1);j=locatevex_hc(g,v2); g-arcs[i][j].adj=1; if(incinfo)g-arcs[i][j].info=incinfo; g-arcs[j][i].adj=g-arcs[i][j].adj; g-arcs[j][i].info=g-arcs[i][j].info; flushall();scanf(%c%c,v1,v2);} return(g);} visited_hc vis[MAX_VERTEX_NUM]; int firstadjvex_hc(mgraph_hc*g,int v) {int i,k=-1; for(i=0;ig-vexnum;i++) if(g-arcs[v][i].adj==1){k=i;i=g-vexnum;} return(k);} int nextadjvex_hc(mgraph_hc*g,int v,int w) {int i,k=-1; for(i=0;ig-vexnum;i++) if(g-arcs[v][i].adj==1iw){k=i;i=g-vexnum;} return(k);} void dfs_hc(mgraph_hc*g,int v) {int w; vis[v]=TRUE; printf(%c,g-vexs[v]); for(w=firstadjvex_hc(g,v);w=0;w=nextadjvex_hc(g,v,w)) if(!vis[w])dfs_hc(g,w);} void dfstraverse_hc(mgraph_hc*g) {int v,i;char f; for(v=0;vg-vexnum;v++)vis[v]=FALSE; printf(输入遍历开始顶点:);flushall();scanf(%c,f); i=locatevex_hc(g,f