數(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; /最大頂點數(shù)最大頂點數(shù)typedef char VertexType; /頂點數(shù)據(jù)類型頂點數(shù)據(jù)類型typedef int ArcType; /邊邊(弧弧)數(shù)據(jù)類型數(shù)據(jù)類型typedef struct VertexType vexs MaxVex; /頂點數(shù)組頂點數(shù)組 ArcType arcs MaxVex MaxVex; /

4、鄰接矩陣鄰接矩陣 int vexnum, /頂點個數(shù)頂點個數(shù) arcnum; /邊條數(shù)邊條數(shù) MGraph ;2021-10-31鄰接矩陣的建立算法鄰接矩陣的建立算法 void CreateMGraph ( MGraph *G ) / 1. 輸入頂點個數(shù)輸入頂點個數(shù) vexnum、邊條數(shù)、邊條數(shù) arcnum / 2. 輸入頂點數(shù)據(jù)，建立頂點數(shù)組輸入頂點數(shù)據(jù)，建立頂點數(shù)組 / 3. 初始化鄰接矩陣初始化鄰接矩陣 / 4. 輸入邊的頂點序號輸入邊的頂點序號 i、j，建立鄰接陣，建立鄰接陣 /arcsij=1 /arcsji=1 /無向圖無向圖 /end CreateMGraph2021-10-3

5、1鄰接矩陣建立算法鄰接矩陣建立算法void CreateMGraph ( MGraph *G) int i, j, k, w;char ch; printf (“輸入頂點數(shù)輸入頂點數(shù), 邊數(shù)：邊數(shù)：n); scanf (%d, %d, &(G-vexnum), &(G-arcnum) );/待續(xù)待續(xù) /end CreateMGraph2021-10-31鄰接矩陣建立算法鄰接矩陣建立算法void CreateMGraph ( MGraph *G) /續(xù)續(xù) printf(“輸入頂點數(shù)據(jù)：輸入頂點數(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(“輸入邊對應頂點序號輸入邊對應頂點序號(格式：格式：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 頂點數(shù)組：存儲頂點數(shù)據(jù)；掛接頂點數(shù)組：存儲頂點數(shù)據(jù)；掛接鄰接鏈表鄰接鏈表 datafirstarc#define MAX_VERTEX_NUM 20 /允許的最大頂點個數(shù)允許的最大頂點個數(shù)typedef struct /頂點結(jié)點頂點結(jié)點 VertexType data; /頂點頂點數(shù)據(jù)數(shù)據(jù) ArcNode *firstarc; /鄰接表首結(jié)點指針鄰接表首結(jié)點指針 VNode, AdjList MAX_VERTEX_NUM ;2021-10-31

9、v 鄰接表(Adjacency List)v 鄰接鄰接(鏈鏈)表：每個頂點掛接表：每個頂點掛接 1 個單鏈表個單鏈表typedef struct /加權(quán)圖加權(quán)圖的鄰接表結(jié)點的鄰接表結(jié)點 int adjvex; /鄰接點鄰接點的頂點的頂點數(shù)組數(shù)組下標下標 ArcType info ; /邊權(quán)值邊權(quán)值 (網(wǎng)網(wǎng)) struct ArcNode *nextarc; /指向指向下一下一鄰接點的指針鄰接點的指針 ArcNode ;adjvexnextarcinfo datafirstarc2021-10-31v 鄰接表(Adjacency List)v 鄰接鄰接(鏈鏈)表：每個頂點掛接表：每個頂點掛接 1

10、 個單鏈表個單鏈表typedef struct /無權(quán)圖無權(quán)圖的鄰接表結(jié)點的鄰接表結(jié)點 int adjvex; /鄰接點鄰接點的頂點的頂點數(shù)組數(shù)組下標下標 struct ArcNode *nextarc; /指向指向下一下一鄰接點的指針鄰接點的指針 ArcNode ;adjvex nextarc datafirstarc 2021-10-31v 鄰接表(Adjacency List)v 鄰接表表示的圖鄰接表表示的圖typedef struct /圖圖 AdjList vertices; /(掛接了鏈表的掛接了鏈表的)頂點數(shù)組頂點數(shù)組 int vexnum, arcnum; /頂點個數(shù)，邊條數(shù)頂

11、點個數(shù)，邊條數(shù) ALGraph ;2021-10-31 void CreateALGraph(ALGraph *G) / 建立鄰接表建立鄰接表 / 1. 輸入頂點數(shù)輸入頂點數(shù) vexnum 和邊數(shù)和邊數(shù) arcnum / 2. 輸入頂點信息，建立有輸入頂點信息，建立有 n 個頂點的頂點表個頂點的頂點表 / 2.1 讀入頂點信息讀入頂點信息 / 2.2 頂點的邊表頭指針設為空頂點的邊表頭指針設為空 / 3. 輸入邊頂點對應序號輸入邊頂點對應序號 i, j ，建立邊鏈表，建立邊鏈表 / 3.1 生成新的邊鏈表結(jié)點生成新的邊鏈表結(jié)點 s / 3.2 鄰接點序號鄰接點序號 j / 3.3 新的邊表結(jié)點

12、新的邊表結(jié)點 s 頭插法頭插法，插入頂點，插入頂點 Vi 的邊表的邊表2021-10-31void CreateALGraph(ALGraph *G) / 建立有向圖鄰接表建立有向圖鄰接表int i, j, k; ArcNode * s; printf(輸入頂點數(shù)和邊數(shù)輸入頂點數(shù)和邊數(shù)(輸入格式為輸入格式為:頂點數(shù)頂點數(shù),邊數(shù)邊數(shù))：n); scanf(“%d,%d, &(G-vexnum), &(G-arcnum) );/頂點數(shù)組頂點數(shù)組printf(“輸入頂點編號輸入頂點編號(一個頂點占一行一個頂點占一行)：n);for ( i=0; ivexnum; i+ ) scanf (n%d, &(G-vertices i.data) ); G-vertices i.firstarc = NULL; /鏈表頭指針初始為空鏈表頭指針初始為空2021-10-31 printf(“請輸入邊信息請輸入邊信息(輸入格式為輸入格式為:i, j 回車回車)：n); /建立邊表建立邊表 for (k=0; karcnum; k+ ) sc