#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 enum {DG, DN, UDG,UDN} GraphKind ;/* {有向图，有向网，无向图，无向网} */BOOLEAN Visited[MAX_VERTEX_NUM];BOOLEAN visited[MAX_VERTEX_NUM];#define VEX_NUM 20#define MAXSIZE 50typedef char Vextype;typedef int ElemType;typedef int Status;////////////////////////////// 邻接矩阵结构定义typedef struct {Vextype vexs[VEX_NUM];int adj[VEX_NUM][VEX_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 adjlist[MAXSIZE];int n,e;} ALGraph;////int FirstAdjVex(ALGraph G,int v){//在图G中寻找第v个顶点的第一个邻接顶点if(!G.adjlist[v].firstedge) return -1;else return(G.adjlist[v].firstedge->adjvex);}int NextAdjVex(ALGraph G,int v,int w){//在图G中寻找第v个顶点的相对于w的下一个邻接顶点EdgeNode *p;int vi;p=G.adjlist[v].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;i<G->n;i++)scanf("%s",&(G->vexs[i]));for (i=0;i<G->n;i++)for (j=0;j<G->n;j++)G->adj[i][j]=0; /*初始化邻接矩阵*/printf("输入每条边对应的两个顶点的序号:\n");for (k=0;k<G->e;k++) {scanf("%d,%d",&i,&j); /*输入e条边*/G->adj[i][j]=1;G->adj[j][i]=1; /*对称加入,无向图的邻接矩阵存储建立*/ }}/*CreateMGraph*/void CreateALGraph(ALGraph *G){ /*建立无向图的邻接表存储*/int i,j,k;char vi;EdgeNode *s;printf("请输入顶点数和边数:\n");scanf("%d,%d",&(G->n),&(G->e));printf("请输入顶点信息Vi\n例如a，每输入一个顶点后回车:\n");for (i=0;i<G->n;i++) {scanf("%s",&vi);G->adjlist[i].vertex=vi;G->adjlist[i].firstedge=NULL;}printf("顶点:");for (i=0;i<G->n;i++)printf("%c(%d)-",G->adjlist[i].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(EdgeNode));s->adjvex=j-1;s->nextarc=G->adjlist[i-1].firstedge;G->adjlist[i-1].firstedge=s;s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=i-1;s->nextarc=G->adjlist[j-1].firstedge;G->adjlist[j-1].firstedge=s;}////输出邻接表...}/*CreateALGraph*/void DFS(ALGraph *G, int v) {EdgeNode *p ;Visited[v]=TRUE ;printf("%c->",G->adjlist[v].vertex); /* 置访问标志，访问顶点v */p=G->adjlist[v].firstedge; /* 链表的第一个结点 */while (p!=NULL){if(!Visited[p->adjvex])DFS(G, p->adjvex);/* 从v的未访问过的邻接顶点出发深度优先搜索 */p=p->nextarc ;}}void DFS_traverse (ALGraph *G){int v ;EdgeNode *p ;printf("深度度优先搜索输出结点信息:");for (v=0; v<G->n; v++) Visited[v]=FALSE ; /* 访问标志初始化 */ p=G->adjlist[v].firstedge ;for (v=0; v<G->n; v++)if (!Visited[v]) DFS(G,v);}///////////////队列 ///////////////////////typedef struct Node{ElemType data; // 元素数据struct Node *next; // 链式队列中结点元素的指针} QNode, *QueuePtr;typedef struct{QueuePtr front; // 队列头指针QueuePtr rear; // 队列尾指针} LinkQueue;Status InitQueue(LinkQueue &Q) {//构造一个空队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if(Q.front == NULL) exit(OVERFLOW); //存储失败Q.front ->next = NULL;return OK;}Status DestoryQueue(LinkQueue &Q) {//销毁队列Qwhile(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;elsereturn 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.adjlist[v].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;v<G.n;++v) visited[v]=FALSE;// 初始化访问标志InitQueue(Q); //置空的辅助队列for(v=0;v<G.n;++v)if(!visited[v]){ //v 未访问visited[v]=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(!visited[w]){ //w为u尚未访问的邻接顶点 visited[w]=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');}。