实验5 图的操作
?
?
?
参考代码：
?
#include "stdio.h"#include "conio.h"#define MaxVertexNum 100#define MAXSIZE 100typedef struct{ int data[MAXSIZE]; int front; int rear;}SeqQueue;typedef char VertexType;typedef enum{FALSE,TRUE}Boolean;Boolean visited[MaxVertexNum];typedef char elemtype;/*边结点*/typedef struct node{ int adjvex;/*邻接点域*/ struct node *nextedge;/*链域*/}EdgeNode;/*顶点表结点*/typedef struct vnode{ VertexType vertex; /*顶点域*/ EdgeNode *firstedge; /*边表头指针*/}VertexNode;typedef VertexNode AdjList[MaxVertexNum];/*AdjList是邻接表类型*//* 对于简单的应用，无须定义此类型，可直接使用AdjList类型*/typedef struct{ AdjList adjlist;/*邻接表*/ int n,e; /*当前结点数和边数*/ int kind; /*图的种类标志*/}ALGraph;/*建立无向图的邻接表*/void CreateALGraPh(ALGraph *G1){ int i,j,k; EdgeNode *s; /*读入顶点数和边数*/ printf("please input vertices: "); scanf("%d",&G1->n);getchar(); printf("please input Vertex edge number: "); scanf("%d",&G1->e);getchar(); /*建立顶点表*/ for(i=0;i<G1->n;i++) { printf("please input the %dth Vertex\n",i+1); scanf("%c",&G1->adjlist[i].vertex);getchar(); /*读入顶点信息*/ G1->adjlist[i].firstedge=NULL; /*边表置为空表*/ } printf("Please enter no to chart the relationship between vertices.the style is vi,vj\n\n "); /*建立边表*/ for(k=0;k<G1->e;k++) { printf("the %dth is: ",k+1); scanf("%d,%d",&i,&j); /*读入边(vi,vj)的顶点对序号*/ s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成边表结点*/ s->adjvex=j;/*邻接点序号为j*/ s->nextedge=G1->adjlist[i].firstedge; G1->adjlist[i].firstedge=s;/*将新结点*s插入顶点vi的边表头部*/ s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i;/*邻接点序号为i*/ s->nextedge=G1->adjlist[j].firstedge; G1->adjlist[j].firstedge=s; /*将新结点*s插入顶点vj的边表头部*/ }}/*邻接表表示的深度优先遍历*/void DFS(ALGraph *G1,int i){ EdgeNode *p; printf("%c ",G1->adjlist[i].vertex);/*访问顶点vi*/ visited[i]=TRUE;/*标记vi已访问*/ p=G1->adjlist[i].firstedge; /*取vi边表的头指针*/ while(p) { if(!visited[p->adjvex]) /*若vi尚未被访问，则以vj为出发点向纵深搜索*/ { DFS(G1,p->adjvex); } p=p->nextedge;/*找vi的下一邻接点*/ }}/*邻接表表示的广度优先遍历*/void BFS(ALGraph *G,int k){ int i; SeqQueue *Q; EdgeNode *p; /*初始队列*/ Q=(SeqQueue *)malloc(sizeof(SeqQueue)); Q->front=Q->rear=0; printf("%c ",G->adjlist[k].vertex); visited[k]=TRUE; /*入队*/ Q->data[Q->rear]=k; Q->rear=(Q->rear+1)%MAXSIZE; Q->rear++; while(Q->rear) { i=Q->data[Q->front]; Q->front=(Q->front+1)%MAXSIZE; Q->rear--; p=G->adjlist[i].firstedge; while(p) { if(!visited[p->adjvex]) { printf("%c ",G->adjlist[p->adjvex].vertex); visited[p->adjvex]=TRUE; Q->data[Q->rear]=p->adjvex; Q->rear=(Q->rear+1)%MAXSIZE; Q->rear++; } p=p->nextedge; } }}executeBFS(ALGraph *G){ int i; for(i=0;i<G->n;i++)/*将图G的所有顶点设置未访问过标记 */ visited[i]=FALSE; for(i=0;i<G->n;i++)/*对图G调用bfs函数进行广度优先搜索*/ if(!visited[i]) BFS(G,i);}main(){ ALGraph *G1; int i; CreateALGraPh(&G1); printf("DFS\n"); DFS(&G1,0); printf("\nBFS\n"); executeBFS(&G1); getch();}?
?
?
?
?