资源描述
精选优质文档-倾情为你奉上#include stdafx.h#include conio.h#include stdio.h#include stdlib.htypedef enum FALSE, TRUE BOOLEAN;#define OVERFLOW -1#define OK 1#define ERROR 0#define INFINITY INT_MAX /* 最大值 */ /* 根据图的权值类型，分别定义为最大整数或实数 */#define MAX_VERTEX_NUM 20 /* 最大顶点数目 */typedef enum DG, DN, UDG,UDN GraphKind ; /* 有向图，有向网，无向图，无向网 */BOOLEAN VisitedMAX_VERTEX_NUM;BOOLEAN visitedMAX_VERTEX_NUM;#define VEX_NUM 20#define MAXSIZE 50typedef char Vextype;typedef int ElemType;typedef int Status; / 邻接矩阵结构定义typedef struct Vextype vexsVEX_NUM; int adjVEX_NUMVEX_NUM; /*邻接矩阵*/ int n,e; /*顶点数和边数*/ Mgraph; / 邻接表结构定义typedef struct node /*边结点*/int adjvex; /*邻接点域*/struct node * nextarc; /*指向下一个边结点的指针域*/ EdgeNode; typedef struct vnode /顶点结构，2个域，结点信息和第一个邻接点Vextype vertex; EdgeNode *firstedge; VertexNode; typedef struct /图结构VertexNode adjlistMAXSIZE;int n,e; ALGraph; /int FirstAdjVex(ALGraph G,int v) /在图G中寻找第v个顶点的第一个邻接顶点 if(!G.adjlistv.firstedge) return -1; else return(G.adjlistv.firstedge-adjvex); int NextAdjVex(ALGraph G,int v,int w) /在图G中寻找第v个顶点的相对于w的下一个邻接顶点 EdgeNode *p;int vi; p=G.adjlistv.firstedge; if(!p) return -1; while(p-adjvex!=w) p=p-nextarc; /在顶点v的弧链中找到顶点w p=p-nextarc;if(!p) return -1; /若已是最后一个顶点，返回-1else vi=p-adjvex;return vi; /返回下一个邻接顶点的序号 /void CreateMGraph(Mgraph *G) int i,j,k; / char ch; printf(请输入顶点数和边数:n); scanf(%d,%d,&(G-n),&(G-e); /*输入*/ printf(请输入顶点信息:n); for (i=0;in;i+) scanf(%s,&(G-vexsi); for (i=0;in;i+) for (j=0;jn;j+) G-adjij=0; /*初始化邻接矩阵*/ printf(输入每条边对应的两个顶点的序号:n); for (k=0;ke;k+) scanf(%d,%d,&i,&j); /*输入e条边*/G-adjij=1; G-adjji=1; /*对称加入,无向图的邻接矩阵存储建立*/ /*CreateMGraph*/ void CreateALGraph(ALGraph *G) /*建立无向图的邻接表存储*/int i,j,k;char vi;EdgeNode *s; printf(请输入顶点数和边数:n);scanf(%d,%d,&(G-n),&(G-e); printf(请输入顶点信息Vin例如a，每输入一个顶点后回车:n); for (i=0;in;i+) scanf(%s,&vi); G-adjlisti.vertex=vi;G-adjlisti.firstedge=NULL; printf(顶点:);for (i=0;in;i+) printf(%c(%d)-,G-adjlisti.vertex,i+1); printf(n请输入边的信息(vi,vj)n例如:1,2:n);for (k=0;ke;k+) /*建立边表*/scanf(%d,%d,&i,&j); /在头结点和边结点之间插入新的边结点 s=(EdgeNode*)malloc(sizeof(EdgeNode); s-adjvex=j-1; s-nextarc=G-adjlisti-1.firstedge;G-adjlisti-1.firstedge=s;s=(EdgeNode*)malloc(sizeof(EdgeNode); s-adjvex=i-1; s-nextarc=G-adjlistj-1.firstedge;G-adjlistj-1.firstedge=s; /输出邻接表./*CreateALGraph*/void DFS(ALGraph *G, int v) EdgeNode *p ; Visitedv=TRUE ; printf(%c-,G-adjlistv.vertex); /* 置访问标志，访问顶点v */ p=G-adjlistv.firstedge; /* 链表的第一个结点 */ while (p!=NULL) if(!Visitedp-adjvex) DFS(G, p-adjvex);/* 从v的未访问过的邻接顶点出发深度优先搜索 */ p=p-nextarc ; void DFS_traverse (ALGraph *G) int v ; EdgeNode *p ; printf(深度度优先搜索输出结点信息:);for (v=0; vn; v+) Visitedv=FALSE ; /* 访问标志初始化 */ p=G-adjlistv.firstedge ; for (v=0; vn; v+) if (!Visitedv) DFS(G,v);/队列 /typedef struct Node ElemType data; / 元素数据 struct Node *next; / 链式队列中结点元素的指针 QNode, *QueuePtr; typedef struct QueuePtr front; / 队列头指针 QueuePtr rear; / 队列尾指针 LinkQueue; Status InitQueue(LinkQueue &Q) /构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if(Q.front = NULL) exit(OVERFLOW); /存储失败 Q.front -next = NULL; return OK; Status DestoryQueue(LinkQueue &Q) /销毁队列Q while(Q.front)Q.rear = Q.front-next; /利用尾指针移动保存队头指针free(Q.front); /依次释放头结点 Q.front = Q.rear; return OK;Status QueueEmpty(LinkQueue Q) /assert(Q.front != NULL & Q.rear != NULL); if(Q.front = Q.rear) return TRUE; else return FALSE; Status EnQueue(LinkQueue &Q, ElemType e) /插入元素e为Q新的队尾元素 QueuePtr p = (QueuePtr )malloc(sizeof(QNode); if(!p) exit(OVERFLOW); /存储失败 p -data = e; p -next = NULL; Q.rear -next = p; /当前队尾指针指向新的结点 Q.rear = p; /移动队尾知道到新的结点，当前结点成为队尾结点 return OK; Status DeQueue(LinkQueue &Q, ElemType *e) /若队列不空，则删除Q的队头元素，用e返回值，并返回OK。否则返回ERROR if(Q.front = Q.rear) return ERROR; QueuePtr p = Q.front -next; *e = p -data; Q.front -next= p -next; if(Q.rear = p) Q.rear = Q.front; /只有一个元素，恢复到空队列，只有各头结点 free(p); return OK; /int Visit(int v,ALGraph G)/printf(%d,v); printf(%c-,G.adjlistv.vertex); return OK;void BFSTraverse(ALGraph G, Status (*Visit)(int v,ALGraph G)/ 连通图 G 广度优先搜索 LinkQueue Q;ElemType u;/ EdgeNode *p;int v;int w;printf(广度优先搜索输出结点信息:);for(v=0;vG.n;+v) visitedv=FALSE;/ 初始化访问标志 InitQueue(Q); /置空的辅助队列 for(v=0;v=0; w=NextAdjVex(G,u,w) if(!visitedw) /w为u尚未访问的邻接顶点 visitedw=TRUE; Visit(w,G); EnQueue(Q,w);/访问的顶点 w入队列/if /while /if/BFSTraversevoid main() /Mgraph Gm;/CreateMGraph(&Gm); /邻接矩阵存储 ALGraph G2;/邻接表存储do CreateALGraph(&G2); DFS_traverse(&G2); printf(n=n); BFSTraverse(G2, Visit); printf(n=是否还继续? 0-退出=n);while(getch()!=0);专心-专注-专业
展开阅读全文