一、流程图

本题示例用关联前向边存储图

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）
图的深度优先遍历（递归、非递归；邻接表，邻接矩阵）