數(shù)據(jù)結(jié)構(gòu)第七章圖

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