建立圖的鄰接矩陣或鄰接表存儲并在此基礎(chǔ)上實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷

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 /* 最大值 */ /* 根據(jù)圖的權(quán)值類型，分別定義為最大整數(shù)或?qū)崝?shù) */#define MAX_VERTEX_NUM 20 /* 最大頂點數(shù)目 */typedef

2、 enum DG, DN, UDG,UDN GraphKind ; /* 有向圖，有向網(wǎng)，無向圖，無向網(wǎng) */BOOLEAN VisitedMAX_VERTEX_NUM;BOOLEAN visitedMAX_VERTEX_NUM;#define VEX_NUM 20#define MAXSIZE 50typedef char Vextype;typedef int ElemType;typedef int Status; / 鄰接矩陣結(jié)構(gòu)定義typedef struct Vextype vexsVEX_NUM; int adjVEX_NUMVEX_NUM; /*鄰接矩陣*/ int n,e;

3、/*頂點數(shù)和邊數(shù)*/ Mgraph; / 鄰接表結(jié)構(gòu)定義typedef struct node /*邊結(jié)點*/int adjvex; /*鄰接點域*/struct node * nextarc; /*指向下一個邊結(jié)點的指針域*/ EdgeNode; typedef struct vnode /頂點結(jié)構(gòu)，2個域，結(jié)點信息和第一個鄰接點Vextype vertex; EdgeNode *firstedge; VertexNode; typedef struct /圖結(jié)構(gòu)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("請輸入頂點數(shù)和邊數(shù):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("輸入每條邊對應(yīng)的兩個頂點的序號: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("請輸入頂點數(shù)和邊數(shù):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); /在頭結(jié)點和邊結(jié)點之間插入新的邊結(jié)點 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); /* 置訪問標(biāo)志，訪問頂點v */ p=G->adjlistv.firstedge; /* 鏈表的第一個結(jié)點 */ while (p!=NULL) if(!Visitedp->adjvex) DFS(G, p->adjvex);/* 從v的未訪問過的鄰接頂點出發(fā)深度優(yōu)先搜索 */ p=p->nextarc ; void DFS_traverse (ALGraph *G) int v ; EdgeNode *p ; printf("深度度優(yōu)先搜索輸出結(jié)點信

11、息:");for (v=0; v<G->n; v+) Visitedv=FALSE ; /* 訪問標(biāo)志初始化 */ p=G->adjlistv.firstedge ; for (v=0; v<G->n; v+) if (!Visitedv) DFS(G,v);/隊列 /typedef struct Node ElemType data; / 元素數(shù)據(jù) struct Node *next; / 鏈?zhǔn)疥犃兄薪Y(jié)點元素的指針 QNode, *QueuePtr; typedef struct QueuePtr front; / 隊列頭指針 QueuePtr rea

12、r; / 隊列尾指針 LinkQueue; Status InitQueue(LinkQueue &Q) /構(gòu)造一個空隊列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); /依次釋放頭結(jié)點 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; /當(dāng)前隊尾指針指向新的結(jié)點 Q.rear = p; /移動隊尾知道到新的結(jié)點，當(dāng)前結(jié)點成為隊尾結(jié)點 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; /只有一個元素，恢復(fù)到空隊列，只有各頭結(jié)點 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 廣度優(yōu)先搜

16、索 LinkQueue Q;ElemType u;/ EdgeNode *p;int v;int w;printf("廣度優(yōu)先搜索輸出結(jié)點信息:");for(v=0;v<G.n;+v) visitedv=FALSE;/ 初始化訪問標(biāo)志 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