隨著計(jì)算機(jī)科學(xué)和技術(shù)的發(fā)展，數(shù)據(jù)結(jié)構(gòu)已經(jīng)成為了大學(xué)中相當(dāng)重要的一門學(xué)科。其中“圖”是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)重要概念，本文將會(huì)介紹圖的各種關(guān)鍵名詞和算法。一、圖的基本概念圖（Graph）是一種非線性數(shù)據(jù)結(jié)構(gòu)，

隨著計(jì)算機(jī)科學(xué)和技術(shù)的發(fā)展，數(shù)據(jù)結(jié)構(gòu)已經(jīng)成為了大學(xué)中相當(dāng)重要的一門學(xué)科。其中“圖”是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)重要概念，本文將會(huì)介紹圖的各種關(guān)鍵名詞和算法。

一、圖的基本概念

圖（Graph）是一種非線性數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)（Vertex）和邊（Edge）組成。在圖中，節(jié)點(diǎn)之間可以通過邊連接起來，形成任意復(fù)雜的結(jié)構(gòu)。

圖G(V,E)是由頂點(diǎn)集V和邊集E組成的。如果邊是有方向的，則稱該圖為有向圖（DiGraph）；反之，則稱該圖為無向圖（UnDiGraph）。兩個(gè)相鄰的結(jié)點(diǎn)稱為鄰結(jié)點(diǎn)（Adjacent Vertex），起始節(jié)點(diǎn)稱為始點(diǎn)（Start Vertex），結(jié)束節(jié)點(diǎn)稱為終點(diǎn)（End Vertex），從一個(gè)節(jié)點(diǎn)出發(fā)到達(dá)另外一個(gè)節(jié)點(diǎn)的邊稱為出邊（Outgoing Edge），指向該節(jié)點(diǎn)的邊稱為入邊（Incoming Edge）。一個(gè)節(jié)點(diǎn)的度數(shù)（Degree），包括出度（Out Degree）和入度（In Degree）。對(duì)于一個(gè)圖中所有節(jié)點(diǎn)的度數(shù)之和，等于所有邊數(shù)的兩倍。

完全圖（Complete Graph）是指節(jié)點(diǎn)之間都有連邊的圖，因此完全圖的邊數(shù)最多，為n(n-1)/2，n為節(jié)點(diǎn)數(shù)。稠密圖（Dense Graph）則是指節(jié)點(diǎn)之間有相對(duì)較多的連邊的圖。稀疏圖（Sparse Graph）則相反，節(jié)點(diǎn)之間的連邊數(shù)量比較少。子圖（Sub Graph）是指原圖中一部分節(jié)點(diǎn)和它們之間的連邊所組成的圖。路徑（Path）是指從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)所經(jīng)過的所有邊和節(jié)點(diǎn)的序列?；芈罚–ycle）是指起點(diǎn)和終點(diǎn)相同的路徑。

連通圖（Connected Graph）是指任意兩個(gè)節(jié)點(diǎn)之間都存在路徑的圖。如果不滿足這個(gè)條件，則稱之為非連通圖（Disconnected Graph）。強(qiáng)連通圖（Strongly Connected Graph）是指任意兩個(gè)節(jié)點(diǎn)之間都存在有向路徑的圖。非強(qiáng)連通圖則相反。

二、算法

1. 圖的鄰接矩陣存儲(chǔ)的初始化算法：

```

void InitMatrix(adjmatrix GA, int K){

for(int i0; i

for(int j0; j

GA[i][j] 0; // 初始化為0

}

}

}

```

2. 根據(jù)一個(gè)圖的邊集生成圖的鄰接矩陣的算法：

```

void CreateMatrix(adrmatrix GA,int n,char*s,int k1,int k2){

for(int i0; i

for(int j0; j

if(ij){

GA[i][j] 0;

}

else{

GA[i][j] -1;// 用-1表示不連通

}

}

}

for(int i0; i

char a s[i*2];

char b s[i*2 1];

GA[a-'A'][b-'A'] 1;

GA[b-'A'][a-'A'] 1;// 如果是無向圖，需要把兩個(gè)方向都賦值

}

}

```

3. 遍歷算法：

(1) 深度優(yōu)先遍歷：

```

void dfsMatrix(adjmatrix GA, int i, int n, bool *visited){

visited[i] true;

printf("%c ",i 'A');

for(int j0;j

if(GA[i][j]!0 !visited[j]){

dfsMatrix(GA,j,n,visited);

}

}

}

```

(2) 廣度優(yōu)先遍歷：

```

void bfsMatrix(adjmatrix GA, int i, int n, bool *visited){

int queue[MAXSIZE],front-1,rear-1;

visited[i] true;

printf("%c ",i 'A');

queue[ rear] i;

while(front!rear){

front ;

int j queue[front];

for(int k0;k

if(GA[j][k]!0 !visited[k]){

visited[k] true;

printf("%c ",k 'A');

queue[ rear] k;

}

}

}

}

```

圖作為非常重要的數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)科學(xué)中扮演著非常重要的角色。學(xué)習(xí)和理解圖的相關(guān)概念和算法，是每個(gè)計(jì)算機(jī)科學(xué)專業(yè)學(xué)生不可或缺的一部分。