




已閱讀5頁(yè),還剩1頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
#include#include#define MAX_VERTEX_NUM 20#define MAX 32767#define ERROR 0#define OK 1#define OVERFLOW -2typedef int Status;typedef char VertexType;typedef int PathMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM;typedef int ShortPathTable MAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;bool finalMAX_VERTEX_NUM;typedef struct char adj; int lowcost;closedgeMAX_VERTEX_NUM;typedef struct ArcNodeint adjvex;/弧所指向的頂點(diǎn)的位置struct ArcNode *nextarc;/指向下一條弧的指針int weight;/權(quán)重/InfoType *info;/該弧相關(guān)信息的指針ArcNode;typedef struct VNodeVertexType data;/頂點(diǎn)信息ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;int kind;ALGraph;/-/隊(duì)列typedef struct nodeint data;struct node *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;/構(gòu)造一個(gè)空隊(duì)列Status InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK;/插入元素Status EnQueue(LinkQueue &Q,int &e)QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;/出隊(duì)列Status DeQueue(LinkQueue &Q,int &e)QueuePtr p;if(Q.front=Q.rear)return ERROR; p=Q.front-next; e=p-data; Q.front-next =p-next; if(p=Q.rear)Q.rear=Q.front; free(p); return OK;Status QueueEmpty(LinkQueue &Q)if(Q.front=Q.rear) return OK; else return ERROR;/*-*/int LocateVex(ALGraph G,char e) int i;for(i=0;iG.vexnum;i+)if(e=G.verticesi.data) return i;return -1;/創(chuàng)建圖int CreateGraph(ALGraph &G)int i,j,w,k;char V1,V2;printf(輸入頂點(diǎn)數(shù),弧數(shù):);scanf(%d%d,&G.vexnum,&G.arcnum);for(i=0;iG.vexnum;i+) printf(輸入第%d個(gè)頂點(diǎn)的值:,i+1); scanf(n%c,&G.verticesi.data); fflush(stdin);G.verticesi.firstarc=NULL;ArcNode* p;for(i=0;iadjvex=k; p-weight=w; p-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=p;return OK;/鄰接表表示的深度優(yōu)先搜索算法 void DFS(ALGraph G,int v)int j;ArcNode* q;visitedv=OK;printf(%c ,G.verticesv.data ); q=G.verticesv.firstarc;for(;q;q=q-nextarc)j=q-adjvex;if(!visitedj) DFS(G,j); /鄰接表表示的廣度優(yōu)先搜索算法 void BFS(ALGraph G,int v)int i,u;ArcNode* q;for(i=0;iMAX_VERTEX_NUM;i+) visitedi=ERROR; LinkQueue Q;InitQueue(Q);for(i=v;inextarc) if(!visitedu) EnQueue(Q,u);int minium(closedge a,ALGraph G)int i=0,j,k,min; while(!ai.lowcost) i+; min=ai.lowcost; / 第一個(gè)不為0的值 k=i; for(j=i+1;j0) if(minaj.lowcost) min=aj.lowcost; k=j; return k;void MiniSpanTree_PRIM(ALGraph &G,char u) int k,j,i;ArcNode* q; closedge a; for(j=0;jadjvex.adj=G.verticesk.data; aq-adjvex.lowcost=q-weight ; q=q-nextarc;ak.lowcost=0; printf(n最小代價(jià)生成樹的各條邊為:n);for(i=1;iweightadjvex.lowcost) aq-adjvex.adj=G.verticesk.data; aq-adjvex.lowcost=q-weight ; q=q-nextarc; /void ShortestPath_DIJ(ALGraph &G1,int v0,PathMatrix &p,ShortPathTable &D)int v,i,min,w,j;ArcNode* q; q=G1.verticesv0.firstarc; for(v=0;vG1.vexnum;v+)finalv=false; Dv=MAX;for(w=0;wadjvex=q-weight; pq-adjvexv0=true; pq-adjvexq-adjvex=true; q=q-nextarc; Dv0=0; finalv0=true; for(i=1;iG1.vexnum;i+)min=MAX;for(w=0;wG1.vexnum;w+) if(!finalw)if(Dwadjvex&min+q-weightadjvex) Dq-adjvex=min+q-weight; for(j=0;jadjvexj=pvj;pq-adjvexq-adjvex=true; q=q-nextarc; void main() int i,start,start1,j;char c;PathMatrix p; ShortPathTable d;for(i=0;iMAX_VERTEX_NUM;i+)visitedi=ERROR;ALGraph G;CreateGraph(G);printf(深度優(yōu)先遍歷開始位置:);scanf(%d,&start);DFS(G,start);printf(n廣度優(yōu)先遍歷開始元素:); scanf(%d,&start1);BFS( G,start1); printf(nprim算法開始元素:);scanf(n%c,&c);MiniSpanTree_PRIM(G, c );ShortestPath_DIJ(G,0,p,d);for(i=0;iG.vexn
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年產(chǎn)品售后服務(wù)策劃合作協(xié)議書標(biāo)準(zhǔn)格式
- 2025年租約提前解除協(xié)議示例
- 2025年商品混凝土運(yùn)輸合作協(xié)議模板
- 2025年企業(yè)員工傷亡賠償策劃諒解協(xié)議指南
- 2025年項(xiàng)目策劃方與投資協(xié)議草案
- 雙元制教育模式在產(chǎn)教共融中的應(yīng)用
- 產(chǎn)教深度融合對(duì)人才培養(yǎng)模式的影響
- 精準(zhǔn)農(nóng)業(yè)技術(shù)提升油菜種植效益
- 構(gòu)建語(yǔ)文教學(xué)新形態(tài)的面臨的問(wèn)題、機(jī)遇與挑戰(zhàn)
- 社交媒體時(shí)代出版行業(yè)的用戶體驗(yàn)升級(jí)
- 東南大學(xué)強(qiáng)基試題及答案
- 復(fù)雜應(yīng)用的C語(yǔ)言設(shè)計(jì)考題及答案
- 中華護(hù)理學(xué)會(huì)團(tuán)體標(biāo)準(zhǔn)|2024 針刺傷預(yù)防與處理課件
- 國(guó)家開放大學(xué)國(guó)開電大《健康管理實(shí)務(wù)》形考及期末終考題庫(kù)
- 2025安全生產(chǎn)月全員安全主題宣講課件二十六(41ye)
- 浙江省杭州市保俶塔中學(xué)2025屆八下數(shù)學(xué)期末經(jīng)典試題含解析
- 礦產(chǎn)勘查野外地質(zhì)調(diào)查安全操作考核試卷
- 2025水利工程總承包合同
- 2025-2030年中國(guó)數(shù)字金融行業(yè)市場(chǎng)深度調(diào)研及競(jìng)爭(zhēng)格局與前景預(yù)測(cè)研究報(bào)告
- 2025入團(tuán)積極分子發(fā)展對(duì)象考試題庫(kù)及答案詳解(必刷)
- 2025河南省農(nóng)業(yè)信貸擔(dān)保有限責(zé)任公司招聘32人筆試參考題庫(kù)附帶答案詳解
評(píng)論
0/150
提交評(píng)論