一.思維導圖

二.概念筆記

圖的存儲結構

1. 鄰接矩陣

定義：設圖G有n (n大于等于1) 個頂點，則鄰接矩陣是一個n階方陣。

當矩陣中的 [i,j] !=0(下標從1開始) ,代表其對應的第i個頂點與第j個頂點是連接的

特點

無向圖的鄰接矩陣是對稱矩陣，n個頂點的無向圖需要n*(n+1)/2個空間大小

有向圖的鄰接矩陣不一定對稱，n個頂點的有向圖需要n2的存儲空間

無向圖中第i行的非零元素的個數為頂點Vi的度

有向圖中第i行的非零元素的個數為頂點Vi的出度，第i列的非零元素的個數為頂點Vi的入度

2.鄰接表

定義：為圖G中的每一個頂點建立一個單鏈表，每條鏈表的結點元素為與該頂點連接的頂點

特點

無向圖頂點Vi的度為第i個單鏈表中的結點數無向圖中

頂點Vi的出度為第i個單鏈表中的結點個數

頂點Vi的入度為全部單鏈表中連接點域值是i的結點個數

圖的遍歷

深度優先遍歷

圖的深度優先遍歷類似于樹的前序遍歷。先以一個未被訪問過的頂點作為起始頂點，沿當前頂點的邊走到未訪問過的頂點；當沒有未訪問過的頂點時，則回到上一個頂點，繼續試探別的頂點，直到所有的頂點都被訪問。

廣度優先遍歷

圖的廣度優先遍歷類似于樹的層次遍歷。從圖中某頂點出發，依次訪問各個鄰接點，然后分別從這些鄰接點出發依次訪問它們的鄰接點，并使得“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，直至圖中所有頂點都被訪問到為止。

最小生成樹

Prim算法

Prim算法首先以一個結點作為最小生成樹的初始結點，然后以迭代的方式找出與最小生成樹中各結點權重最小邊，并加入到最小生成樹中。加入之后如果產生回路則跳過這條邊，選擇下一個結點。直至所有結點都加入到最小生成樹中。

Kruskal算法

Kruskal算法在找最小生成樹結點之前，需要對所有權重邊做從小到大排序。將排序好的權重邊依次加入到最小生成樹中，如果加入時產生回路就跳過這條邊，加入下一條邊。當所有結點都加入到最小生成樹中之后，就找出了最小生成樹。

Kruskal在算法效率上是比Prim快，因為Kruskal只需一次對權重的排序就能找到最小生成樹，而Prim算法需要多次對鄰邊排序才能找到

最短路徑

Dijkstra算法

Dijkstra算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

Floyd算法

Floyd算法是先找出最短的距離，然后在考慮如何找出對應的行進路線。

三.疑難問題

關于Dijkstra算法和Floyd算法的代碼實現，從網上摘取兩段代碼理解

const int MAXINT = 32767;

const int MAXNUM = 10;

int dist[MAXNUM];

int prev[MAXNUM];

int A[MAXUNM][MAXNUM];

void Dijkstra(int v0)

{

bool S[MAXNUM]; // 判斷是否已存入該點到S集合中

int n=MAXNUM;

for(int i=1; i<=n; ++i)

{

dist[i] = A[v0][i];

S[i] = false; // 初始都未用過該點

if(dist[i] == MAXINT)

prev[i] = -1;

else

prev[i] = v0;

}

dist[v0] = 0;

S[v0] = true;

for(int i=2; i<=n; i++)

{

int mindist = MAXINT;

int u = v0; 　　 // 找出當前未使用的點j的dist[j]最小值

for(int j=1; j<=n; ++j)

if((!S[j]) && dist[j]

{

u = j; // u保存當前鄰接點中距離最小的點的號碼

mindist = dist[j];

}

S[u] = true;

for(int j=1; j<=n; j++)

if((!S[j]) && A[u][j]

{

if(dist[u] + A[u][j] < dist[j]) //在通過新加入的u點路徑找到離v0點更短的路徑

{

dist[j] = dist[u] + A[u][j]; //更新dist

prev[j] = u; //記錄前驅頂點

}

}

}

}

typedef struct

{

char vertex[VertexNum]; //頂點表

int edges[VertexNum][VertexNum]; //鄰接矩陣,可看做邊表

int n,e; //圖中當前的頂點數和邊數

}MGraph;

void Floyd(MGraph g)

{

int A[MAXV][MAXV];

int path[MAXV][MAXV];

int i,j,k,n=g.n;

for(i=0;i

for(j=0;j

{

A[i][j]=g.edges[i][j];

path[i][j]=-1;

}

for(k=0;k

{

for(i=0;i

for(j=0;j

if(A[i][j]>(A[i][k]+A[k][j]))

{

A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;

}

}

}