建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历

1、#include "stdafx.h"#include "conio.h"#include "stdio.h"#include "stdlib.h"typedef enum FALSE, TRUE BOOLEAN;#define OVERFLOW -1#define OK 1#define ERROR 0#define INFINITY INT_MAX /* 最大值 */ /* 根据图的权值类型，分别定义为最大整数或实数 */#define MAX_VERTEX_NUM 20 /* 最大顶点数目 */typedef

2、 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;

3、/*顶点数和边数*/ 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(ALGr

4、aph 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=

5、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;i<G->n;i+) sca

6、nf("%s",&(G->vexsi); for (i=0;i<G->n;i+) for (j=0;j<G->n;j+) G->adjij=0; /*初始化邻接矩阵*/ printf("输入每条边对应的两个顶点的序号:n"); for (k=0;k<G->e;k+) scanf("%d,%d",&i,&j); /*输入e条边*/G->adjij=1; G->adjji=1; /*对称加入,无向图的邻接矩阵存储建立*/ /*CreateMGraph*/

7、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;i<G->n;i+) scanf("%s",&vi); G->adjlisti.vertex=vi;G->

8、adjlisti.firstedge=NULL; printf("顶点:");for (i=0;i<G->n;i+) printf("%c(%d)-",G->adjlisti.vertex,i+1); printf("n请输入边的信息(vi,vj)n例如:1,2:n");for (k=0;k<G->e;k+) /*建立边表*/scanf("%d,%d",&i,&j); /在头结点和边结点之间插入新的边结点 s=(EdgeNode*)malloc(sizeof(EdgeN

9、ode); 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

10、 ; 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("深度度优先搜索输出结点信

11、息:");for (v=0; v<G->n; v+) Visitedv=FALSE ; /* 访问标志初始化 */ p=G->adjlistv.firstedge ; for (v=0; v<G->n; v+) if (!Visitedv) DFS(G,v);/队列 /typedef struct Node ElemType data; / 元素数据 struct Node *next; / 链式队列中结点元素的指针 QNode, *QueuePtr; typedef struct QueuePtr front; / 队列头指针 QueuePtr rea

12、r; / 队列尾指针 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

13、(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) exi

14、t(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 -&

15、gt;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 广度优先搜

16、索 LinkQueue Q;ElemType u;/ EdgeNode *p;int v;int w;printf("广度优先搜索输出结点信息:");for(v=0;v<G.n;+v) visitedv=FALSE;/ 初始化访问标志 InitQueue(Q); /置空的辅助队列 for(v=0;v<G.n;+v) if(!visitedv) /v 未访问 visitedv=TRUE; Visit(v,G); EnQueue(Q,v);/v 入队列 while(!QueueEmpty(Q) DeQueue(Q,&u); /队头元素出队并置为 u for(w=FirstAdjVex(G,u);w>=0; w=NextAdjVex(G,u,w) if(!visitedw) /w为u尚未访问的邻接顶点 visitedw=TRUE; Visit(w,G); EnQueue(Q,w);/访问的顶点 w入队列/i