# 有向图的深度优先遍历算法的快速实现及应用

+关注继续查看

Key 表示顶点的标识，如，"hap","peg"....

Value 表示顶点的邻接表。如，顶点"hap"的邻接表是 <"pmg","peg">

1         Map<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>(arr.length);//根据字符串数组arr构造图
2
3         for (String str : arr) {
4             graph.put(str, new ArrayList<String>());
5         }

 1                 if(start.charAt(startLen-1) == end.charAt(0))//start-->end
2                 {
7                 }else if(start.charAt(0) == end.charAt(endLen-1)){//end-->start
12                 }

1         ArrayList<String> paths = new ArrayList<>(graph.size());//保存访问路径
2
3         HashSet<String> visited = new HashSet<>(graph.size());//用来判断某个顶点是否已经访问了
5
6         stack.push(start);
8         visited.add(start);

 1         while(!stack.isEmpty())
2         {
3             String next = null;//下一个待遍历的顶点
4             String currentVertex = stack.peek();//当前正在遍历的顶点
7             {
8                 for (String vertex : adjs) {
9                     if(!visited.contains(vertex))//vertex 未被访问过
10                     {
11                         next = vertex;
12                         break;
13                     }
14                 }
15             }//end if
16
17             if(next != null)//当前顶点还有未被访问的邻接点
18             {
20                 stack.push(next);
22             }else{
23                 stack.pop();//回退
24             }
25         }//end while

 1         //从图中的每一个顶点开始DFS遍历
2         for (String v : vertexs) {
3             paths = dfs(graph, v);
4
5             if(paths.size() == graph.size())//从 顶点 v 遍历 能够遍历完图中所有的顶点.
6             {
7                 System.out.println("从顶点: " + v + " 开始DFS遍历能够遍历完所有的顶点,路径如下:");
8                 printPath(paths, graph);
9                 result = true;
10                 break;
11             }
12         }

 1     public static ArrayList<String> dfs_recu(String start, Map<String, ArrayList<String>> graph)
2     {
3         ArrayList<String> paths = new ArrayList<>();//保存访问路径
4         HashSet<String> visited = new HashSet<>();//保存顶点的访问状态
5         dfsrecuresive(start, graph, paths, visited);//递归DFS
6         return paths;//返回本次DFS的访问路径
7     }
8     private static void dfsrecuresive(String start, Map<String, ArrayList<String>> graph, ArrayList<String> paths, HashSet<String> visited)
9     {
12
14             for (String v : adjs) {
15                 if(!visited.contains(v))//如果 start顶点的邻接表中还有未被访问的顶点
16                     dfsrecuresive(v, graph, paths, visited);//递归访问该未被访问的顶点v
17             }
18     }

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
* 有向图的深度优先遍历实现 在深度遍历中，是否存在一条路径包含了图中所有的顶点??
*
* @author psj
*
*/
public class DFSOrder {

public static Map<String, ArrayList<String>> buildGraph(String[] arr) {
Map<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>(
arr.length);

for (String str : arr) {
graph.put(str, new ArrayList<String>());
}

String start;
int startLen;
String end;
int endLen;
for (int i = 0; i < arr.length; i++) {
start = arr[i];
startLen = start.length();
if (startLen == 0)
continue;
for (int j = 0; j < arr.length; j++) {
end = arr[j];
endLen = end.length();
if (endLen == 0)
continue;
if (start.charAt(startLen - 1) == end.charAt(0))// start-->end
{
} else if (start.charAt(0) == end.charAt(endLen - 1)) {// end-->start
}
}
}
return graph;
}

/**
* 从start顶点开始,对graph进行DFS遍历(非递归)
*
* @param graph
* @param start
* @return DFS遍历顺序
*/
public static ArrayList<String> dfs(Map<String, ArrayList<String>> graph,
String start) {

assert graph.keySet().contains(start);// 假设 start 一定是图中的顶点
ArrayList<String> paths = new ArrayList<>(graph.size());

HashSet<String> visited = new HashSet<>(graph.size());// 用来判断某个顶点是否已经访问了

stack.push(start);

while (!stack.isEmpty()) {
String next = null;// 下一个待遍历的顶点
String currentVertex = stack.peek();// 当前正在遍历的顶点
for (String vertex : adjs) {
if (!visited.contains(vertex))// vertex 未被访问过
{
next = vertex;
break;
}
}
}// end if

if (next != null)// 当前顶点还有未被访问的邻接点
{
stack.push(next);
} else {
stack.pop();// 回退
}
}// end while
return paths;
}

// 打印从某个顶点开始的深度优先遍历路径
public static void printPath(ArrayList<String> paths,
Map<String, ArrayList<String>> graph) {
System.out.println("dfs path:");
for (String v : paths) {
System.out.print(v + " ");
}
System.out.println();
}

// 判断有向图中是否存在某顶点，从该顶点进行DFS遍历，能够遍历到图中所有的顶点
public static boolean containsAllNode(Map<String, ArrayList<String>> graph) {
boolean result = false;

ArrayList<String> paths = null;
Set<String> vertexs = graph.keySet();
// 从图中的每一个顶点开始DFS遍历
for (String v : vertexs) {
paths = dfs(graph, v);

if (paths.size() == graph.size())// 从 顶点 v 遍历 能够遍历完图中所有的顶点.
{
System.out.println("从顶点: " + v + " 开始DFS遍历能够遍历完所有的顶点,路径如下:");
printPath(paths, graph);
result = true;
break;
}
}
return result;
}

// hapjin test
public static void main(String[] args) {
// String[] words = {"me","cba","agm","abc","eqm","cde"};

String[] words = { "abc", "cde", "efg", "che" };
Map<String, ArrayList<String>> graph = buildGraph(words);
System.out.println(containsAllNode(graph));
}
}
View Code

|
2月前
|

33 0
|
8月前
|

rapidio 网络枚举--深度优先遍历算法
rapidio 网络枚举--深度优先遍历算法
48 0
|
8月前
|

71 0
|

|

|

|

952 0