【数据结构与算法之图结构】图的遍历-蒲公英云

【数据结构与算法之图结构】图的遍历

文章目录

- - 【数据结构与算法之图结构】图的遍历
  - - - 1 深度优先搜索遍历
      - 2 广度优先搜索遍历

1 深度优先搜索遍历

深度优先，从图中一个顶点出发，先访问该顶点，再依次从该顶点未被访问过的邻接点开始继续深搜，递归。

Java代码实现：

// 定义一个成员变量数组, 记录遍历图时已访问的节点
int[] visited;
/**
 * 从vNodes[vIndex] 节点开始深度优先遍历
 *
 * @param vIndex
 */
private void DFS(int vIndex) {
    visit(vIndex); // 访问打印vIndex 节点数据信息
    visited[vIndex] = 1;  // 置1表示已经访问过
    // 找到顶点v 的第1个邻接点, 如果有返回顶点下标，如果没有，返回-1
    int w = getFirstAdj(vIndex);
    while (w != -1) {
        if (visited[w] == 0) {
     // 该顶点未被访问
            DFS(w); // 递归深搜
        }
        // 找到顶点v的 下一个邻接点
        w = getNextAdj(vIndex, w);
    }
}
/**
 * 主算法
 */
public void travelByDFS() {
    // 创建访问数组, 记录已访问节点
    visited = new int[vNodes.length];
    for (int i = 0; i < vNodes.length; i++) {
        visited[i] = 0; // 全部初始化为0
    }
    for (int i = 0; i < vNodes.length; i++) {
        if (visited[i] == 0) {
            DFS(i);
        }
    }
}
private int getFirstAdj(int vIndex) {
    if (vNodes[vIndex].firstArc != null) {
        return vNodes[vIndex].firstArc.adjvex;
    }
    return -1;
}
private int getNextAdj(int vIndex, int w) {
    ArcNode p;
    p = vNodes[vIndex].firstArc;
    while (p != null) {
        if (p.adjvex == w && p.next != null) {
            return p.next.adjvex;
        }
        p = p.next;
    }
    return -1;
}
//访问函数
private void visit(int vIndex) {
    System.out.print(vNodes[vIndex].data + " ");
}

测试

public static void main(String[] args) {
    int v[] = {
    2, 9, 6, 3, 7};
    int arc[] = {
    1, 2, 3, -1, 0, 2, -1, 1, 0, -1, 0, 4, -1, 3};
    MyGragh gragh = new MyGragh();
    gragh.createGragh(v, arc);
    System.out.println("深搜结果");
    gragh.travelByDFS();
}

运行结果

在这里插入图片描述

2 广度优先搜索遍历

广度优先搜索遍历是一种按层次遍历的算法。它的遍历顺序是先访问顶点 v 0 v_0 v0，再访问离顶点 v 0 v_0 v0 最近的顶点 v 1 , v 2 , . . , v n v_1,v_2,..,v_n v1,v2,..,vn ，然后依次遍历离 v 1 , v 2 , . . . , v n v_1,v_2,…,v_n v1,v2,…,vn 最近的顶点。

【以 v 0 v_0 v0 为中心，一层一层向外扩展】

Java实现：

void BFS(int vIndex) {
        visit(vIndex); // 访问vIndex 顶点信息
        visited[vIndex] = 1; // 置1表示已访问
        MyQueue queue = new MyQueue(); // 创建一个队列来存放图顶点对象
        queue.enQueue(vIndex); // 顶点下标vIndex 入队
        while (queue.getQueueLength() != 0) {
            int v = queue.deQueue(); // 队头元素取出
            int w = getFirstAdj(v); // 找到顶点v 的第一个邻接点，如果没有返回-1
            while (w != -1) {
                if (visited[w] == 0) {
                    visit(w);
                    queue.enQueue(w);
                    visited[w] = 1;
                }
                w = getNextAdj(v, w);
            }
        }
    }
    // 主算法
    public void travelByBFS() {
        // 广度优先搜索遍历图
        visited = new int[vNodes.length];
        for (int i = 0; i < vNodes.length; i++) {
            visited[i] = 0;
        }
        for (int i = 0; i < vNodes.length; i++) {
            if (visited[i] == 0) {
                BFS(i);
            }
        }
    }

测试

public static void main(String[] args) {
    int v[] = {
    2, 9, 6, 3, 7};
    int arc[] = {
    1, 2, 3, -1, 0, 2, -1, 1, 0, -1, 0, 4, -1, 3};
    MyGragh gragh = new MyGragh();
    gragh.createGragh(v, arc);
    System.out.println("广搜结果");
    gragh.travelByBFS();
}