數(shù)據(jù)結構
“圖”的數(shù)據(jù)結構有兩種：
- 鄰接表
鄰接表適用于稀疏圖（邊的數(shù)量遠遠小于頂點的數(shù)量）乳丰，它的抽象描述如下：
adjacency list
上圖是一個含有四個頂點的無向圖，四個頂點V0词疼，V1，V2及V3用一個數(shù)組來存取烁兰，借用后面的結構體定義來描述脚囊，數(shù)組元素的類型為VertexNode，一個字段info用來保存頂點的信息芦拿，另一個字段firstEdge指向與該頂點有關的邊結點士飒，類型為EdgeNode，邊結點的toAdjVex字段表示這條邊的另一個頂點結點的數(shù)組下標蔗崎，next字段僅僅用來指向另一個邊結點酵幕，所有通過next鏈接起來的邊結點都有相同的起始頂點.
注意：當用一個鄰接表描述圖時，就已經(jīng)確定了該圖的遍歷順序缓苛，以上圖的鄰接表為例芳撒，從 V0頂點開始遍歷時，無論是深度優(yōu)先搜索 (DFS)還是廣度優(yōu)先搜索 (BFS)未桥，都會先找到 V1結點笔刹，而從左邊的圖來看，其實V1冬耿，V2徘熔，V3都可以為下一個遍歷的結點。
鄰接表結構體定義如下：
typedef struct EdgeNode
{
int toAdjVex; // The index of vertex array which this edge points to.
float weight; // The edge weight.
struct EdgeNode *next; // The next edge, note that it only means the next edge also links to the vertex which this edge links to.
} EdgeNode;
typedef struct VertexNode
{
VERTEX_DATA_TYPE info; // The vertex info,.
struct EdgeNode* firstEdge; // The first edge which the vertex points to.
} VertexNode;
typedef struct
{
VertexNode adjList[VERTEX_NUM]; // Adjacency list, which stores the all vertexes of the graph.
int vertextNum; // The number of vertex.
int edgeNum; // The number of edge.
} AdjListGraph;
-
鄰接矩陣
鄰接矩陣適用于稠密圖（邊的數(shù)量比較多）淆党，它的抽象描述如下：
adjacency matrix
上圖是個無向無權圖，僅用0讶凉、1來表示兩個頂點是否相連染乌，當然，通常做法是將邊的權值來代替1懂讯，用一個十分大的數(shù)字（如∞）來代替0荷憋，表示不相連。
鄰接矩陣的結構體定義如下：
typedef struct
{
int number;
VERTEX_DATA_TYPE info;
} Vertex;
typedef struct
{
float edges[VERTEX_NUM][VERTEX_NUM]; // The value of this two dimensional array is the weight of the edge.
int vertextNum; // The number of vertex.
int edgeNum; // The number of edge.
Vertex vex[VERTEX_NUM]; // To store vertex.
} MGraph;
算法
深度優(yōu)先搜索 （Depth First Search）
一句話描述就是“一條路走到黑”褐望，它的遞歸與非遞歸的代碼如下：
- 遞歸
void dfsRecursion(AdjListGraph* graph, int startVertexIndex, bool visit[])
{
printf("%c ", (graph -> adjList[startVertexIndex]).info);
visit[startVertexIndex] = true;
EdgeNode* edgeIndex = (graph -> adjList[startVertexIndex]).firstEdge;
while (edgeIndex != NULL)
{
if (visit[edgeIndex -> toAdjVex] == false)
dfsRecursion(graph, edgeIndex -> toAdjVex, visit);
edgeIndex = edgeIndex -> next;
}
}
提示：DFS的遞歸遍歷有些類似于二叉樹的前序遍歷勒庄。
- 非遞歸
借用了額外的數(shù)據(jù)結構——棧串前。
void dfsNonRecursion(AdjListGraph* graph, int startVertextIndex, bool visit[])
{
linked_stack* stack = NULL;
init_stack(&stack);
// Visit the start vertex.
printf("%c ", (graph -> adjList[startVertextIndex]).info);
visit[startVertextIndex] = true;
EdgeNode* edgeNode = (graph -> adjList[startVertextIndex]).firstEdge;
if (edgeNode != NULL)
push(stack, edgeNode);
while (!isEmptyStack(stack))
{
edgeNode = ((EdgeNode*)pop(stack)) -> next;
while (edgeNode != NULL && !visit[edgeNode -> toAdjVex])
{
printf("%c ", (graph -> adjList[edgeNode -> toAdjVex]).info);
visit[edgeNode -> toAdjVex] = true;
push(stack, edgeNode);
edgeNode = (graph -> adjList[edgeNode -> toAdjVex]).firstEdge;
}
}
}
廣度優(yōu)先搜索 （Breadth First Search）
BFS是“一圈一圈往外找”的算法，借助了“循環(huán)隊列”來實現(xiàn)：
void bfs(AdjListGraph* graph, int startVertexIndex, bool visit[])
{
// Loop queue initialization.
LoopQueue loopQ;
loopQ.front = 0;
loopQ.rear = 0;
LoopQueue* loopQueue = &loopQ;
enqueue(loopQueue, &(graph -> adjList[startVertexIndex]));
printf("%c ", (graph -> adjList[startVertexIndex]).info);
visit[startVertexIndex] = true;
while (!isEmpty(loopQueue))
{
VertexNode* vertexNode = dequeue(loopQueue);
EdgeNode* edgeNode = vertexNode -> firstEdge;
while(edgeNode != NULL)
{
if (visit[edgeNode -> toAdjVex] == false)
{
printf("%c ", (graph -> adjList[edgeNode -> toAdjVex]).info);
visit[edgeNode -> toAdjVex] = true;
enqueue(loopQueue, &(graph -> adjList[edgeNode -> toAdjVex]));
}
edgeNode = edgeNode -> next;
}
}
}
提示：
- BFS算法類似于二叉樹的層次遍歷实蔽。
- BFS遍歷的最后一個結點是離起始結點“最遠”的結點荡碾。
最小生成樹 （Minimum Spanning Tree）
Prim
-
算法
- 從圖中任意選擇一個頂點
startVertex，作為生成樹的起始結點局装； - 從生成樹集合（所有已經(jīng)加入生成樹的頂點所組成的集合）外的結點中坛吁，選擇一個距離生成樹集合代價最小的點，將其加入到生成樹集合中（更新
treeSet[]）铐尚，此時由于新結點的加入拨脉，可能使新的生成樹到其他結點的距離發(fā)生變化，因此要更新lowCost[]宣增； - 不斷重復步驟2玫膀，直到所有頂點加入到生成樹集合中。
- 從圖中任意選擇一個頂點
代碼
float prim(MGraph* graph, int startVertex)
{
float totalCost = 0;
float lowCost[VERTEX_NUM]; // The value of lowCost[i] represents the minimum distance from vertex i to current spanning tree.
bool treeSet[VERTEX_NUM]; // The value of treeSet[i] represents whether the vertex i has been merged into the spanning tree.
// Initialization
for (int i = 0; i < (graph -> vertextNum); i++)
{
lowCost[i] = graph -> edges[startVertex][i]; // Init all cost from i to startVertex.
treeSet[i] = false; // No vertex is in the spanning tree set at first.
}
treeSet[startVertex] = true; // Merge the startVertex into the spanning tree set.
printf("%c ", (graph -> vex[startVertex]).info);
for (int i = 0; i < (graph -> vertextNum); i++)
{
int minCost = MAX_COST; // MAX_COST is a value greater than any other edge weight.
int newVertex = startVertex;
// Find the minimum cost vertex which is out of the spanning tree set.
for (int j = 0; j < (graph -> vertextNum); j++)
{
if (!treeSet[j] && lowCost[j] < minCost)
{
minCost = lowCost[j];
newVertex = j;
}
}
treeSet[newVertex] = true; // Merge the new vertex into the spanning tree set.
/*
Some ops, for example you can print the vertex so you will get the sequence of node of minimum spanning tree.
*/
if (newVertex != startVertex)
{
printf("%c ", (graph -> vex[newVertex]).info);
totalCost += lowCost[newVertex];
}
// Judge whether the cost is change between the new spanning tree and the remaining vertex.
for (int j = 0; j < (graph -> vertextNum); j++)
{
if (!treeSet[j] && lowCost[j] > graph -> edges[newVertex][j])
lowCost[j] = graph -> edges[newVertex][j]; // Update the cost between the spanning tree and the vertex j.
}
}
return totalCost;
}
并查集 （Union Find Set）
介紹
并查集可以很容易判斷幾個不同的元素是否屬于同一個集合爹脾，正是因為這個特性帖旨，并查集是克魯斯卡爾算法（ Kruskal's algorithm）的重要工具。
在這個例子中誉简，我們用數(shù)組來作為并查集工具的“集”碉就，數(shù)組的下標代表集合里元素的序列號，而該下標的值表示這個結點的父結點在該數(shù)組的下標闷串。這個數(shù)組是一個大集合瓮钥，大集合里還劃分了許多小集合，劃分的依據(jù)是這些元素是否屬于同一個根結點烹吵，這個根節(jié)點的值為負數(shù)碉熄，其絕對值的大小為該集合里元素的個數(shù)，因此通過不斷尋找兩個元素的父結點肋拔，直至找到根結點锈津，進而判斷根結點是否相等來判定這兩個元素是否屬于同一個集合（在克魯斯卡爾算法中，也就是通過此來判斷新加入的結點是否會形成環(huán)）凉蜂。代碼
int findRootInSet(int array[], int x)
{
if (array[x] < 0)
{
// Find the root index.
return x;
}
else
{
// Recursively find its parent until find the root,
// then recursively update the children node so that they will point to the root.
return array[x] = findRootInSet(array, array[x]);
}
}
// For merging the one node into the other set.
bool unionSet(int array[], int node1, int node2)
{
int root1 = findRootInSet(array, node1);
int root2 = findRootInSet(array, node2);
if (root1 == root2)
{
// It means they are in the same set
return false;
}
// The value of array[root] is negative and the absolute value is its children numbers,
// when merging two sets, we choose to merge the more children set into the less one.
if (array[root1] > array[root2])
{
array[root1] += array[root2];
array[root2] = root1;
}
else
{
array[root2] += array[root1];
array[root1] = root2;
}
return true;
}
注意上面的 unionSet方法是用來合并集合的琼梆，多作為克魯斯卡爾算法的輔助工具，該方法執(zhí)行成功說明選的兩個結點及其所在的集合可以構成一個無環(huán)連通分量窿吩，每次成功執(zhí)行該方法茎杂，都要更新各個集合的狀態(tài)（因為有新的結點加入），以便后續(xù)的判斷纫雁。
最短路徑算法
單源最短路徑算法——迪杰斯特拉算法（Dijkstra Algorithm）
迪杰斯特拉算法是用來計算圖中所有結點到某個特定結點的最短距離的算法煌往，因為執(zhí)行一次迪杰斯特拉算法，只是計算出所給特定的“源結點”到其他結點的最短距離轧邪，因此該算法也屬于“單源最短路徑算法”刽脖。
-
步驟
- 將圖的各個結點分為兩個集合羞海，一個是已經(jīng)訪問的集合（visited set），另一個是未訪問的集合（unvisited set）曲管。算法初始階段却邓，將需要計算的給定“源結點”加入到visited set。
- 從unvisited set里選擇一個距離源結點最近的結點翘地，并將其加入到visited set申尤。
- 將新加入的結點當做“跳板”，重新計算unvisited set里的結點與源結點間的最短距離（由于新加入的結點可能會縮短源結點到unvisited set里的結點的距離衙耕，因此要特別注意）昧穿。
- 重復步驟2直到所有結點都已加入到visited set。
代碼
void dijkstra(MGraph* graph, int startVertexIndex)
{
// For storing the minimum cost from the arbitrary node to the start vertex.
float minCostToStart[VERTEX_NUM];
// For marking whether the node is in the set.
bool set[VERTEX_NUM];
// Initialization
for (int i = 0; i < VERTEX_NUM; i++)
{
minCostToStart[i] = graph -> edges[i][startVertexIndex];
set[i] = false;
}
// Add the start vertex into the set.
set[startVertexIndex] = true;
int minNodeIndex = startVertexIndex;
for (int count = 1; count < VERTEX_NUM; count++)
{
int minCost = MAX_COST;
// Find the adjacent node which is nearest to the startVertexIndex.
for (int i = 0; i < VERTEX_NUM; i++)
{
if (!set[i] && minCostToStart[i] < minCost)
{
minCost = minCostToStart[minNodeIndex];
minNodeIndex = i;
}
}
// Add the proper node into the set
set[minNodeIndex] = true;
// After the new node is added into the set, update the minimum cost of each node which is out of the set.
for (int i = 0; i < VERTEX_NUM; i++)
{
if (!set[i] && (graph -> edges[i][minNodeIndex]) < MAX_COST)
{
// The new cost of each node to source = the cost of new added node to source + the cost of node i to new added node.
float newCost = minCostToStart[minNodeIndex] + graph -> edges[i][minNodeIndex];
if (newCost < minCostToStart[i])
minCostToStart[i] = newCost;
}
}
}
printf("The cost of %c to each node:\n", (graph -> vex[startVertexIndex]).info);
for (int i = 0; i < VERTEX_NUM; i++)
{
if (i != startVertexIndex)
printf("-----> %c : %f\n", (graph -> vex[i]).info, minCostToStart[i]);
}
}
提示：迪杰斯特拉算法與普利姆算法十分類似橙喘，特別是步驟 2时鸵。迪杰斯特拉算法總是從 unvisited set里選擇距離 源結點最近的結點加入到 visited set里，而普利姆算法總是從生成樹集合外厅瞎，選擇一個距離 生成樹這個集合最近的結點加入到生成樹中饰潜。
多源最短路徑算法——弗洛伊德算法（Floyd Algorithm）
與迪杰斯特拉算法不同的是，調用一次弗洛伊德算法可以計算任意兩個結點間的最短距離和簸，當然彭雾，你也可以通過多次調用迪杰斯特拉算法來計算多源最短路徑。
-
步驟
- 初始化
minCost[i][j]锁保。minCost[i][j]表示結點i到j的距離薯酝。 - 引入第三結點（跳板）k，查看通過結點k能否使
minCost[i][j]得值變小爽柒，如果能吴菠，則更新minCost[i][j]的值。 - 重復步驟2直到所有結點都曾經(jīng)被當做k為止浩村。
- 初始化
代碼
void floyd(MGraph* graph)
{
float minCost[VERTEX_NUM][VERTEX_NUM]; // Store the distance between any two nodes.
int path[VERTEX_NUM][VERTEX_NUM]; // Store the intermediate node between the two nodes.
int i, j, k;
// Initialization
for (i = 0; i < VERTEX_NUM; i++)
{
for (j = 0; j < VERTEX_NUM; j++)
{
minCost[i][j] = graph -> edges[i][j];
path[i][j] = -1;
}
}
// Find if there is another k node, it makes the distance dis[i][k] + dis[k][j] < dis[i][j];
for (k = 0; k < VERTEX_NUM; k++)
for (i = 0; i < VERTEX_NUM; i++)
for (j = 0; j < VERTEX_NUM; j++)
{
if (minCost[i][j] > minCost[i][k] + minCost[k][j])
{
minCost[i][j] = minCost[i][k] + minCost[k][j];
path[i][j] = k;
}
}
for (i = 0; i < VERTEX_NUM; i++)
for (j = 0; j < VERTEX_NUM; j++)
{
if (i != j && minCost[i][j] != MAX_COST)
printf("%c ---> %c, the minimum cost is %f\n", (graph -> vex[i]).info, (graph -> vex[j]).info, minCost[i][j]);
}
}
