图的深度优先遍历（非递归）
2018-11-13 本文已影响154人
四喜汤圆
一、流程图
本题示例用关联前向边存储图
Q：访问了节点i后，如何找到下一个可访问节点
A：若该节点有未被访问的邻接节点，则任选一个进行访问；若该节点没有未被访问的邻接节点，则找到最新被访问的节点latestNode，找到节点latestNode的任一未被访问节点进行访问
Q：如何找到某节点的所有邻接节点
A：在关联前向边存储结构中每个
Node对象中存储了1）count:从该节点中发出的边；2）该节点发出的第一条边在数组linkedEdges中存储的下标。故遍历该节点发出的所有边，然后找到每条边的exitNodeId，即找到了该节点的所有邻接节点
int beginIndex = g.nodes[curIndex].linkEdgesBeginIndex;
int count = g.nodes[curIndex].count;
// 遍历该节点发出的所有边
for (int i = beginIndex; i < beginIndex + count; i++) {
int linkNodeNum = g.edges[g.linkedEdges[i]].exitNode.nodeId;
int linkNodeIndex = getIndex(g, linkNodeNum);
if (curIndex == -1) {
System.out.println("邻接节点编号错误");
return;
}
}
Q：如何判断某一节点是否被访问过
A：为每个顶点设立访问标志。（建立一个
boolean数组，用于存储数组下标对应位置的节点的访问情况）
boolean[] set = new boolean[g.n];
二、代码
1.输入说明
本例输入如下无向图
// 节点个数、边个数（本例是按照有向图来存储图，故下图中的无向图来说有20条边）
9 20
// 一下9行代表节点信息：(节点编号 节点名称)
10 A
11 B
12 C
13 D
14 E
15 F
16 G
17 H
18 I
// 以下10行代表边信息：(起始节点编号 终止节点编号)
10 11
10 12
11 13
11 14
12 15
12 16
15 16
13 17
14 17
17 18
// 从哪个编号的节点开始遍历
10
2.示例代码
非递归深度优先遍历
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
/**
* <pre>
* author : 杨丽金
* time : 2018/11/13
* desc :
* version: 1.0
* </pre>
*/
public class Travel {
public static void main(String[] args) {
new Travel().exe();
}
Scanner scan = new Scanner(System.in);
public void exe() {
MyGraph g = createMyGraph();
int startNum = scan.nextInt();
dfs_NonRecursive(g, startNum);
}
public MyGraph createMyGraph() {
// 节点数
int N = scan.nextInt();
// 边数
int M = scan.nextInt();
MyGraph g = new MyGraph(N, M);
// 节点信息
for (int i = 0; i < N; i++) {
MyGraph.Node node = new MyGraph.Node();
node.nodeId = scan.nextInt();
node.nodeName = scan.next();
g.nodes[i] = node;
}
// 边信息
for (int i = 0; i < M; i += 2) {
int index1 = scan.nextInt();
int index2 = scan.nextInt();
MyGraph.Edge edge = new MyGraph.Edge();
edge.enterNode = new MyGraph.Node(index1);
edge.exitNode = new MyGraph.Node(index2);
g.edges[i] = edge;
MyGraph.Edge edge2 = new MyGraph.Edge();
edge2.enterNode = new MyGraph.Node(index2);
edge2.exitNode = new MyGraph.Node(index1);
g.edges[i + 1] = edge2;
}
// 边关联信息
// 将节点按照节点编号升序排列，边集按照起始节点的编号升序排列
Arrays.sort(g.nodes);
Arrays.sort(g.edges);
int k = 0;// linkedEdges[]中可用的最新位置
int index = 0;// 上一节点搜索结束后在弧集中的索引
for (int i = 0; i < N; i++) {
// 对于每一个节点：从弧集中找出从该节点发出的弧
MyGraph.Node node = g.nodes[i];
int count = 0;
int beginIndex = k;
while (index < g.edges.length && g.edges[index].enterNode.nodeId == node.nodeId) {
// 如果是该节点发出的弧
count++;// 个数加1
// g.linkedEdges[k++]=g.edges[index].edgeId;// 将该弧存起来
g.linkedEdges[k++] = index;// 将该弧在数组中的下标存起来
index++;// 判断下一个弧如何
}
// 所有的弧都判断完后
if (count == 0) {
// 该节点没有任何弧发出
node.count = 0;
node.linkEdgesBeginIndex = -1;
} else {
node.count = count;
node.linkEdgesBeginIndex = beginIndex;
}
}
return g;
}
/**
* 非递归的方法深度优先遍历
*
* @param g
* @param vNum
*/
public void dfs_NonRecursive(MyGraph g, int vNum) {
boolean[] set = new boolean[g.n];
Stack<Integer> stack = new Stack<>();
// 最新被访问的节点在数组中的小标
int curIndex = getIndex(g, vNum);
if (curIndex == -1) {
System.out.println("源节点编号输入错误，不在范围内");
return;
}
// 访问源节点
set[curIndex] = true;
visit(g, curIndex);
stack.push(curIndex);
while (true) {
// 遍历该节点的邻接节点
int beginIndex = g.nodes[curIndex].linkEdgesBeginIndex;
int count = g.nodes[curIndex].count;
int nextIndex = -1;
for (int i = beginIndex; i < beginIndex + count; i++) {
int linkNodeNum = g.edges[g.linkedEdges[i]].exitNode.nodeId;
int linkNodeIndex = getIndex(g, linkNodeNum);
if (curIndex == -1) {
System.out.println("邻接节点编号错误");
return;
}
if (!set[linkNodeIndex]) {
// 未被访问，则访问
set[linkNodeIndex] = true;
visit(g, linkNodeIndex);
stack.push(linkNodeIndex);
nextIndex = linkNodeIndex;
curIndex = linkNodeIndex;
break;
}
}
if (nextIndex == -1) {
// 该节点的邻接节点都被访问了
if (stack.isEmpty()) {
return;// 遍历结束
} else {
// stack.pop();
curIndex = stack.pop();
}
}
}
}
/**
* 访问数组nodes中下标为curIndex的节点
*
* @param g
* @param curIndex
*/
private void visit(MyGraph g, int curIndex) {
System.out.println(g.nodes[curIndex].nodeId + ":" + g.nodes[curIndex].nodeName);
}
/**
* 得到编号为vNum的节点在数组nodes中存储的下标（二分查找）
*
* @param g
* @param vNum
* @return
*/
private int getIndex(MyGraph g, int vNum) {
int low = 0;
int high = g.nodes.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (g.nodes[mid].nodeId == vNum) {
return mid;
} else if (g.nodes[mid].nodeId < vNum) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}
图的存储结构
package road;
import java.util.Arrays;
import java.util.List;
/**
* <pre>
* author : 杨丽金
* time : 2018/10/30
* desc : 前向边存储结构
* version: 1.0
* </pre>
*/
public class MyGraph {
// 节点个数
public int n;
// 边个数
public int e;
// 结点集合
public Node[] nodes;
// 所有节点发出的所有边（按照特定的顺序排列起来）
public int[] linkedEdges;
// 边集合
public Edge[] edges;
public MyGraph(){}
@Override
public String toString() {
return "MyGraph{" +
"n=" + n +
", e=" + e +
", nodes=" + Arrays.toString(nodes) +
", linkedEdges=" + Arrays.toString(linkedEdges) +
", edges=" + Arrays.toString(edges) +
'}';
}
public MyGraph(int n, int e){
this.n=n;
this.e=e;
// 从数组下标0开始存储
nodes=new Node[n];
edges=new Edge[e];
linkedEdges=new int[e];
}
public static class Node implements Comparable<Node>{
// 节点编号
public int nodeId;
// 节点名称
public String nodeName;
// 经度
public float longtitude;
// 纬度
public float latitude;
// TODO: 2018/10/30 节点类型
public int type;
// 是否有红绿灯
public boolean hasLed;
// 从该节点发出的弧个数
public int count;
// 该节点发出的第一个弧在linkEdges中的下标
public int linkEdgesBeginIndex;
// 该节点处的转向限制
public List<ForbiddenTurn> forbiddenTurnList;
// 该节点数据是否为手动采集
public boolean fromManual;
public Node(){}
public Node(int nodeId) {
this.nodeId = nodeId;
}
@Override
public String toString() {
return "Node{" +
"nodeId=" + nodeId +
", nodeName='" + nodeName + '\'' +
", longtitude=" + longtitude +
", latitude=" + latitude +
", type=" + type +
", hasLed=" + hasLed +
", count=" + count +
", linkEdgesBeginIndex=" + linkEdgesBeginIndex +
", forbiddenTurnList=" + forbiddenTurnList +
", fromManual=" + fromManual +
'}';
}
// 定义默认访问规则
@Override
public int compareTo(Node o) {
return this.nodeId-o.nodeId;
}
}
public static class Edge implements Comparable<Edge>{
// 路段编号
public int edgeId;
// 路段名称
public String edgeName;
// 道路长度
public double length;
// 道路宽度
public double width;
// 车道数
public int laneNum;
// 道路等级：高速公路、国道、省道、县道、乡道、城市快速路等
// 开始节点编号
public Node enterNode;
// 结束节点编号
public Node exitNode;
// TODO: 2018/10/30 路段属性
// TODO: 2018/10/30 路段权值
// 路段权值
public double weight;
// 该道路是否连通
public boolean isConnected;
// 是否为手动采集
public boolean fromManual;
public Node point1;
public Node point2;
public Node point3;
public Node point4;
public Edge() {
}
/*public Edge(int edgeId, int enterNodeNum, int exitNodeNum, double weight) {
this.edgeId = edgeId;
this.enterNodeId = enterNodeNum;
this.exitNodeId = exitNodeNum;
this.weight = weight;
}*/
@Override
public String toString() {
return "Edge{" +
"edgeId=" + edgeId +
", edgeName='" + edgeName + '\'' +
", length=" + length +
", width=" + width +
", laneNum=" + laneNum +
", enterNode=" + enterNode +
", exitNode=" + exitNode +
", weight=" + weight +
", isConnected=" + isConnected +
", fromManual=" + fromManual +
'}';
}
@Override
public int compareTo(Edge o) {
return this.enterNode.nodeId -o.enterNode.nodeId;
}
}
public static class ForbiddenTurn {
// 结点编号
public int nodeId;
// 进节点编号
public int enterNodeId;
// 出节点编号
public int exitNodeId;
public ForbiddenTurn(){}
public ForbiddenTurn(int num, int enterNodeNum, int exitNodeNum) {
this.nodeId = num;
this.enterNodeId = enterNodeNum;
this.exitNodeId = exitNodeNum;
}
@Override
public String toString() {
return "ForbiddenTurn{" +
"nodeId=" + nodeId +
", enterNodeId=" + enterNodeId +
", exitNodeId=" + exitNodeId +
'}';
}
}
}
3.输出结果
10:A
11:B
13:D
17:H
14:E
18:I
12:C
15:F
16:G
参考文献
图的遍历（深度优先搜索）
图的遍历（搜索）算法（深度优先算法DFS和广度优先算法BFS）
图的深度优先遍历（递归、非递归；邻接表，邻接矩阵）
