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

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 /* 最大頂點(diǎn)數(shù)目 */typed

2、ef enum DG, DN, UDG,UDN GraphKind ; /* 有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(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、; /*頂點(diǎn)數(shù)和邊數(shù)*/ Mgraph; / 鄰接表結(jié)構(gòu)定義typedef struct node /*邊結(jié)點(diǎn)*/int adjvex; /*鄰接點(diǎn)域*/struct node * nextarc; /*指向下一個(gè)邊結(jié)點(diǎn)的指針域*/ EdgeNode; typedef struct vnode /頂點(diǎn)結(jié)構(gòu)，2個(gè)域，結(jié)點(diǎn)信息和第一個(gè)鄰接點(diǎn)Vextype vertex; EdgeNode *firstedge; VertexNode; typedef struct /圖結(jié)構(gòu)VertexNode adjlistMAXSIZE;int n,e; ALGraph; /int FirstAdjVex(AL

4、Graph G,int v) /在圖G中尋找第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn) if(!G.adjlistv.firstedge) return -1; else return(G.adjlistv.firstedge->adjvex); int NextAdjVex(ALGraph G,int v,int w) /在圖G中尋找第v個(gè)頂點(diǎn)的相對(duì)于w的下一個(gè)鄰接頂點(diǎn) EdgeNode *p;int vi; p=G.adjlistv.firstedge; if(!p) return -1; while(p->adjvex!=w) p=p->nextarc; /在頂點(diǎn)v的弧鏈中找到頂點(diǎn)w

5、p=p->nextarc;if(!p) return -1; /若已是最后一個(gè)頂點(diǎn)，返回-1else vi=p->adjvex;return vi; /返回下一個(gè)鄰接頂點(diǎn)的序號(hào) /void CreateMGraph(Mgraph *G) int i,j,k; / char ch; printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):n"); scanf("%d,%d",&(G->n),&(G->e); /*輸入*/ printf("請(qǐng)輸入頂點(diǎn)信息:n"); for (i=0;i<G->n;i+) s

6、canf("%s",&(G->vexsi); for (i=0;i<G->n;i+) for (j=0;j<G->n;j+) G->adjij=0; /*初始化鄰接矩陣*/ printf("輸入每條邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)的序號(hào):n"); for (k=0;k<G->e;k+) scanf("%d,%d",&i,&j); /*輸入e條邊*/G->adjij=1; G->adjji=1; /*對(duì)稱加入,無(wú)向圖的鄰接矩陣存儲(chǔ)建立*/ /*CreateMGraph*

7、/ void CreateALGraph(ALGraph *G) /*建立無(wú)向圖的鄰接表存儲(chǔ)*/int i,j,k;char vi;EdgeNode *s; printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):n");scanf("%d,%d",&(G->n),&(G->e); printf("請(qǐng)輸入頂點(diǎn)信息Vin例如a，每輸入一個(gè)頂點(diǎn)后回車:n"); for (i=0;i<G->n;i+) scanf("%s",&vi); G->adjlisti.vertex=vi;G-&g

8、t;adjlisti.firstedge=NULL; printf("頂點(diǎn):");for (i=0;i<G->n;i+) printf("%c(%d)-",G->adjlisti.vertex,i+1); printf("n請(qǐng)輸入邊的信息(vi,vj)n例如:1,2:n");for (k=0;k<G->e;k+) /*建立邊表*/scanf("%d,%d",&i,&j); /在頭結(jié)點(diǎn)和邊結(jié)點(diǎn)之間插入新的邊結(jié)點(diǎn) s=(EdgeNode*)malloc(sizeof(Edg

9、eNode); 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=TR

10、UE ; printf("%c->",G->adjlistv.vertex); /* 置訪問標(biāo)志，訪問頂點(diǎn)v */ p=G->adjlistv.firstedge; /* 鏈表的第一個(gè)結(jié)點(diǎn) */ while (p!=NULL) if(!Visitedp->adjvex) DFS(G, p->adjvex);/* 從v的未訪問過的鄰接頂點(diǎn)出發(fā)深度優(yōu)先搜索 */ p=p->nextarc ; void DFS_traverse (ALGraph *G) int v ; EdgeNode *p ; printf("深度度優(yōu)先搜索輸出結(jié)

11、點(diǎn)信息:");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);/隊(duì)列 /typedef struct Node ElemType data; / 元素?cái)?shù)據(jù) struct Node *next; / 鏈?zhǔn)疥?duì)列中結(jié)點(diǎn)元素的指針 QNode, *QueuePtr; typedef struct QueuePtr front; / 隊(duì)列頭指針 QueuePtr r

12、ear; / 隊(duì)列尾指針 LinkQueue; Status InitQueue(LinkQueue &Q) /構(gòu)造一個(gè)空隊(duì)列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if(Q.front = NULL) exit(OVERFLOW); /存儲(chǔ)失敗 Q.front ->next = NULL; return OK; Status DestoryQueue(LinkQueue &Q) /銷毀隊(duì)列Q while(Q.front)Q.rear = Q.front->next; /利用尾指針移動(dòng)保存隊(duì)頭指針fr

13、ee(Q.front); /依次釋放頭結(jié)點(diǎn) 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新的隊(duì)尾元素 QueuePtr p = (QueuePtr )malloc(sizeof(QNode); if(!p) e

14、xit(OVERFLOW); /存儲(chǔ)失敗 p ->data = e; p ->next = NULL; Q.rear ->next = p; /當(dāng)前隊(duì)尾指針指向新的結(jié)點(diǎn) Q.rear = p; /移動(dòng)隊(duì)尾知道到新的結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)成為隊(duì)尾結(jié)點(diǎn) return OK; Status DeQueue(LinkQueue &Q, ElemType *e) /若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回值，并返回OK。否則返回ERROR if(Q.front = Q.rear) return ERROR; QueuePtr p = Q.front ->next; *e = p

15、->data; Q.front ->next= p ->next; if(Q.rear = p) Q.rear = Q.front; /只有一個(gè)元素，恢復(fù)到空隊(duì)列，只有各頭結(jié)點(diǎn) 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é)點(diǎn)信息:");for(v=0;v<G.n;+v) visitedv=FALSE;/ 初始化訪問標(biāo)志 InitQueue(Q); /置空的輔助隊(duì)列 for(v=0;v<G.n;+v) if(!visitedv) /v 未訪問 visitedv=TRUE; Visit(v,G); EnQueue(Q,v);/v 入隊(duì)列 while(!QueueEmpty(Q) DeQueue(Q,&u); /隊(duì)頭元素出隊(duì)并置為 u for(w=FirstAdjVex(G,u);w>=0; w=NextAdjVex(G,u,w) if(!visitedw) /w為u尚未訪問的鄰接頂點(diǎn) visitedw=TRUE; Visit(w,G); EnQueue(Q,w);/訪問的頂點(diǎn) w入隊(duì)列/i