图的遍历

图的遍历

1462756149

由于一系列的原因，早上我要去找老师给我买票，所以我要去上课！并非出自我本意，本学期的数据结构就上过第一周的2节课，今天是第二次来上的课。

嗯，是的，来了就应该听听，今天讲的是图，说到图的遍历，还提了一下DFS,BFS深度广度搜索法，但是没具体讲，于是，在他讲课的时候我又用DFS,BFS水了一段代码。
问题描述

图的遍历

如图

1.深度优先遍历(DFS)

基本思想：首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程。

其深度优先遍历得到的序列为：

0->1->3->7->4->2->5->6

2.广度优先遍历(BFS)

基本思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。

其广度优先遍历得到的序列为：

0->1->2->3->4->5->6->7

解题思路

遍历，可以采用dfs，bfs，可以使用一个二维数组记录顶点与顶点的关系，例如map[1][2] = 1,map[2][1] = 0, 那就可以表示顶点1->2(1可以通向2,2不能通向1)，map[3][4] = 1,map[4][3] = 1,可以表示为3-4，互通。然后再用一个一位数组标记遍历过的顶点。
代码实现

public class Graph {

static final int MAX = 100;
static int[][] map = new int[MAX][MAX];
static int[] vis = new int[MAX];
static int v; // 顶点数

static void dfs(int n) {
    if (n == v)
        return;
    vis[n] = 1; // 标记第n个顶点
    System.out.print(n + "->");
    for (int i = 0; i < v; i++)
        if (map[n][i] == 1 && vis[i] == 0) // 当第i个顶点与n顶点相通，且i顶点未标记则以i顶点继续遍历
            dfs(i);
}

static void bfs() {
    Queue<Integer> queue = new LinkedList<Integer>();
    // 把开始遍历的顶点加入队列并标记
    queue.offer(0);
    vis[0] = 1;
    System.out.print(0);
    while (!queue.isEmpty()) {
        int top = queue.poll();// 出列
        for (int i = 0; i < v; i++)
            if (map[top][i] == 1 && vis[i] == 0) {
                System.out.print("->" + i);
                // 标记入列
                vis[i] = 1;
                queue.offer(i);
            }
    }
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    v = scanner.nextInt();
    int i, j;
    // 默认输入为无向图
    while (scanner.hasNext()) {
        i = scanner.nextInt();
        j = scanner.nextInt();
        if (i <= v && j <= v && i >= 0 && j >= 0 && map[i][j] == 0) {
            map[i][j] = 1;
            map[j][i] = 1;
        } else
            break;
    }
    // dfs(0);
    bfs();
    scanner.close();
}

}