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

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

一、圖的基本概念

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

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

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

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

二、算法

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

```

void InitMatrix(adjmatrix GA, int K){

for(int i0; i

for(int j0; j

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

}

}

}

```

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

```

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;// 如果是無向圖，需要把兩個方向都賦值

}

}

```

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)，在計算機科學中扮演著非常重要的角色。學習和理解圖的相關概念和算法，是每個計算機科學專業(yè)學生不可或缺的一部分。