學(xué)號(hào)：20011210126
姓名：劉巖哲
轉(zhuǎn)載自：https://www.cnblogs.com/Unicron/p/10849942.html
【嵌牛導(dǎo)讀】
深度優(yōu)先搜索（縮寫DFS）有點(diǎn)類似廣度優(yōu)先搜索锦秒，也是對(duì)一個(gè)連通圖進(jìn)行遍歷的算法平道。它的思想是從一個(gè)頂點(diǎn)V0開(kāi)始，沿著一條路一直走到底阶祭，如果發(fā)現(xiàn)不能到達(dá)目標(biāo)解犀农，那就返回到上一個(gè)節(jié)點(diǎn)寒锚，然后從另一條路開(kāi)始走到底宠哄，這種盡量往深處走的概念即是深度優(yōu)先的概念。
【嵌牛鼻子】深度優(yōu)先搜索（DFS）思路及算法分析
【嵌牛正文】
1禽最、算法用途
用于遍歷圖中的節(jié)點(diǎn)腺怯，有些類似于樹的深度優(yōu)先遍歷。這里唯一的問(wèn)題是川无，與樹不同呛占，圖形可能包含循環(huán)，因此我們可能會(huì)再次來(lái)到同一節(jié)點(diǎn)懦趋。
2晾虑、主要思想
借用一個(gè)鄰接表和布爾類型數(shù)組（判斷一個(gè)點(diǎn)是否查看過(guò)，用于避免重復(fù)到達(dá)同一個(gè)點(diǎn)愕够，造成死循環(huán)等）走贪，先將所有點(diǎn)按一定次序存入鄰接表，再通過(guò)迭代器惑芭，對(duì)鄰接表的linklist和布爾數(shù)組做出操作坠狡，從而達(dá)到不重復(fù)遞歸遍歷的效果。
（鄰接表是表示了圖中與每一個(gè)頂點(diǎn)相鄰的邊集的集合遂跟，這里的集合指的是無(wú)序集）
3逃沿、代碼（java）
(以上圖為例的代碼）
//深度優(yōu)先搜索
import java.io.*;
import java.util.*;
//This class represents a directed graph using adjacency list
//representation
class Graph
{
private int V; // No. of vertices
// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];
// Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v's list.
}
// A function used by DFS
void DFSUtil(int v,boolean visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v+" ");
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
DFSUtil(n,visited);
}
}
// The function to do DFS traversal. It uses recursive DFSUtil()
void DFS()
{
// Mark all the vertices as not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];
// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
for (int i=0; i<V; ++i)
if (visited[i] == false)
DFSUtil(i, visited);
}
public static void main(String args[])
{
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Following is Depth First Traversal");
g.DFS();
}
}
4婴渡、復(fù)雜度分析
DFS復(fù)雜度分析 DFS算法是一一個(gè)遞歸算法，需要借助一個(gè)遞歸工作棧凯亮，故它的空問(wèn)復(fù)雜度為O(V）边臼。 遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程，其耗費(fèi)的時(shí)間取決于所采用結(jié)構(gòu)假消。 鄰接表表示時(shí)柠并，查找所有頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(E)，訪問(wèn)頂點(diǎn)的鄰接點(diǎn)所花時(shí)間為O（V）,此時(shí)富拗，總的時(shí)間復(fù)雜度為O(V+E)臼予。
