数据结构笔记04 | Vince‘s hut

图

背景

线性表和树都只能有一个前驱节点，也就是父节点，当需要表示多对多关系的时候就需要使用图。图是一种数据结构，其中：节点可以具有 0 个或多个相邻元素，两个节点之间的连接称为边（Edge），节点也被称为顶点（Vertices）。

无向图

顶点之间的连接没有方向，例如：

有向图

顶点之间有方向，只能从一点到另一点，但不能直接返回

带权图

路径有权值（个人看起来像EIGRP），也叫网

图的表示方式

二维数组（邻接矩阵）

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵的行和列表示1到n个点。

例如：左侧列中4（代表图中的 4）所在的行，和上方行中的2（代表图中的2）所在的列的交点值（4，2）是1，表示可以直接连接。

链表表示（邻接表）

由于邻接矩阵有一个缺点：它需要为每个顶点都分配 n 个边的空间，其实有很多边都是不存在的（比如上面的 0,0 不链接，也需要表示出来），这会造成空间的一定损失。

邻接表只关心存在的边，因此没有空间浪费，由数组 + 链表组成。

例如：标号为 0 的链表表示图中的 0 和哪些顶点直接相连。

图的创建

分析

保存顶点 ArrayList
保存矩阵 int[][] deges

代码

import java.util.ArrayList;
import java.util.Arrays;

public class GraphExample {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        String vertexValue[]={"A","B","C","D","E"};
        for (String VertexValue:vertexValue) {
            graph.addVertex(VertexValue);
        }
        //A-B A-C B-C B-D B-E
        graph.addEdge(0,1,1);
        graph.addEdge(0,2,1);
        graph.addEdge(1,2,1);
        graph.addEdge(1,3,1);
        graph.addEdge(1,4,1);

        graph.showGraph();
    }
}

class Graph {
    private ArrayList<String> vertexList;
    private int[][] edge;
    private int numOfEdges; //number of edges

    public Graph(int numOfVertex) {
        edge = new int[numOfVertex][numOfVertex];
        vertexList = new ArrayList<>(numOfVertex);
        numOfEdges = 0;
    }

    public void addVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * add edge
     *
     * @param vertex1 first vertex
     * @param vertex2 second vertex
     * @param weight  weight of edge
     */
    public void addEdge(int vertex1, int vertex2, int weight) {
        edge[vertex1][vertex2] = weight;
        edge[vertex2][vertex1] = weight;
        numOfEdges++;
    }

    public int getNumOfVertex() {
        return vertexList.size();
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    public int getWeight(int vertex1, int vertex2) {
        return edge[vertex1][vertex2];
    }

    public void showGraph() {
        for (int[] link : edge) {
            System.out.println(Arrays.toString(link));
        }
    }
}

深度优先遍历 Depth First Search, DFS

从初始访问节点出发，初始访问节点可能有多个邻接节点（直连）

深度优先遍历的策略为：初始节点出发，访问第一个邻节点，再将访问到的邻节点视为初始节点，访问它的第一个邻节点，以此类推。

算法步骤：

访问初始节点 v ，并标记已访问
查找节点的第一个邻节点 w
若 w 存在，执行步骤 4 ，若不存在返回第一步，从 v 的下一个节点继续
若 w 未被访问，对 w 进行深度优先遍历递归（把 w 看成 v，继续执行1、2、3）
若 w 被访问过，查找节点 w 的下一个邻节点，转到步骤 3

在本例中，以 A 为初始节点，在 vertexList 中，顶点的储存方式为 { A, B, C, D, E }

从 A 出发，标记成已访问
它的第一个节点是 B，存在且未被访问，访问 B 的第一个邻节点 C
C存在，访问 C ，标记为已访问，C 的下一个节点的 D，但无法到达（不存在），回溯至上一步
B 的第一个节点是 C，被访问，查找下一个邻节点 D
D存在，访问 D ，标记为已访问，D 的下一个节点的 E，但无法到达（不存在），回溯至上一步
B 的第一个、第二个邻节点都被访问，访问第三个邻节点 E
E 存在，访问 E ，标记为已访问（回溯/打断）

广度优先遍历 Broad First Search, BFS

类似于分层搜索，广度优先遍历需要使用一个队列来保存访问过的节点的顺序。按此顺序来访问这些节点的邻接节点

算法步骤：

访问初始节点 v ，并标记已访问
将 v 加入队列
当 v 为非空时，继续执行，否则算法结束
出队列，取得头节点 u
查找 u 的第一个邻节点 w
若 w 不存在，转到步骤 3，否则：
6.1. 若 w 未访问，标记为已访问
6.2. 节点 w 入队
6.3. 查找节点 u 的继 w 零界点后的下一个邻节点 w，转到步骤 6

图