4 圖的遍歷
??圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種。
4.1 深度優(yōu)先遍歷
??深度優(yōu)先遍歷（Depth First Search），也稱為深度優(yōu)先搜索，簡稱DFS，深度優(yōu)先遍歷，是指從某一個頂點開始，按照一定的規(guī)則，訪問并記錄下一個未訪問頂點。對于非連通圖，則是按連通分量，采用同一規(guī)則進(jìn)行深度優(yōu)先遍歷的方式，以以下圖為例：
??我們使用visited[vertexSize]來記錄已訪問的頂點，先從A開始，并把A加入到visited中，訪問規(guī)則是“下一個訪問的頂點是最右手邊的那個頂點”，注意，圖上的小人是面向我們，從上往下走的，此時visited = {A}：
??接下來，依附于頂點A的邊有(A,B)、(A,F)，小人右手邊的邊是(A,B)，因此延著(A,B)走，visited = {A, B}:
??依附于頂點B的邊有(B,C)、(B,I)、(B,G)，小人右手邊且沒被走過的邊是(B,C)，于是延著邊(B,C)走，visited = {A, B, C}：
??按照這個規(guī)則走，走到F時，visited = {A, B, C, D, E, F}：
??這時，小人的右手邊有幾條路，從右至左依次是(F,A)、(F,G)、(F、E)，但頂點A在visited中，表示頂點A已經(jīng)被訪問過了，所以排除(F,A)，延著(F,G)走，visited = {A, B, C, D, E, F, G}：
??這時，相對于頂點G，小人可走的路從右到左依次是(G,B)、(G,D)、(G,H），B和D已經(jīng)在visited中，因此跳過，延著(G,H)走，visited = {A, B, C, D, E, F, G, H}：
??這是，相對于頂點H，小人可走的路從右到左依次是(H,D)、(H、E)，但D和E都在visited中了，這時，讓小人延原路返回，即延著(H,G)走：
??但相對于頂點G，可走的路(G,B)、(G,D)和(G,H)三條路對應(yīng)的頂點B、D、H也都在visited中了，無路可走了，繼續(xù)原路返回，到頂點F，仍然無路可走，繼續(xù)返回E，仍無路可走，繼續(xù)返回D：
??這時，發(fā)現(xiàn)了(D,I)這條路還沒走過，于是延著(D,I)走，visited = {A, B, C, D, E, F, G, H, I}：
??又無路可走了，于是原路返回，直到返回頂點A，也就是開始的那個頂點，表示圖已遍歷完。
??再來總結(jié)一下深度遍歷優(yōu)先的過程：
??(1) 先定一個規(guī)則，比如“延著依附于當(dāng)前頂點中，最左側(cè)的，未被訪問的邊進(jìn)行迭代”；
??(2) 從某一個頂點開始按定義的規(guī)則迭代；
??(3) 若有符合規(guī)則的邊，則繼續(xù)往下迭代，若無符合規(guī)則的邊，則一步一步原路返回，查找可迭代的邊；
??(4) 當(dāng)原路返回到最開始的那個頂點時，迭代完畢；
??實際上整體上是一個遞歸調(diào)度的過程，主要就是找到“下一條邊”。
??注意，深度優(yōu)先遍歷的規(guī)則并不是固定不變的，只要最終結(jié)果遵循“按一定規(guī)則，逐步訪問結(jié)點的下一個鄰邊”即可。
4.1.1 鄰接矩陣的深度優(yōu)先遍歷
??我們舉幾個例子：
??對這些圖使用深度優(yōu)先遍歷時，找“下一條未被訪問邊”的方式是：
??(1) 從第一個頂點開始，訪問arc[0][1]、arc[0][2]…arc[0][n]，找到第一個未被訪問的邊，邊的判斷是，如果為圖，則值為1表示存在邊，如果為網(wǎng)，則值不為無窮大且arc[i][j]中i不等于j表示存在邊；
??(2) 找到這個邊后，訪問它，假設(shè)這個邊為arc[0][x]；
??(3) 然后繼續(xù)訪問arc[x]，找到x的未被訪問的邊，即遞歸第(1)、(2)步，直到所有關(guān)聯(lián)的邊都訪問完；
??(4) 若此時，結(jié)點還未迭代完，則從第二個“未被訪問的頂點”開始，繼續(xù)迭代；
??因此如上無向圖的遍歷過程如下所示：
??過程為：
??(0) iterate C；
??(1) 遍歷arc[0][j]，尋找C相關(guān)的頂點，找到(C,D)，visit C，visit D；
??(2) 遍歷arc[1][j]，尋找D相關(guān)的頂點，找到(D,C)，兩個頂點都被訪問過，跳過；
??(3) 找到(D,A)，visit A；
??(4) 遍歷arc[2][j]，尋找A相關(guān)的頂點，找到(A,C)，兩個頂點都被訪問過，跳過；
??(5) 找到(A,D)，兩個頂點都被訪問過，跳過；
??(6) 找到(A,B)，visit B；
??(7) 遍歷arc[3][j]，尋找B相關(guān)的頂點，找到(B,C)，兩個頂點都被訪問過，跳過；
??(8) 找到(B,D)，值為0，不相關(guān)，跳過；
??(9) 找到(B,A)，兩個頂點都被訪問過，跳過；
??(10) 找到(B,F)，visit F；
??(11) 遍歷arc[4][j]，尋找F相關(guān)的頂點，找到(F,C)，值為0，不相關(guān)，跳過；
??(12) 找到(F,D)，值為0，不相關(guān)，跳過；
??(13) 找到(F,A)，值為0，不相關(guān)，跳過；
??(14) 找到(F,B)，兩個頂點都被訪問過，跳過；
??(15) 找到(F,E)，visit E，此時所有頂點均訪問完畢，結(jié)束；
??如上有向網(wǎng)的遍歷過程如下所示：
??過程為：
??(0) iterate E；
??(1) 迭代arc[0][j]，尋找E指向的頂點，找到<E,F>，visit E，然后發(fā)現(xiàn)數(shù)組值為無窮大，不相關(guān)，跳過；
??(2) 找到<E,C>，值為無窮大，不相關(guān)，跳過；
??(3) 找到<E,A>，visit A；
??(4) 迭代arc[3][j]，尋找A指向的頂點，找到<A,E>，值為無窮大，不相關(guān)，跳過；
??(5) 找到<A,F>，值為無窮大，不相關(guān)，跳過；
??(6) 找到<A,C>，值為無窮大，不相關(guān)，跳過；
??(7) 找到<A,B>，值為無窮大，不相關(guān)，跳過；
??(8) 找到<A,D>，visit D；
??(9) 迭代arc[5][j]，尋找D指向的頂點，找到<D,E>，值為無窮大，不相關(guān)，跳過；
??(10) 找到<D,F>，visit F；
??(11) 迭代arc[1][j]，尋找F指向的頂點，找到<F,E>，值為無窮大，不相關(guān)，跳過；
??(12) 找到<F,C>，值為無窮大，不相關(guān)，跳過；
??(13) 找到<F,A>，值為無窮大，不相關(guān)，跳過；
??(14) 找到<F,B>，值為無窮大，不相關(guān)，跳過；
??(15) 找到<F,D>，值為無窮大，不相關(guān)，跳過；
??(16) F處理完畢，沒有相關(guān)的頂點，于是回退一步，到D，繼續(xù)迭代arc[5][j]，找到<D,C>，visit C；
??(17) 迭代arc[2][j]，尋找C指向的頂點，找到<C,E>，E已被訪問，跳過；
??(18) 找到<C,F>，值為無窮大，不相關(guān)，跳過；
??(19) 找到<C,A>，值為無窮大，不相關(guān)，跳過；
??(20) 找到<C,B>，visit B，此時所有頂點均訪問完畢，結(jié)束；
??代碼實現(xiàn)如下所示：
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @author Korbin
* @date 2023-02-02 17:02:23
**/
public List<T> deepFirstTraverse() {
List<T> visitedVertex = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
for (int i = 0; i < vertexNum && visitedVertex.size() < vertexNum; i++) {
deepFirstTraverse(visitedVertex, visited, i);
}
return visitedVertex;
}
/**
* 對圖進(jìn)行深度迭代
*
* @param visitedVertex 迭代結(jié)果
* @param visited 已訪問過的頂點
* @param index 接著要迭代的結(jié)點
* @author Korbin
* @date 2023-02-02 17:26:43
**/
public void deepFirstTraverse(List<T> visitedVertex, boolean[] visited, int index) {
// 取出當(dāng)前頂點
if (!visited[index]) {
// 當(dāng)前頂點未被訪問，才繼續(xù)
T ver = vertex[index];
visitedVertex.add(ver);
visited[index] = true;
// 取出當(dāng)前頂點可走的邊
for (int j = 0; j < arc[index].length && visitedVertex.size() < vertexNum; j++) {
if (j != index) {
switch (type) {
case UNDIRECTED:
case DIRECTED: {
// 無向圖或有向圖，為1且頂點未被訪問表示可以走
try {
int weight = (int) (arc[index][j]);
if (weight == 1 && !visited[j]) {
// 可以繼續(xù)往下走
deepFirstTraverse(visitedVertex, visited, j);
}
} catch (NumberFormatException e) {
// do nothing
}
break;
}
case UNDIRECTED_NETWORK:
case DIRECTED_NETWORK: {
// 無向圖或有向網(wǎng)
// 不為infinity，且頂點未被訪問
if (!arc[index][j].equals(infinity) && !visited[j]) {
// 可以繼續(xù)往下走
deepFirstTraverse(visitedVertex, visited, j);
}
break;
}
}
}
}
}
}
4.1.2 鄰接表的深度優(yōu)先遍歷
??考慮如下有向圖：
??從第一個頂點開始，打到它未被訪問的下一個頂點，尋找的過程是先找firstEdge，如果firstEdge指向的頂點已被訪問，則找firstEdge的next，直到找到這個頂點為止；接著訪問這個頂點的指向下一個未訪問的頂點，尋找方式與第一個頂點相同。
??該鄰接表的遍歷過程如下所示：
??整體過程為：
??(0) iterate C, visit C；
??(1) 找頂點C相關(guān)的頂點，找到(C,D)，visit D；
??(2) 找頂點D相關(guān)的頂點，找到(D,C)，兩個頂點都被訪問過，跳過；
??(3) 繼續(xù)找頂點D相關(guān)的頂點，找到(D,A)，visit A；
??(4) 找頂點A相關(guān)的頂點，找到(A,C)，兩個頂點都被訪問過，跳過；
??(5) 繼續(xù)找頂點A相關(guān)的頂點，找到(A,D)，兩個頂點都被訪問過，跳過；
??(6) 繼續(xù)找頂點A相關(guān)的頂點，找到(A,B)，visit B；
??(7) 找頂點B相關(guān)的頂點，找到(B,C)，兩個頂點都被訪問過，跳過；
??(8) 繼續(xù)找頂點B相關(guān)的頂點，找到(B,A)，兩個頂點都被訪問過，跳過；
??(9) 繼續(xù)找頂點B相關(guān)的頂點，找到(B,F)，visit F；
??(10) 找頂點F相關(guān)的頂點，找到(F,B)，兩個頂點都被訪問過，跳過；
??(11) 繼續(xù)找頂點F相關(guān)的頂點，找到(F,E)，visit E，此時所有頂點都訪問完畢，結(jié)束；
??相應(yīng)地，有向圖的鄰接表遍歷過程如下所示：
??即：
??(0) iterate C，visit C；
??(1) 找頂點C指向的頂點，找到<C,B>，visit B；
??(2) 找頂點B指向的頂點，找到<B,A>，visit A；
??(3) 找頂點A指向的頂點，找到<A,D>，visit D；
??(4) 找頂點D指向的頂點，找到<D,C>，兩個頂點都被訪問過，跳過；
??(5) 繼續(xù)找頂點D指向的頂點，找到<D,B>，兩個頂點都被訪問過，跳過；
??(6) 繼續(xù)找頂點D指向的頂點，找到<D,F>，visit F；F沒有指向的頂點，回退到D；繼續(xù)找頂點D指向的頂點，D所有指向的頂點都已訪問，回退到B；繼續(xù)找頂點B指向的頂點，B所有指向的頂點都已被訪問，回退到C；
??(7) 繼續(xù)找頂點C指向的頂點，找到<C,E>，visit E，此時所有頂點訪問完畢，結(jié)束；
??除了鄰接表外，還有一種逆鄰接表，逆鄰接表使用的遍歷方法與鄰接表不同，因為邊集數(shù)組中保存的是每個頂點被指向的信息，如下：
??逆鄰接表的查找下一個未訪問頂點的過程，是“遍歷邊集數(shù)組，找到firstEdge或nextEdge的為當(dāng)前頂點的邊集數(shù)組結(jié)點，這個邊集數(shù)組元素關(guān)聯(lián)的第一個未被訪問的頂點數(shù)組元素，就是要找的下一個頂點”，如上逆鄰接表的遍歷過程如下：
??(1) 從第一個頂點C開始迭代，將它加入訪問列表，visit C；
??(2) 迭代所有邊集數(shù)組，找到C指向的頂點，因為C已被訪問，因此忽略它，先看D，只有邊<A,D>，與頂點C不相關(guān)，跳過；
??(3) 看頂點A，第一條邊<B,A>，與頂點C不相關(guān)，跳過；
??(4) 繼續(xù)看頂點A，第二條邊<E,A>，與頂點C不相關(guān)，跳過；
??(5) A的邊看完了，看B的邊，第一條邊<C,B>，找到頂點B是C指向的頂點，且由于是按下標(biāo)從小到大迭代的，因此它一定是C指向的，且下標(biāo)最小的頂點，因此，visit B；
??(6) 接下來看頂點B指向的頂點，首先是頂點C，因為已訪問過，因此忽略，然后是頂點D，有邊<A,D>，與頂點B不相關(guān)，跳過；
??(7) 然后看頂點A，有邊<B,A>，A是頂點B指向的頂點，因此visit A；
??(8) 接下來看頂點A指點的頂點，頂點C已被訪問，仍然跳過，然后是頂點D，打到邊<A,D>，符合要求，因此，visit D；
??(9) 接下來看頂點D指向的頂點，前面的幾個頂點C、D、A、B都已被訪問過，跳過，看頂點F，有邊<D,F>，符合要求，因此，visit F；
??(10) 接下來看頂點F指向的頂點，前面的幾個頂點C、D、A、B、F都已被訪問，跳過，看頂點E，有邊<C,E>，與頂點F不相關(guān)，跳過；
??(11) 這時，所有頂點都迭代完畢，但仍未訪問到所有頂點，因此回到第(1)步，繼續(xù)迭代頂點，C已迭代過，于是看頂點D，頂點D已被訪問，跳過；
??(12) 繼續(xù)，迭代頂點A，已被訪問，跳過；
??(13) 繼續(xù)，迭代頂點B，已被訪問，跳過；
??(14) 繼續(xù)，迭代頂點F，已被訪問，跳過；
??(15) 繼續(xù)，迭代頂點E，未被訪問，因此，visit E，此時，所有頂點都訪問完畢，遍歷結(jié)束；
??代碼實現(xiàn)如下所示：
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @author Korbin
* @date 2023-02-02 19:59:26
**/
public List<T> deepFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
// 對于鄰接表，從第一個頂點開始處理，先處理firstEdge
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
if (!visited[i]) {
System.out.println("iterate " + vertexes[i].getVertex());
VertexNode<T, W> vertexNode = vertexes[i];
vertexList.add(vertexNode.getVertex());
visited[i] = true;
if (reverseAdjacency) {
deepFirstTraverse(vertexList, visited, i);
} else {
deepFirstTraverse(vertexList, visited, vertexNode);
}
}
}
return vertexList;
}
/**
* 對使用逆鄰接表存儲的圖進(jìn)行深度優(yōu)先遍歷
*
* @param vertexList 遍歷結(jié)果
* @param visited 訪問列表
* @param index 當(dāng)前遍歷的下標(biāo)
* @author Korbin
* @date 2023-02-06 18:13:34
**/
public void deepFirstTraverse(List<T> vertexList, boolean[] visited, int index) {
int minRefIndex = -1;
// 找到index指向的下標(biāo)最小的未訪問的頂點
boolean got = false;
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum && !got; i++) {
if (!visited[i]) {
VertexNode<T, W> vertexNode = vertexes[i];
EdgeNode<W> edgeNode = vertexNode.getFirstEdge();
while (null != edgeNode && vertexList.size() < vertexNum) {
int edgeIndex = edgeNode.getIndex();
System.out.format("check %s-%s\r\n", vertexes[edgeIndex].getVertex(), vertexes[i].getVertex());
if (edgeIndex == index) {
minRefIndex = i;
got = true;
break;
}
edgeNode = edgeNode.getNext();
}
}
}
if (minRefIndex != -1) {
if (!visited[minRefIndex]) {
// 訪問這個頂點
visited[minRefIndex] = true;
vertexList.add(vertexes[minRefIndex].getVertex());
System.out.println("in " + vertexes[minRefIndex].getVertex());
// 再訪問這個頂點指向的頂點
deepFirstTraverse(vertexList, visited, minRefIndex);
}
}
}
/**
* 對使用鄰接表存儲的圖進(jìn)行深度優(yōu)先遍歷
*
* @param vertexList 遍歷結(jié)果
* @param visited 已訪問的頂點
* @param vertexNode 正在訪問的頂點
* @author Korbin
* @date 2023-02-03 20:26:22
**/
public void deepFirstTraverse(List<T> vertexList, boolean[] visited, VertexNode<T, W> vertexNode) {
EdgeNode<W> firstEdge = vertexNode.getFirstEdge();
while (null != firstEdge && vertexList.size() < vertexNum) {
System.out.format("check %s-%s\r\n", vertexNode.getVertex(), vertexes[firstEdge.getIndex()].getVertex());
int index = firstEdge.getIndex();
if (!visited[index]) {
// 把它加入到遍歷結(jié)果中，然后遞歸處理它對應(yīng)的頂點
VertexNode<T, W> nextNode = vertexes[index];
vertexList.add(nextNode.getVertex());
visited[index] = true;
deepFirstTraverse(vertexList, visited, nextNode);
}
// 取下一個edge
firstEdge = firstEdge.getNext();
}
}
4.1.3 十字鏈表的深度優(yōu)先遍歷
??十字鏈表是在鄰接表上的進(jìn)一步優(yōu)化，因此十字鏈表的深度優(yōu)先遍歷方式與鄰接表類似，鄰接表是處理firstEdge，十字鏈表處理的是firstOut和nextHead，因為firstOut就等于鄰接表（非逆鄰接表）的firstEdge，而nextHead相關(guān)于鄰接表的EdgeNode中的next，大致邏輯為：
??(1) 從第一個頂點開始處理，按如下規(guī)則：
????1) 如果頂點X未被訪問，則訪問它；
????2) 找到頂點X的指向的下一個未被訪問的頂點，我們知道，首先是firstOut，然后是firstOut之后弧結(jié)點的nextHead；
????3) 找到這個頂點后，訪問它，然后遞歸1)、2)步；
??(2) 繼續(xù)迭代頂點列表中的其他頂點，若還有未訪問的頂點，則按(1)的規(guī)則處理，直到所有頂點處理完畢；
??以下面的十字鏈表為例：
??下圖展示了它的深度優(yōu)先遍歷過程：
??(0) 先忽略所有firstIn相關(guān)的線，然后iterate E，visit E；
??(1) 找到E指向的頂點，找到<E,A>，visit A；
??(2) 找到A指向的頂點，找到<A,D>，visit D；
??(3) 找到D指向的頂點，找到<D,F>，visit F；F沒有指向的頂點，因此回退到D；
??(4) 找到D指向的頂點，找到<D,C>，visit C;
??(5) 找到C指向的頂點，找到<C,E>，兩個頂點都已被訪問，跳過；
??(6) 繼續(xù)找到C指向的頂點<C,B>，visit B，此時所有頂點都已被訪問，結(jié)束；
??代碼如下所示：
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @author Korbin
* @date 2023-02-02 19:59:26
**/
public List<T> deepFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
// 對于鄰接表，從第一個頂點開始處理，先處理firstEdge
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
if (!visited[i]) {
AcrossLinkVertexNode<T, W> vertexNode = vertexes[i];
vertexList.add(vertexNode.getVertex());
visited[i] = true;
deepFirstTraverse(vertexList, visited, vertexNode);
}
}
return vertexList;
}
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @param vertexList 遍歷結(jié)果
* @param visited 已訪問于列表
* @param vertexNode 待處理的頂點
* @author Korbin
* @date 2023-02-03 19:33:32
**/
private void deepFirstTraverse(List<T> vertexList, boolean[] visited, AcrossLinkVertexNode<T, W> vertexNode) {
AcrossLinkEdgeNode<W> firstEdge = vertexNode.getFirstOut();
int nextIndex = -1;
while (null != firstEdge && vertexList.size() < vertexNum) {
// 指向的頂點下標(biāo)為headIndex
int index = firstEdge.getHeadIndex();
if (!visited[index]) {
vertexList.add(vertexes[index].getVertex());
visited[index] = true;
nextIndex = index;
// 遞歸處理下一個頂點的鄰邊
deepFirstTraverse(vertexList, visited, vertexes[nextIndex]);
}
firstEdge = firstEdge.getNextHead();
}
}
4.1.4 鄰接多重表的深度優(yōu)先遍歷
??考慮如下鄰接多重表：
??第一個頂點是C，它有三條關(guān)聯(lián)的邊，分別是(C,A)、(C,B)和(C,D)，我們把規(guī)則定為，下一個未訪問的鄰邊是在頂點數(shù)組中下標(biāo)最小，且未訪問的那條邊，這個定義與鄰接多重表的存儲結(jié)構(gòu)相同，鄰接多重表的存儲設(shè)計是“firstEdge指向第一條邊，iLink指向下一條邊（下一條邊的jVex必須為當(dāng)前頂點），下一條邊的jLink指向下下一條邊（并不要求jVex為當(dāng)前頂點），下下一條邊的jLink指向下下一條邊（并不要求jVex為當(dāng)前頂點）,依此類推”，因此鄰接多重表深度優(yōu)先遍歷的過程是：
??(1) 從第一個頂點X開始，找到這個頂點下一條未被訪問的邊(X,Y)：
????1) 若能找到Y(jié)，則訪問Y，并查找Y的下一條未被訪問的邊；
????2) 若Y不存在，則原路返回，走上一個頂點的未被訪問的邊；
??(2) 遞歸執(zhí)行第(1)步，直到找不到下一條未被訪問的邊時，繼續(xù)對第二個頂點進(jìn)行處理，直到所有頂點處理完畢。
??如下為該鄰接多重表的深度優(yōu)先遍歷過程：
??過程為：
??(0) iterate C，visit C；
??(1) 找C關(guān)聯(lián)的頂點，找到(C,D)，visit D；
??(2) 找D關(guān)聯(lián)的頂點，找到(D,A)，visit A；
??(3) 找A關(guān)聯(lián)的頂點，找到(A,C)，兩個頂點都已訪問，跳過；
??(4) 繼續(xù)找A關(guān)聯(lián)的頂點，找到(D,A)，兩個頂點都已訪問，跳過；
??(5) 繼續(xù)找A關(guān)聯(lián)的頂點，找到(A,B)，visit B；
??(6) 找B關(guān)聯(lián)的頂點，找到(B,C)，兩個頂點都已訪問，跳過；
??(7) 繼續(xù)找B關(guān)聯(lián)的頂點，找到(A,B)，兩個頂點都已訪問，跳過；
??(8) 繼續(xù)找B關(guān)聯(lián)的頂點，找到(F,B)，visit F；
??(9) 找F關(guān)聯(lián)的頂點，找到(F,B)，兩個頂點都已訪問，跳過；
??(10) 繼續(xù)找F關(guān)聯(lián)的頂點，找到(E,F)，visit E，所有頂點都已訪問，結(jié)束；
??實現(xiàn)代碼如下所示：
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @return 遍歷結(jié)果
* @author Korbin
* @date 2023-02-03 17:09:46
**/
public List<T> deepFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
// 從第1個頂點開始找
if (!visited[i]) {
AdjacencyMultiVertexNode<T, W> vertexNode = vertexes[i];
vertexList.add(vertexNode.getVertex());
visited[i] = true;
deepFirstTraverse(vertexList, visited, vertexNode);
}
}
return vertexList;
}
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @param vertexList 遍歷結(jié)果
* @param visited 頂點是否已被訪問
* @param vertexNode 待迭代的頂點
* @author Korbin
* @date 2023-02-03 17:44:43
**/
public void deepFirstTraverse(List<T> vertexList, boolean[] visited, AdjacencyMultiVertexNode<T, W> vertexNode) {
AdjacencyMultiEdgeNode<W> firstEdge = vertexNode.getFirstEdge();
if (null != firstEdge) {
// firstEdge的關(guān)聯(lián)頂點下標(biāo)是jVex
int index = firstEdge.getJVex();
int myIndex = firstEdge.getIVex();
if (!visited[index]) {
// 未訪問
AdjacencyMultiVertexNode<T, W> nextVertexNode = vertexes[index];
vertexList.add(nextVertexNode.getVertex());
visited[index] = true;
// 然后處理index對應(yīng)的頂點，找它的下一個未訪問的鄰邊
deepFirstTraverse(vertexList, visited, nextVertexNode);
} else {
// 已訪問
// 下一個相關(guān)邊是firstEdge的iLink
AdjacencyMultiEdgeNode<W> nextEdge = firstEdge.getILink();
if (null != nextEdge) {
// 這個相關(guān)邊的關(guān)聯(lián)頂點是iVex
index = nextEdge.getIVex();
if (!visited[index]) {
// 未訪問
AdjacencyMultiVertexNode<T, W> nextVertexNode = vertexes[index];
vertexList.add(nextVertexNode.getVertex());
visited[index] = true;
// 然后處理index對應(yīng)的頂點，找它的下一個未訪問的鄰邊
deepFirstTraverse(vertexList, visited, nextVertexNode);
} else {
// 已訪問
// 下一條，以及下下條等，相關(guān)邊都是jLink
nextEdge = nextEdge.getJLink();
while (null != nextEdge && vertexList.size() < vertexNum) {
// 關(guān)聯(lián)頂點可能是iVex，也可能是jVex
int iVex = nextEdge.getIVex();
int jVex = nextEdge.getJVex();
if (iVex == myIndex) {
// 關(guān)聯(lián)頂點是JVex
if (!visited[jVex]) {
AdjacencyMultiVertexNode<T, W> nextVertexNode = vertexes[jVex];
vertexList.add(nextVertexNode.getVertex());
visited[jVex] = true;
// 然后處理index對應(yīng)的頂點，找它的下一個未訪問的鄰邊
deepFirstTraverse(vertexList, visited, nextVertexNode);
} else {
nextEdge = nextEdge.getJLink();
}
} else if (jVex == myIndex) {
// 關(guān)聯(lián)頂點是IVex
if (!visited[iVex]) {
AdjacencyMultiVertexNode<T, W> nextVertexNode = vertexes[iVex];
vertexList.add(nextVertexNode.getVertex());
visited[iVex] = true;
// 然后處理index對應(yīng)的頂點，找它的下一個未訪問的鄰邊
deepFirstTraverse(vertexList, visited, nextVertexNode);
} else {
nextEdge = nextEdge.getILink();
}
}
}
}
}
}
}
}
4.1.5 邊集數(shù)組的深度優(yōu)先遍歷
??邊集數(shù)組存儲了每條邊的begin、end信息，由于無向圖/網(wǎng)和有向圖/網(wǎng)不同，無向圖/網(wǎng)的begin和end可以是邊上的任何一個頂點，因此對于無向圖/網(wǎng)和有向圖/網(wǎng)的遍歷方式不同，但整體方向差不多：從下標(biāo)最小的那個頂點開始，找每個頂點關(guān)聯(lián)的、未被訪問的、下標(biāo)最小的那個頂點進(jìn)行訪問。
??先看無向圖/網(wǎng)：
??從下標(biāo)最小的那個頂點開始找，即從頂點C開始找，找它的邊，有(B,C)、(C,A)和(C,D)，下標(biāo)最小的關(guān)聯(lián)頂點是D，然后找D的邊，有(A,D)、(C,D)，C被訪問過了，因此下一個頂點是C，依此類推，整體過程如下：
??整體過程是：
??(0) iterate C；
??(1) 找到C關(guān)聯(lián)的頂點，找到(C,D)，visit C，visit D；
??(2) 找到D關(guān)聯(lián)的頂點，找到(A,D)，visit A；
??(3) 找到A關(guān)聯(lián)的頂點，找到(A,B)，visit B；
??(4) 找到B關(guān)聯(lián)的頂點，找到(B,F)，visit F；
??(5) 找到F關(guān)聯(lián)的頂點，找到(F,E)，visit E，所有頂點訪問完畢，結(jié)束；
??無向圖/網(wǎng)在找“下一個頂點”時，找到的邊中，可以begin等于當(dāng)前頂點，也可以end等于當(dāng)前頂點，但有向網(wǎng)則不同，只能找end為當(dāng)前頂點的邊，看如下有向圖：
??處理過程如下：
??整體過程是：
??(0) iterate E；
??(1) 找E指向的頂點，找到<E,A>，visit E，visit A；
??(2) 找A指向的頂點，找到<A,D>，visit D；
??(3) 找D指向的頂點，找到<D,F>，visit F；F沒有指向任何頂點，回退到D；
??(4) 找D指向的頂點，找到<D,C>，visit C；
??(5) 找C指向的頂點，找到<C,B>，visit B，此時，所有頂點訪問完畢，結(jié)束；
??代碼實現(xiàn)如下所示：
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @return 遍歷結(jié)果
* @author Korbin
* @date 2023-02-06 14:25:42
**/
public List<T> deepFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
deepFirstTraverse(vertexList, visited, i);
}
return vertexList;
}
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @param vertexList 遍歷結(jié)果
* @param visited 訪問記錄
* @param index 待處理的下標(biāo)
* @author Korbin
* @date 2023-02-06 14:25:58
**/
public void deepFirstTraverse(List<T> vertexList, boolean[] visited, int index) {
// 找下標(biāo)為i的頂點關(guān)聯(lián)的邊中，關(guān)聯(lián)頂點下標(biāo)最小且未訪問的頂點
int minReleVertex = -1;
for (int j = 0; j < arc.length && vertexList.size() < vertexNum; j++) {
EdgeListEdgeNode<W> edgeNode = arc[j];
int begin = edgeNode.getBegin();
int end = edgeNode.getEnd();
switch (type) {
case UNDIRECTED:
case UNDIRECTED_NETWORK: {
if (begin == index && !visited[end]) {
if (minReleVertex == -1 || minReleVertex > end) {
minReleVertex = end;
}
} else if (end == index && !visited[begin]) {
if (minReleVertex == -1 || minReleVertex > begin) {
minReleVertex = begin;
}
}
break;
}
case DIRECTED:
case DIRECTED_NETWORK: {
if (begin == index && !visited[end]) {
if (minReleVertex == -1 || minReleVertex > end) {
minReleVertex = end;
}
}
break;
}
}
}
if (!visited[index]) {
// 訪問該頂點
visited[index] = true;
vertexList.add(vertex[index]);
}
if (minReleVertex != -1 && !visited[minReleVertex]) {
// 訪問該頂點的下標(biāo)最小的關(guān)聯(lián)頂點
visited[minReleVertex] = true;
vertexList.add(vertex[minReleVertex]);
// 接下來，訪問關(guān)聯(lián)頂點的“下標(biāo)最小的關(guān)聯(lián)頂點”
deepFirstTraverse(vertexList, visited, minReleVertex);
// 處理完畢后，應(yīng)繼續(xù)處理本頂點，即“下一個頂點沒有關(guān)聯(lián)的頂點，因此回退一步”
deepFirstTraverse(vertexList, visited, index);
}
}
4.2 廣度優(yōu)先遍歷
??廣度優(yōu)先遍歷（Breadth First Search），又稱為廣度優(yōu)先搜索，簡稱BFS，廣度優(yōu)先遍歷有點類似于樹的層序遍歷。
4.2.1 鄰接矩陣的廣度優(yōu)先遍歷
??考慮如下無向圖：
??廣度優(yōu)先遍歷的方法是：從下標(biāo)最小的頂點C開始，訪問C，然后找到它的下一層，訪問它的下一層，然后找到下一層的下一層，訪問它們，依此類推。
??在無向圖中我們這邊實現(xiàn)：
??(0) 我們先建一個隊列用于輔助；
??(1) 從頂點C開始，把它的下標(biāo)加入隊列，此時隊列里面只有C；
??(2) 從隊列中取出隊頭的數(shù)據(jù)，即C的下標(biāo)0，訪問C，然后迭代arc[0][j]，weight為1的依次加入隊列，此時隊列從尾到頭依次是B、A、D，已訪問列表里有{C}；
??(3) 從隊列中取出隊頭的數(shù)據(jù)，即D的下標(biāo)1，訪問D，然后迭代arc[1][j]，weight為1且未被訪問的依次加入隊列，此時隊列從尾到頭依次是A、B、A，已訪問列表里有{C, D}；
??(4) 從隊列中取出隊頭的數(shù)據(jù)，即A的下標(biāo)2，訪問A，然后迭代arc[2][j]，weight為1且未被訪問的依次加入隊列，此時隊列從尾到頭依次是B、A、B，已訪問列表里有{C, D, A}；
??(5) 從隊列中取出隊頭的數(shù)據(jù)，即B的下標(biāo)3，訪問B，然后迭代arc[3][j]，weight為1且未被訪問的依次加入隊列，此時隊列從尾到頭依次是F、B、A，已訪問列表里有{C, D, A, B}；
??(6) 從隊列中取出隊頭的數(shù)據(jù)，即A的下標(biāo)2，發(fā)現(xiàn)A已被訪問，跳過，此時隊列從尾到頭依次是F、B，已訪問列表里有{C, D, A, B}；
??(7) 從隊列中取出隊頭的數(shù)據(jù)，即B的下標(biāo)3，發(fā)現(xiàn)B已被訪問，跳過，此時隊列從尾到頭依次是F，已訪問列表里有{C, D, A, B}；
??(8) 從隊列中取出隊頭的數(shù)據(jù)，即F的下標(biāo)4，訪問F，然后迭代arc[4][j]，weight為1且未被訪問的依次加入隊列，此時隊列從尾到頭依次是E，已訪問列表里有{C, D, A, B, F}；
??(9) 從隊列中取出隊頭的數(shù)據(jù)，即E的下標(biāo)5，訪問E，這時發(fā)現(xiàn)所有頂點均已訪問完畢，結(jié)束遍歷，得到結(jié)果{C, D, A, B, F, E}；
??有向圖/網(wǎng)的實現(xiàn)類似，考慮如下有向網(wǎng)：
??遍歷過程如下所示：
??(1) 仍然使用一個輔助隊列，用于存儲頂點下標(biāo)，從下標(biāo)為0的頂點開始迭代，先將它入隊，此時隊列里面只有E；
??(2) 從隊列中取出隊頭數(shù)據(jù)，即E的下標(biāo)0，訪問它，迭代arc[0][j]，取出相關(guān)邊，有<E,A>，將A插入隊列，此時隊列里面只有A，已訪問頂點列表為{E}；
??(3) 從隊列中取出隊頭數(shù)據(jù)，即A的下標(biāo)3，訪問它，迭代arc[3][j]，取出相關(guān)邊，有<A,D>，將D插入隊列，此時隊列里面只有D，已訪問頂點列表為{E, A}；
??(4) 從隊列中取出隊頭數(shù)據(jù)，即D的下標(biāo)5，訪問它，迭代arc[5][j]，取出相關(guān)邊，有<D,F>、<D,C>、<D,B>，將F、C、B依次插入隊列，此時隊列從隊尾到隊頭依次是B、C、F，已訪問頂點列表為{E, A, D}；
??(5) 從隊列中取出隊頭數(shù)據(jù)，即F的下標(biāo)1，訪問它，迭代arc[1][j]，取出相關(guān)邊，沒有，不進(jìn)行處理，此時隊列從隊尾到隊頭依次是B、C，已訪問頂點列表為{E, A, D, F}；
??(6) 從隊列中取出隊頭數(shù)據(jù)，即C的下標(biāo)2，訪問它，迭代arc[2][j]，取出相關(guān)邊，有<C,E>、<C,B>，因為頂點E已被訪問，因此忽略它，把B加入到隊列，此時隊列從隊尾到隊頭依次是B、B，已訪問頂點列表為{E, A, D, F, C}；
??(7) 從隊列中取出隊頭數(shù)據(jù)，即B的下標(biāo)4，訪問它，發(fā)現(xiàn)所有頂點已訪問完畢，遍歷結(jié)束，得到結(jié)果{E, A, D, F, C, B}；
??代碼實現(xiàn)如下所示：
/**
* 對圖進(jìn)行廣度優(yōu)先遍歷
*
* @return 遍歷結(jié)果
* @author Korbin
* @date 2023-02-06 19:33:16
**/
public List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> queue = new LinkQueue<>();
queue.init();
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
if (!visited[i]) {
// 入隊列
LinkListNode<Integer> node = new LinkListNode<>();
node.setData(i);
queue.insert(node);
System.out.println("iterate " + vertex[i]);
while (!queue.isEmpty() && vertexList.size() < vertexNum) {
// 一個個取出來訪問，并把它們的下一層放入隊列
node = queue.delete();
int index = node.getData();
if (!visited[index]) {
vertexList.add(vertex[index]);
visited[index] = true;
System.out.println("in " + vertex[index]);
for (int j = 0; j < vertexNum && vertexList.size() < vertexNum; j++) {
if (j != index && !visited[j]) {
boolean canInsert = false;
switch (type) {
case UNDIRECTED:
case DIRECTED: {
// 無向圖和有向圖，weight為1表示頂點相關(guān)
try {
int weight = (int) arc[index][j];
if (weight == 1) {
canInsert = true;
}
} catch (NumberFormatException e) {
// do nothing
}
break;
}
case UNDIRECTED_NETWORK:
case DIRECTED_NETWORK: {
// 無向網(wǎng)和有向網(wǎng)，weight不為infinity表示頂點相關(guān)
if (!arc[index][j].equals(infinity)) {
canInsert = true;
}
}
}
if (canInsert) {
// 把下一層入隊
node = new LinkListNode<>();
node.setData(j);
queue.insert(node);
System.out.println("in queue " + vertex[j]);
}
}
}
}
}
}
}
return vertexList;
}
4.2.2 鄰接表的廣度優(yōu)先遍歷
??與鄰接矩陣相同，鄰接表的廣度優(yōu)先遍歷也借助隊列實現(xiàn)，其中，逆鄰接表的實現(xiàn)會更為復(fù)雜：
/**
* 對圖進(jìn)行廣度優(yōu)先遍歷
*
* @return 遍歷結(jié)果
* @author Korbin
* @date 2023-02-07 08:38:46
**/
public List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> queue = new LinkQueue<>();
queue.init();
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
System.out.println("iterate " + vertexes[i].getVertex());
if (!visited[i]) {
LinkListNode<Integer> node = new LinkListNode<>();
node.setData(i);
queue.insert(node);
System.out.println("insert " + vertexes[i].getVertex());
while (!queue.isEmpty() && vertexList.size() < vertexNum) {
// 出隊列
node = queue.delete();
System.out.println("get " + vertexes[node.getData()].getVertex());
int index = node.getData();
VertexNode<T, W> vertexNode = vertexes[index];
// 訪問該頂點
if (!visited[index]) {
vertexList.add(vertexNode.getVertex());
visited[index] = true;
System.out.println("visit " + vertexNode.getVertex());
if (!reverseAdjacency) {
// 鄰接表
// 把指向的頂點一一入隊
EdgeNode<W> edge = vertexNode.getFirstEdge();
while (edge != null && vertexList.size() < vertexNum) {
index = edge.getIndex();
if (!visited[index]) {
System.out.println("insert " + vertexes[index].getVertex());
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(index);
queue.insert(childNode);
}
edge = edge.getNext();
}
} else {
// 逆鄰表
// 把指向的頂點一一入隊
for (int j = 0; j < vertexNum && vertexList.size() < vertexNum; j++) {
if (j != index && !visited[j]) {
VertexNode<T, W> tmpVertex = vertexes[j];
EdgeNode<W> tmpEdge = tmpVertex.getFirstEdge();
while (null != tmpEdge && vertexList.size() < vertexNum) {
if (tmpEdge.getIndex() == index) {
// 入隊
System.out.println(tmpEdge.getIndex() + "=======" + index + "=======" + j);
System.out.println("insert " + vertexes[j].getVertex());
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(j);
queue.insert(childNode);
break;
}
tmpEdge = tmpEdge.getNext();
}
}
}
}
}
}
}
}
return vertexList;
}
4.2.3 十字鏈表的廣度優(yōu)先遍歷
??十字鏈表的實現(xiàn)與鄰接表的實現(xiàn)相同：
/**
* 對圖進(jìn)行廣度優(yōu)先遍歷
*
* @return 遍歷結(jié)果
* @author Korbin
* @date 2023-02-07 09:56:29
**/
public List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> queue = new LinkQueue<>();
queue.init();
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
System.out.println("iterate " + vertexes[i].getVertex());
if (!visited[i]) {
LinkListNode<Integer> node = new LinkListNode<>();
node.setData(i);
queue.insert(node);
System.out.println("insert " + vertexes[i].getVertex());
while (!queue.isEmpty() && vertexList.size() < vertexNum) {
// 出隊列
node = queue.delete();
System.out.println("get " + vertexes[node.getData()].getVertex());
int index = node.getData();
AcrossLinkVertexNode<T, W> vertexNode = vertexes[index];
// 訪問該頂點
if (!visited[index]) {
vertexList.add(vertexNode.getVertex());
visited[index] = true;
System.out.println("visit " + vertexNode.getVertex());
// 鄰接表
// 把指向的頂點一一入隊
AcrossLinkEdgeNode<W> edge = vertexNode.getFirstOut();
while (edge != null && vertexList.size() < vertexNum) {
index = edge.getHeadIndex();
if (!visited[index]) {
System.out.println("insert " + vertexes[index].getVertex());
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(index);
queue.insert(childNode);
}
edge = edge.getNextHead();
}
}
}
}
}
return vertexList;
}
4.2.4 鄰接多重表的廣度優(yōu)先遍歷
??上文有提到如何在鄰接多重表中尋找關(guān)聯(lián)的頂點，在進(jìn)行廣度遍歷時，同樣借助隊列實現(xiàn)：
/**
* 對圖進(jìn)行廣度優(yōu)先遍歷
*
* @return 遍歷結(jié)果
* @author Korbin
* @date 2023-02-07 10:03:26
**/
public List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> queue = new LinkQueue<>();
queue.init();
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
if (!visited[i]) {
System.out.println("iterate " + vertexes[i].getVertex());
// 入隊
LinkListNode<Integer> node = new LinkListNode<>();
node.setData(i);
queue.insert(node);
System.out.println("insert " + vertexes[i].getVertex());
while (!queue.isEmpty() && vertexList.size() < vertexNum) {
// 從隊列中取出
int index = queue.delete().getData();
System.out.println("get " + vertexes[index].getVertex());
if (!visited[index]) {
// 訪問它
AdjacencyMultiVertexNode<T, W> vertexNode = vertexes[index];
vertexList.add(vertexNode.getVertex());
visited[index] = true;
System.out.println("visit " + vertexNode.getVertex());
// 取index關(guān)聯(lián)的頂點
AdjacencyMultiEdgeNode<W> firstEdge = vertexNode.getFirstEdge();
if (null != firstEdge) {
int childIndex = firstEdge.getJVex();
if (!visited[childIndex]) {
// 相關(guān)頂點入隊
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(childIndex);
queue.insert(childNode);
System.out.println("insert " + vertexes[childIndex].getVertex());
}
AdjacencyMultiEdgeNode<W> edgeNode = firstEdge.getILink();
while (null != edgeNode && vertexList.size() < vertexNum) {
// 可能是iVex等于當(dāng)前頂點，也可能是jVex等于當(dāng)前頂點
int iVex = edgeNode.getIVex();
int jVex = edgeNode.getJVex();
if (iVex == index && !visited[jVex]) {
// 相關(guān)頂點是jVex
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(jVex);
queue.insert(childNode);
System.out.println("insert " + vertexes[jVex].getVertex());
} else if (jVex == index && !visited[iVex]) {
// 相關(guān)頂點是iVex
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(iVex);
queue.insert(childNode);
System.out.println("insert " + vertexes[iVex].getVertex());
}
edgeNode = edgeNode.getJLink();
}
}
}
}
}
}
return vertexList;
}
4.2.5 邊集數(shù)組的廣度優(yōu)先遍歷
??邊集數(shù)組仍然需要多次迭代邊集數(shù)組，才能找到相關(guān)的頂點：
/**
* 對圖進(jìn)行廣度優(yōu)先遍歷
*
* @return 遍歷結(jié)果
* @author Korbin
* @date 2023-02-07 10:30:36
**/
public List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> queue = new LinkQueue<>();
queue.init();
boolean[] visitedArc = new boolean[edgeNum];
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
if (!visited[i]) {
System.out.println("iterate " + vertex[i]);
// 入隊
LinkListNode<Integer> node = new LinkListNode<>();
node.setData(i);
queue.insert(node);
System.out.println("insert " + vertex[i]);
while (!queue.isEmpty() && vertexList.size() < vertexNum) {
// 取出
int index = queue.delete().getData();
System.out.println("get " + vertex[index]);
if (!visited[index]) {
// 訪問它
vertexList.add(vertex[index]);
visited[index] = true;
System.out.println("visit " + vertex[index]);
// 找它相關(guān)的頂點或指向的頂點
switch (type) {
case UNDIRECTED:
case UNDIRECTED_NETWORK: {
// 無向圖/網(wǎng)
for (int j = 0; j < edgeNum && vertexList.size() < vertexNum; j++) {
if (!visitedArc[j]) {
System.out.println("iterate arc " + j);
EdgeListEdgeNode<W> edge = arc[j];
int begin = edge.getBegin();
int end = edge.getEnd();
if (begin == index) {
if (!visited[end]) {
// 入隊
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(end);
queue.insert(childNode);
System.out.println("insert " + vertex[end]);
}
} else if (end == index) {
if (!visited[begin]) {
// 入隊
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(begin);
queue.insert(childNode);
System.out.println("insert " + vertex[begin]);
}
}
if (visited[begin] && visited[end]) {
visitedArc[j] = true;
}
}
}
break;
}
case DIRECTED:
case DIRECTED_NETWORK: {
for (int j = 0; j < edgeNum && vertexList.size() < vertexNum; j++) {
if (!visitedArc[j]) {
System.out.println("iterate arc " + j);
EdgeListEdgeNode<W> edge = arc[j];
int begin = edge.getBegin();
int end = edge.getEnd();
if (begin == index && !visited[end]) {
// 入隊
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(end);
queue.insert(childNode);
System.out.println("insert " + vertex[end]);
}
if (visited[begin] && visited[end]) {
visitedArc[j] = true;
}
}
}
break;
}
}
}
}
}
}
return vertexList;
}
??注意，邊集數(shù)組若不進(jìn)行特殊處理的話，每一層的頂點順序取決于邊集數(shù)組中結(jié)點順序的定義。，如下有向網(wǎng)：
??若定義為如下邊集數(shù)組時：
??廣度優(yōu)先遍歷過程為：
??廣度優(yōu)先遍歷結(jié)果為EADBFC。
??但如果把邊集數(shù)組的定義做一些調(diào)整：
??廣度優(yōu)先遍歷過程為：
??遍歷結(jié)果為EADCBF，與之前的遍歷結(jié)果并不相同。
??當(dāng)然，你也可以選擇在取出所有相關(guān)的頂點后，對這些頂點按下標(biāo)排序，那么廣度優(yōu)先遍歷的結(jié)果就是固定的了，與邊集數(shù)組中結(jié)點的順序無關(guān)。文章來源：http://www.zghlxwxcb.cn/news/detail-756563.html
??注：本文為程 杰老師《大話數(shù)據(jù)結(jié)構(gòu)》的讀書筆記，其中一些示例和代碼是筆者閱讀后自行編制的。文章來源地址http://www.zghlxwxcb.cn/news/detail-756563.html
到了這里，關(guān)于大話數(shù)據(jù)結(jié)構(gòu)-圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
