




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、王玲V1V2V3V4V5V1V2V3V4FECBADABCDEFV1V2V3V4V5FECBADABCDEFV1V2V3V4V5V1V2V3V1V2V3V4V1V2V3V1V2V3V4V1V2V3V4V5V1V2V3V4evODvIDiiii= = = = = =11)()(nnV1V2V3V42785V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5256328V1V2V3V4V5V1V2V3V4V1V2V3V4V5V1V2V3V4V5V1V3V4V1V2V3V4V5V6V7V1V2V4V5V3V6V7V1V2V3V4V1V3V4V2如何理解極小連通子圖如何理解極小連通子圖?V1V
2、2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5arcsV1V3V4V2arcsV1V3V4V2V1 V2 V3 V4vexs=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arcs=V1 V2 V3 V4V1V2V3V4V1V3V4V2V1 V2 V3 V4vexs=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arcs=V1 V2 V3 V4V1V2V3V4V1V3V4V2arcsV1V2V3V4arcsV1V2V3V4arcsV1V2V3V40 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc
3、s=V1V2V3V4arcsarcsij wij 若若(vi, vj)E(或(或E)0 若若i=j 其他其他V1V2V3V42785 0 2 5 0 0 8 7 0 arcs=2021-10-31/鄰接陣類型聲明鄰接陣類型聲明const int MaxVex = 100; /最大頂點(diǎn)數(shù)最大頂點(diǎn)數(shù)typedef char VertexType; /頂點(diǎn)數(shù)據(jù)類型頂點(diǎn)數(shù)據(jù)類型typedef int ArcType; /邊邊(弧弧)數(shù)據(jù)類型數(shù)據(jù)類型typedef struct VertexType vexs MaxVex; /頂點(diǎn)數(shù)組頂點(diǎn)數(shù)組 ArcType arcs MaxVex MaxVex; /
4、鄰接矩陣鄰接矩陣 int vexnum, /頂點(diǎn)個(gè)數(shù)頂點(diǎn)個(gè)數(shù) arcnum; /邊條數(shù)邊條數(shù) MGraph ;2021-10-31鄰接矩陣的建立算法鄰接矩陣的建立算法 void CreateMGraph ( MGraph *G ) / 1. 輸入頂點(diǎn)個(gè)數(shù)輸入頂點(diǎn)個(gè)數(shù) vexnum、邊條數(shù)、邊條數(shù) arcnum / 2. 輸入頂點(diǎn)數(shù)據(jù),建立頂點(diǎn)數(shù)組輸入頂點(diǎn)數(shù)據(jù),建立頂點(diǎn)數(shù)組 / 3. 初始化鄰接矩陣初始化鄰接矩陣 / 4. 輸入邊的頂點(diǎn)序號(hào)輸入邊的頂點(diǎn)序號(hào) i、j,建立鄰接陣,建立鄰接陣 /arcsij=1 /arcsji=1 /無向圖無向圖 /end CreateMGraph2021-10-3
5、1鄰接矩陣建立算法鄰接矩陣建立算法void CreateMGraph ( MGraph *G) int i, j, k, w;char ch; printf (“輸入頂點(diǎn)數(shù)輸入頂點(diǎn)數(shù), 邊數(shù):邊數(shù):n); scanf (%d, %d, &(G-vexnum), &(G-arcnum) );/待續(xù)待續(xù) /end CreateMGraph2021-10-31鄰接矩陣建立算法鄰接矩陣建立算法void CreateMGraph ( MGraph *G) /續(xù)續(xù) printf(“輸入頂點(diǎn)數(shù)據(jù):輸入頂點(diǎn)數(shù)據(jù):n); for ( i=0; i vexnum; i+) scanf (n%c,
6、&(G-vexsi) );/待續(xù)待續(xù)/ end CreateMGraph2021-10-31鄰接矩陣建立算法鄰接矩陣建立算法void CreateMGraph ( MGraph *G) /續(xù)續(xù) /初始化鄰接陣初始化鄰接陣 for (i=0; ivexnum; i+) for (j=0; jvexnum; j+) G-arcs ij =0;/待續(xù)待續(xù) / end CreateMGraph2021-10-31鄰接矩陣建立算法鄰接矩陣建立算法void CreateMGraph ( MGraph *G) /續(xù)續(xù) printf(“輸入邊對(duì)應(yīng)頂點(diǎn)序號(hào)輸入邊對(duì)應(yīng)頂點(diǎn)序號(hào)(格式:格式:i,j):n);
7、 for (k=0;karcnum;k+) scanf(n%d,%d,&i, &j); G-arcsij=1; /G-arcsji=1; /無向圖無向圖 /end CreateMGraph10323101 V1 V2 V3 V40123V1V3V4V2V1V3V4V210323101 V1 V2 V3 V40123V1V3V4V210323101 V1 V2 V3 V40123V1V2V3V41230 V1 V2 V3 V40123V1V2V3V41230 V1 V2 V3 V40123V1V2V3V427852 1 V1 V2 V3 V401235 28 37 0V1V2V3
8、V412 3 0v1v2v3v401231 3 0 2 v1v2v3v4012303 2021-10-31v 鄰接表(Adjacency List)v 頂點(diǎn)數(shù)組:存儲(chǔ)頂點(diǎn)數(shù)據(jù);掛接頂點(diǎn)數(shù)組:存儲(chǔ)頂點(diǎn)數(shù)據(jù);掛接鄰接鏈表鄰接鏈表 datafirstarc#define MAX_VERTEX_NUM 20 /允許的最大頂點(diǎn)個(gè)數(shù)允許的最大頂點(diǎn)個(gè)數(shù)typedef struct /頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn) VertexType data; /頂點(diǎn)頂點(diǎn)數(shù)據(jù)數(shù)據(jù) ArcNode *firstarc; /鄰接表首結(jié)點(diǎn)指針鄰接表首結(jié)點(diǎn)指針 VNode, AdjList MAX_VERTEX_NUM ;2021-10-31
9、v 鄰接表(Adjacency List)v 鄰接鄰接(鏈鏈)表:每個(gè)頂點(diǎn)掛接表:每個(gè)頂點(diǎn)掛接 1 個(gè)單鏈表個(gè)單鏈表typedef struct /加權(quán)圖加權(quán)圖的鄰接表結(jié)點(diǎn)的鄰接表結(jié)點(diǎn) int adjvex; /鄰接點(diǎn)鄰接點(diǎn)的頂點(diǎn)的頂點(diǎn)數(shù)組數(shù)組下標(biāo)下標(biāo) ArcType info ; /邊權(quán)值邊權(quán)值 (網(wǎng)網(wǎng)) struct ArcNode *nextarc; /指向指向下一下一鄰接點(diǎn)的指針鄰接點(diǎn)的指針 ArcNode ;adjvexnextarcinfo datafirstarc2021-10-31v 鄰接表(Adjacency List)v 鄰接鄰接(鏈鏈)表:每個(gè)頂點(diǎn)掛接表:每個(gè)頂點(diǎn)掛接 1
10、 個(gè)單鏈表個(gè)單鏈表typedef struct /無權(quán)圖無權(quán)圖的鄰接表結(jié)點(diǎn)的鄰接表結(jié)點(diǎn) int adjvex; /鄰接點(diǎn)鄰接點(diǎn)的頂點(diǎn)的頂點(diǎn)數(shù)組數(shù)組下標(biāo)下標(biāo) struct ArcNode *nextarc; /指向指向下一下一鄰接點(diǎn)的指針鄰接點(diǎn)的指針 ArcNode ;adjvex nextarc datafirstarc 2021-10-31v 鄰接表(Adjacency List)v 鄰接表表示的圖鄰接表表示的圖typedef struct /圖圖 AdjList vertices; /(掛接了鏈表的掛接了鏈表的)頂點(diǎn)數(shù)組頂點(diǎn)數(shù)組 int vexnum, arcnum; /頂點(diǎn)個(gè)數(shù),邊條數(shù)頂
11、點(diǎn)個(gè)數(shù),邊條數(shù) ALGraph ;2021-10-31 void CreateALGraph(ALGraph *G) / 建立鄰接表建立鄰接表 / 1. 輸入頂點(diǎn)數(shù)輸入頂點(diǎn)數(shù) vexnum 和邊數(shù)和邊數(shù) arcnum / 2. 輸入頂點(diǎn)信息,建立有輸入頂點(diǎn)信息,建立有 n 個(gè)頂點(diǎn)的頂點(diǎn)表個(gè)頂點(diǎn)的頂點(diǎn)表 / 2.1 讀入頂點(diǎn)信息讀入頂點(diǎn)信息 / 2.2 頂點(diǎn)的邊表頭指針設(shè)為空頂點(diǎn)的邊表頭指針設(shè)為空 / 3. 輸入邊頂點(diǎn)對(duì)應(yīng)序號(hào)輸入邊頂點(diǎn)對(duì)應(yīng)序號(hào) i, j ,建立邊鏈表,建立邊鏈表 / 3.1 生成新的邊鏈表結(jié)點(diǎn)生成新的邊鏈表結(jié)點(diǎn) s / 3.2 鄰接點(diǎn)序號(hào)鄰接點(diǎn)序號(hào) j / 3.3 新的邊表結(jié)點(diǎn)
12、新的邊表結(jié)點(diǎn) s 頭插法頭插法,插入頂點(diǎn),插入頂點(diǎn) Vi 的邊表的邊表2021-10-31void CreateALGraph(ALGraph *G) / 建立有向圖鄰接表建立有向圖鄰接表int i, j, k; ArcNode * s; printf(輸入頂點(diǎn)數(shù)和邊數(shù)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為輸入格式為:頂點(diǎn)數(shù)頂點(diǎn)數(shù),邊數(shù)邊數(shù)):n); scanf(“%d,%d, &(G-vexnum), &(G-arcnum) );/頂點(diǎn)數(shù)組頂點(diǎn)數(shù)組printf(“輸入頂點(diǎn)編號(hào)輸入頂點(diǎn)編號(hào)(一個(gè)頂點(diǎn)占一行一個(gè)頂點(diǎn)占一行):n);for ( i=0; ivexnum; i+ ) scanf (n%d, &(G-vertices i.data) ); G-vertices i.firstarc = NULL; /鏈表頭指針初始為空鏈表頭指針初始為空2021-10-31 printf(“請(qǐng)輸入邊信息請(qǐng)輸入邊信息(輸入格式為輸入格式為:i, j 回車回車):n); /建立邊表建立邊表 for (k=0; karcnum; k+ ) sc
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 茶葉品牌授權(quán)與加盟合作合同
- 城市綠線測(cè)繪與城市管理合同范本
- 鏟車銷售與租賃、維修、保養(yǎng)、培訓(xùn)合同范本
- 網(wǎng)絡(luò)安全領(lǐng)域公司成立出資協(xié)議書
- 成都市房產(chǎn)中介服務(wù)與二手房交易合同
- 被迫解除勞動(dòng)合同關(guān)系通知書
- 中職學(xué)校書法活動(dòng)方案
- 學(xué)校學(xué)生浴室管理制度
- 衛(wèi)生衛(wèi)生制度管理制度
- 單位文件傳閱管理制度
- 辦理公司車輛違章委托書模板
- 靜脈治療小組開展工作匯報(bào)
- (優(yōu)化版)高中地理新課程標(biāo)準(zhǔn)【2024年修訂版】
- DB34T1268-2024油茶營造林技術(shù)規(guī)程
- 2024年三角形教學(xué)新思路:跨學(xué)科整合
- 國家電網(wǎng)公司招聘高校畢業(yè)生應(yīng)聘登記表
- 采購合同(標(biāo)準(zhǔn)模板)
- 2024年重慶市中考化學(xué)試題(A卷)含答案
- 全國數(shù)據(jù)應(yīng)用大賽“數(shù)字安全賽”備賽試題及答案
- 部編版 高中語文 選擇性必修下 第四單元 自然選擇的證明練習(xí)題及答案
- 2024年醫(yī)學(xué)高級(jí)職稱-心血管內(nèi)科(醫(yī)學(xué)高級(jí))考試近5年真題集錦(頻考類試題)帶答案
評(píng)論
0/150
提交評(píng)論