有向图的深度和广度遍历_有向图的深度遍历

题目要求：

1．对于下图所示的有向图(访问顺序按序号从小到大)，试写出： 

(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；

(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树。

package com.test.tree;
import java.util.*;
 
public class Graph {
    // 存储节点信息
    private Object[] vertices;
    // 存储边的信息
    private int[][] arcs;
    private int vexnum;
    // 记录第i个节点是否被访问过
    private boolean[] visited;
 
    /**
     * @param args
     */
    public static void main(String[] args) {
        Graph g = new Graph(5);
        Character[] vertices = { '1', '2', '3', '4', '5'};
        g.addVertex(vertices);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(4, 0);
 
 
        System.out.println("深度优先遍历：");
        g.depthTraverse();
        System.out.println();
 
        System.out.println("广度优先遍历：");
        g.broadTraverse2(1);
        System.out.println();
 
    }
 
    public Graph(int n) {
        vexnum = n;
        vertices = new Object[n];
        arcs = new int[n][n];
        visited = new boolean[n];
        for (int i = 0; i < vexnum; i++) {
            for (int j = 0; j < vexnum; j++) {
                arcs[i][j] = 0;
            }
        }
 
    }
 
    public void addVertex(Object[] obj) {
        this.vertices = obj;
    }
 
    public void addEdge(int i, int j) {
        if (i == j)return;
        arcs[i][j] = 1;    //单独一条表示有向图
        //arcs[j][i] = 1;   // 这一条打开是无线图
    }
 
    public int firstAdjVex(int i) {
        for (int j = 0; j < vexnum; j++) {
            if (arcs[i][j] > 0)
                return j;
        }
        return -1;
    }
 
    public int nextAdjVex(int i, int k) {
        for (int j = k + 1; j < vexnum; j++) {
            if (arcs[i][j] > 0)
                return j;
        }
        return -1;
    }
 
    // 深度优先遍历
    public void depthTraverse() {
        for (int i = 0; i < vexnum; i++) {
            visited[i] = false;
        }
 
 
        for (int i = 0; i < vexnum; i++) {
            if (!visited[i])
                traverse(i);
        }
    }
 
    // 一个连通图的深度递归遍历
    public void traverse(int i) {
        // TODO Auto-generated method stub
        visited[i] = true;
        visit(i);
        for (int j = this.firstAdjVex(i); j >= 0; j = this.nextAdjVex(i, j)) {
            if (!visited[j])
                this.traverse(j);
        }
    }
 
    // 广度优先遍历  任意节点开始，这里是第二节点开始
    public void broadTraverse2(int n) {
        // LinkedList实现了Queue接口
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < vexnum; i++) {
            visited[i] = false;
        }
        if (!visited[n]) {
                q.add(n);
                visited[n] = true;
                visit(n);
                while (!q.isEmpty()) {
                    int j = (Integer) q.remove().intValue();
                    int k = this.firstAdjVex(j);
                    for ( k = this.firstAdjVex(j); k >= 0; k = this
                            .nextAdjVex(j, k)) {
                        if (!visited[k]) {
                            q.add(k);
                            visited[k] = true;
                            visit(k);
                        }
                    }
 
                }
            }
    }
 
    // 广度优先遍历  默认从0开始
    public void broadTraverse(int n) {
        // LinkedList实现了Queue接口
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < vexnum; i++) {
            visited[i] = false;
        }
        for (int i = 0; i < vexnum; i++) {
            if (!visited[i]) {
                q.add(i);
                visited[i] = true;
                visit(i);
                while (!q.isEmpty()) {
                    int j = (Integer) q.remove().intValue();
                    for (int k = this.firstAdjVex(j); k >= 0; k = this
                            .nextAdjVex(j, k)) {
                        if (!visited[k]) {
                            q.add(k);
                            visited[k] = true;
                            visit(k);
                        }
                    }
 
                }
            }
        }
    }
 
    private void visit(int i) {
        // TODO Auto-generated method stub
        System.out.print(vertices[i] + " ");
    }
 
 
    // 最后一个
    public int lastAdjVex(int i) {
        for (int j = vexnum - 1; j >= 0; j--) {
            if (arcs[i][j] > 0)
                return j;
        }
        return -1;
    }
 
    // 上一个
    public int lastAdjVex(int i, int k) {
        for (int j = k - 1; j >= 0; j--) {
            if (arcs[i][j] > 0)
                return j;
        }
        return -1;
    }
}