對(duì)于圖的操作，最基本的就是對(duì)圖的遍歷了韩玩，圖的遍歷主要有兩種思想惭每，一種是DFS（Deepth First Search）深度優(yōu)先遍歷，另外一種是BFS（Breadth First Search）廣度優(yōu)先遍歷
-
DFS
-
算法特點(diǎn)：DFS算法鳖擒，從名字中就可以得出信息，深度優(yōu)先的烫止，那么在算法的執(zhí)行過(guò)程中蒋荚，總是將沿著一條路徑一直深入，直到?jīng)]有路徑了再返回查看其他路徑馆蠕∑谏可以看出惊奇，DFS算法是一種遞歸的過(guò)程，我們?cè)俾?lián)想到樹(shù)的遍歷中吓妆，其實(shí)DFS算法就是樹(shù)的先序遍歷赊时。
-
算法具體代碼：
int graph[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N] = { 0, };
void DFS(int start)
{
visited[start] = 1;
for (int i = 0; i < N; i++)
{
if (!visited[i] && graph[start][i] == 1) // 找到相鄰的點(diǎn)，同時(shí)這個(gè)點(diǎn)沒(méi)有被訪(fǎng)問(wèn)過(guò)
DFS(i);
}
cout << start << " ";
}
int main()
{
for (int i = 0; i < N; i++)
{
if (!visited[i])
DFS(i);
}
return 0;
}
* 算法分析：由于是遞歸調(diào)用行拢，那么每次遞歸都是一個(gè)單元祖秒，這個(gè)單元需要做的事情就是去找相鄰的沒(méi)有訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)，對(duì)這個(gè)節(jié)點(diǎn)重復(fù)遞歸舟奠，而去尋找這樣的節(jié)點(diǎn)就是遞歸的終止條件竭缝，即是如果沒(méi)有找到這樣的點(diǎn)，那么遞歸終止沼瘫，返回上一層調(diào)用
* **非遞歸版**
* 具體代碼：
int graph[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N] = { 0, };
void DFS(int start)
{
stack<int> s; // 使用一個(gè)棧進(jìn)行輔助
s.push(start);
visited[start] = 1;
bool isPush = false;
while (!s.empty())
{
isPush = false;
int v = s.top();
for (int i = 0; i < N; i++)
{
if (graph[v][i] == 1 && !visited[i])
{
visited[i] = 1;
s.push(i);
isPush = true;
break; // 找到了一個(gè)符合節(jié)點(diǎn)就先彈出當(dāng)前位置
}
}
if (!isPush)
{
cout << v << " ";
s.pop();
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (!visited[i])
DFS(i);
}
return 0;
}
* 算法分析：非遞歸的情況下抬纸，使用迭代的思想，需要借助一個(gè)棧去模擬遞歸的過(guò)程耿戚，然后用while循環(huán)進(jìn)行控制湿故，在非遞歸的情況下需要去手動(dòng)加上兩個(gè)東西：
* 終止條件：利用一個(gè)標(biāo)記來(lái)作控制，用來(lái)控制找不到點(diǎn)的情況
* 棧行為：如果找到一個(gè)符合的點(diǎn)膜蛔，那么就將其壓入棧坛猪，并且彈出本次循環(huán)，如果遇到終止條件皂股，那么就將目前的棧彈出一個(gè)
-
BFS
-
算法特點(diǎn)：BFS從字面上來(lái)理解就是廣度搜索墅茉，與深度搜索不同的是，BFS會(huì)將每個(gè)節(jié)點(diǎn)的周?chē)蠗l件的節(jié)點(diǎn)都遍歷之后才會(huì)繼續(xù)向下遍歷呜呐，BFS實(shí)際上和樹(shù)的層序遍歷很像就斤。
-
算法實(shí)際代碼：
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
int visited[N + 1] = { 0, };
void BFS(int start)
{
queue<int> Q;
Q.push(start);
visited[start] = 1;
while (!Q.empty())
{
int front = Q.front();
cout << front << " ";
Q.pop();
for (int i = 1; i <= N; i++)
{
if (!visited[i] && maze[front - 1][i - 1] == 1)
{
visited[i] = 1;
Q.push(i);
}
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
BFS(i);
}
return 0;
}
-
算法分析：
BFS實(shí)際上市借助了隊(duì)列這種結(jié)構(gòu)，對(duì)于每個(gè)節(jié)點(diǎn)蘑辑，都將它相鄰的同時(shí)符合條件的節(jié)點(diǎn)壓入到隊(duì)列中洋机，然后在遍歷完這個(gè)節(jié)點(diǎn)的時(shí)候就將這個(gè)節(jié)點(diǎn)給壓出隊(duì)列
