DFS.rar_dfs

#include"stdio.h" #include"stdlib.h" #define MAXSIZE 50 #define MAXVALUE 32767 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType Vertex[MAXSIZE]; EdgeType Edge[MAXSIZE][MAXSIZE]; int vertexnum,edgenum; int isTrav[MAXSIZE]; int GraphType; }*MGraph,Graph; typedef struct { int Data[MAXSIZE]; int top; }Stack,*PStack; PStack Init_Stack() { PStack S; S=(PStack)malloc(sizeof(Stack)); S->top=-1; return S; } void Push_Stack(PStack S,int temp) { if(S->top==MAXSIZE-1) printf("栈满，溢出！\n"); else { S->top++; S->Data[S->top]=temp; } } int Empty_Stack(PStack S) { if(S->top==-1) return 1; else return 0; } void Pop_Stack(PStack S,int*temp) { if(Empty_Stack(S)) return ; else { *temp=S->Data[S->top]; S->top--; } } void Destory_Stack(PStack*S) { if(*S) free(*S); *S=NULL; } MGraph Create_Graph() { int i,j,k,weight; char start,end; MGraph G; G=(MGraph)malloc(sizeof(Graph)); printf("请选择想要创建的图形：'0':无向图,'1':有向图\n"); scanf("%d",&(G->GraphType)); printf("请输入图的定点数和图的边数： "); scanf("%d%d",&G->vertexnum,&G->edgenum); for(i=0;i<G->vertexnum;i++) { getchar(); printf("输入第%d个节点： ",i+1); scanf("%c",&G->Vertex[i]); } for(i=0;i<G->vertexnum;i++) for(j=0;j<G->vertexnum;j++) if(i==j) G->Edge[i][j]=0; else G->Edge[i][j]=MAXVALUE; printf("输入构成各边的两个顶点及权值(用逗号分隔):\n"); for(k=0;k<G->edgenum;k++) { getchar(); printf("第%d条边： ",k+1); scanf("%c,%c,%d",&start,&end,&weight); for(i=0;start!=G->Vertex[i];i++); //在已有顶点中查找始点 for(j=0;end!=G->Vertex[j];j++); //在已有顶点中查找结终点 G->Edge[i][j]=weight; if(G->GraphType==0) G->Edge[j][i]=weight; } return G; } void OutMatrix(MGraph G) { int i,j; for(i=0;i<G->vertexnum;i++) printf("\t%c",G->Vertex[i]); printf("\n"); for(i=0;i<G->vertexnum;i++) { printf("%c\t",G->Vertex[i]); for(j=0;j<G->vertexnum;j++) { if(G->Edge[i][j]>=MAXVALUE) printf("∞\t"); else printf("%d\t",G->Edge[i][j]); } printf("\n"); } } void DFS(MGraph G,int k) { int i=0,temp=k; PStack S; S=Init_Stack(); printf("%c->",G->Vertex[temp]); Push_Stack(S,temp); while(!Empty_Stack(S)) { for(i=0;i<G->vertexnum;i++) if(G->Edge[k][i]!=MAXSIZE&&!G->isTrav[i]) break; if(i>=G->vertexnum) { Pop_Stack(S,&temp); k=temp; } else { G->isTrav[i]=1; temp=i; k=temp; printf("%c->",G->Vertex[temp]); Push_Stack(S,temp); } } Destory_Stack(&S); } void main() { int i=0; MGraph G; G=Create_Graph(); OutMatrix(G); for(i=0;i<G->vertexnum;i++) G->isTrav[i]=0; for(i=0;i<G->vertexnum;i++) if(!G->isTrav[i]) { G->isTrav[i]=1; DFS(G,i); } printf("\n"); }