【数据结构与算法】图

图的基本介绍

为什么要有图

我们之前学习的所有数据结构（线性表、树……）不能表示多对多的关系，这时候就需要引入图了！

图的定义及一些概念

• 图是一种数据结构，其中节点可以有零个或多个相邻元素。两个节点之间的连接称为边，节点也可以成为顶点。

  

• 图的一些概念

  • 顶点

  • 边

  • 路径

  • 无向图

  • 有向图

  • 带权图

简单实现

public class Graph {

    //存储顶点集合
    private ArrayList<String> vertexList;
    //存储图对应的邻结矩阵
    private int[][] edges;
    //边的数目
    private int numOfEdges;
    //定义一个数组，记录某个节点是否被访问
    private boolean[] isVisited;

    public Graph(int n) {
        this.vertexList = new ArrayList<>();
        this.edges = new int[n][n];
        isVisited = new boolean[n];
    }

    //添加顶点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 无向图！！！
     * @param v1 第一个节点下标（序号）
     * @param v2 第二个节点下标（序号）
     * @param weight 权值，0为不直接相连，1为直接相连
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    //返回顶点个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    //返回边的个数
    public int getNumOfEdges() {
        return numOfEdges;
    }

    //根据节点下标（序号）得到对应节点的值
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    //返回v1、v2的权值
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    //输出图的矩阵形式
    public void showGraph() {
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }
}

图的遍历

深度优先算法（DFS）

/**
 *
 * @param index 当前节点的下标
 * @return 得到第一个邻接节点的下标
 */
public int getFirstNeighbor(int index) {
    for (int i = 0; i < vertexList.size(); i++) {
        if (edges[index][i] > 0) {
            return i;
        }
    }
    return -1;
}

/**
 * 根据前一个邻接节点的下标获取下一个邻接节点
 * @param v1 当前节点下标
 * @param v2 当前节点邻节点下标
 * @return
 */
public int getNextNeighbor(int v1, int v2) {
    for (int i = v2 + 1; i < vertexList.size(); i++) {
        if (edges[v1][i] > 0) {
            return i;
        }
    }
    return -1;
}

/**
 * private：私有方法，只供内部函数调用
 * 深度优先算法
 * （相当于是对一个节点进行的dfs）
 * @param isVisited
 * @param i 第一次就是0
 */
private void dfs(boolean[] isVisited, int i) {
    //输出访问的节点
    System.out.print(getValueByIndex(i) + "->");
    //将访问过的节点的访问标识设置为true，表示已被访问
    isVisited[i] = true;
    //查找i的第一个邻节点
    int w = getFirstNeighbor(i);
    while (w != -1) {
        if (!isVisited[w]) {
            dfs(isVisited, w);
        }
        //如果w已经被访问过
        w = getNextNeighbor(i, w);
    }
}

/**
 * 重载dfs(boolean[] isVisited, int i)
 * 遍历每一个节点，对每一个节点进行dfs
 * （相当于是对整个图进行的dfs）
 */
public void dfs() {
    for (int i = 0; i < getNumOfVertex(); i++) {
        if (!isVisited[i]) {
            dfs(isVisited, i);
        }
    }
}

广度优先算法（BFS）

/**
 * 对一个节点进行广度优先遍历
 */
public void bfs(boolean[] isVisited, int i) {
    int u;  //表示队列头节点对应的下标
    int w;  //邻接节点的下标

    //队列，记录节点访问的顺序
    LinkedList queue = new LinkedList();
    System.out.println(getValueByIndex(i) + "->");
    isVisited[i] = true;
    //将节点加入队列
    queue.addLast(i);

    while (!queue.isEmpty()) {
        //取出队列的头节点下标
        u = (Integer) queue.removeFirst();
        //得到第一个邻节点的下标
        w = getFirstNeighbor(u);
        while (w != -1) {
            //是否访问过
            if (!isVisited[w]) {
                System.out.println(getValueByIndex(w) + "->");
                //标记已经访问
                isVisited[w] = true;
                //入队列
                queue.addLast(w);
            }
            //体现广度优先！
            w = getNextNeighbor(u, w);
        }
    }
}

/**
 * 对整个图进行广度优先算法
 */
public void bfs() {
    for (int i = 0; i < getNumOfVertex(); i++) {
        if (!isVisited[i]) {
            bfs(isVisited, i);
        }
    }
}