网站 › 『编程语言区』 › 图的创建、遍历

逸帅 发表于 2021-4-4 21:17

图的创建、遍历

本帖最后由 逸帅 于 2021-4-6 11:20 编辑

# 图的创建、遍历

# 1、图的基本介绍

当我们需要表示**多对多**的关系时，我们就需要**图**

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


## 2、图的表示方法

###2.1、邻接矩阵

- 邻接矩阵是表示图形中**顶点之间相邻关系**的矩阵，对于n个顶点的图而言，矩阵是的row和 col表示的是1…n个点，***其中0表示没有连接，1表示有连接***


### 2.2、邻接表

1. 邻接矩阵需要为每个顶点都分配 n 个边的空间，其实有很多边都是不存在,会造成空间的一定损失.

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


## 3、图的代码实现

### 3.1、要实现图的结构


### 3.2、思路分析

(1) 存储顶点用 String类型，并使用 ArrayList

(2) 保存矩阵用二维数组 edges

### 3.3、代码实现

```java
package com.yishuai.Graph;

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

/**
* @AuThor yishuai
* @description 图结构的创建（邻接矩阵）
* @date 2021/4/4 4:45 下午
*/
public class GraphCreate {
    public static void main(String[] args) {
      int sum = 5;
      String[] vertex = {"A", "B", "C", "D", "E"};
      Graph graph = new Graph(sum);
      //指明图的顶点
      for(String top : vertex) {
            graph.insertVertex(top);
      }
      //指明相连的顶点
      graph.insertEdge(0, 1, 1);
      graph.insertEdge(0, 2, 1);
      graph.insertEdge(1, 2, 1);
      graph.insertEdge(1, 3, 1);
      graph.insertEdge(1, 4, 1);

      //显示邻接矩阵
      System.out.println("邻接矩阵为：");
      graph.showGraph();
    }
}

class Graph {
    ArrayList<String> vertexList;
    int[][] edges;
    int numOfEdges;

    public Graph(int sum) {
      //根据顶点总数进行初始化，sum表示顶点的个数
      vertexList = new ArrayList<>(sum);
      //表示创建几行几列的矩阵
      edges = new int;
      //初始化边为0，代表都是孤立的节点
      numOfEdges = 0;
    }

   

    /**
   * 添加顶点，把顶点直接加入到list集合即可
   * @Param vertex 表示顶点
   */
    public void insertVertex(String vertex) {
      vertexList.add(vertex);
    }

    /**
   * 表示建立边的关系，因为是无向边，所以两边的指向都要添加
   * @param vertex1 第一个顶点的下标
   * @param vertex2 第二个顶点的下标
   * @param weight 表示权的值，一般是1
   */
    public void insertEdge(int vertex1, int vertex2, int weight) {
      edges = weight;
      edges = weight;
      numOfEdges++;
    }

   

    /**
   * 得到边的数量
   */
    public int getNumOfEdges() {
      return numOfEdges;
    }
    /**
   * 得到顶点的个数
   */
    public int getNumOfVertex() {
      return vertexList.size();
    }
   
    /**
   * 得到vertex1行，vertex2列的权值，也就是说有没有这条指向的边
   */
    public int getWeight(int vertex1, int vertex2) {
      return edges;
    }

   
    /**
   * 对矩阵进行展示
   */
    public void showGraph() {
      for(int[] list : edges) {
            System.out.println(Arrays.toString(list));
      }
    }
}
```

## 4、深度优先遍历（DFS）

### 4.1、前言

注意DFS方法的重载，为什么要重载？第二个不带参数的DFS方法作用是什么？

很多老师可能没有点出来这里的作用！

### 4.2、思路分析

- 访问初始结点v，并标记结点v为已访问
- 查找结点v的第一个邻接结点w
- 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续
- 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）
- 查找结点v的w邻接结点的下一个邻接结点，转到步骤 3

### 4.3、代码实现

```java
class Graph {
    ArrayList<String> vertexList;
    int[][] edges;
    int numOfEdges;
    boolean[] isExist;

    public Graph(int sum) {
      //根据顶点总数进行初始化，sum表示顶点的个数
      vertexList = new ArrayList<>(sum);
      //表示创建几行几列的矩阵
      edges = new int;
      //初始化边为0，代表都是孤立的节点
      numOfEdges = 0;
      //广度遍历,初始化是否被访问的数组，和顶点数组同步
      isExist = new boolean;
    }



    /**
   * 添加顶点，把顶点直接加入到list集合即可
   * @param vertex 表示顶点
   */
    public void insertVertex(String vertex) {
      vertexList.add(vertex);
    }

    /**
   * 表示建立边的关系，因为是无向边，所以两边的指向都要添加
   * @param vertex1 第一个顶点的下标
   * @param vertex2 第二个顶点的下标
   * @param weight 表示权的值，一般是1
   */
    public void insertEdge(int vertex1, int vertex2, int weight) {
      edges = weight;
      edges = weight;
      numOfEdges++;
    }

    /**
   * 得到边的数量
   */
    public int getNumOfEdges() {
      return numOfEdges;
    }
    /**
   * 得到顶点的个数
   */
    public int getNumOfVertex() {
      return vertexList.size();
    }

    /**
   * 得到vertex1行，vertex2列的权值，也就是说有没有这条指向的边
   */
    public int getWeight(int vertex1, int vertex2) {
      return edges;
    }

    /**
   * 对矩阵进行展示
   */
    public void showGraph() {
      for(int[] list : edges) {
            System.out.println(Arrays.toString(list));
      }
    }

    /**
   * 图的深度遍历思路：
   * 1) 访问初始结点 v1， 并标记结点 v1 为已访问。
   * 2) 查找结点v1的第一个邻接结点v2。
   * 3) 若v2存在，则继续执行步骤4， 如果v2不存在，则回到第 1 步，将从 v1 的下一个邻接结点继续。
   * 4) 若v2未被访问，对v2进行深度优先遍历递归（即把v2当做另一个v1， 然后进行步骤 123）。
   * 5) 查找结点v1的v2邻接结点的下一个邻接结点，转到步骤 3。
   * @param Vertex 顶点的下标,首次从第一个顶点开始
   */
    public void dfs(int Vertex){
      //如果这个顶点被访问过了，就直接返回
      if (isExist){
            return;
      }
      //没有被访问，输出当前的顶点，并标记为已访问
      System.out.print(vertexList.get(Vertex)+"==>");
      isExist = true;
      //找当前顶点的下一个顶点,继续进行深度遍历
      for (int i = 0; i < vertexList.size(); i++) {
            //代表找到了下一个邻接点
            if (edges != 0){
                dfs(i);
            }
      }
    }

    /**
   * 作用：
   * 遍历那些孤立的节点
   */
    public void dfs(){
      for (int i = 0; i < vertexList.size(); i++) {
            if (!isExist){
                dfs(i);
            }
      }
    }
}
```
## 5、广度优先遍历（BFS）
- 类似于一个**分层搜索**的过程，广度优先遍历需要使用一个**队列**以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

#### 5.1、思路

- 访问初始结点 v并标记结点 v为已访问

- 结点v入队列

- 当队列非空时，继续执行，否则算法结束

- 出队列，取得队头结点u

- 查找结点 u的第一个邻接结点 w。

- 若结点 u的邻接结点 w不存在，则转到步骤 3；否则循环执行以下三个步骤：

- 若结点 w尚未被访问，则访问结点 w并标记为已访问

- 结点 w入队列

- 查找结点 u的继 w邻接结点后的下一个邻接结点 w，转到步骤6

### 5.2、核心代码实现
```java
ArrayList<String> vertexList;
    int[][] edges;
    int numOfEdges;
    boolean[] isExist;
    LinkedList queue;

    public Graph(int sum) {
      //根据顶点总数进行初始化，sum表示顶点的个数
      vertexList = new ArrayList<>(sum);
      //表示创建几行几列的矩阵
      edges = new int;
      //初始化边为0，代表都是孤立的节点
      numOfEdges = 0;
      //初始化是否被访问的数组，和顶点数组同步
      isExist = new boolean;
      //广度遍历，用链表模拟队列
      queue = new LinkedList<Integer>();
    }

/**
   * 广度遍历思路：
   * 访问初始结点v1并标记结点v1为已访问
   * 结点v1入队列
   * 当队列非空时，继续执行，否则算法结束
   * 出队列，取得队头结点u1
   * 查找结点 u1的第一个邻接结点w1。
   * 若结点 u1的邻接结点 w1不存在，则转到步骤 3；否则循环执行以下三个步骤：
   * 若结点 w1尚未被访问，则访问结点 w1并标记为已访问
   * 结点 w1入队列
   * 查找结点 u1的继 w1邻接结点后的下一个邻接结点 w1，转到步骤6
   * @param vertex 当前要被遍历顶点的下标
   */
    public void bfs(int vertex){
      //被访问过了直接返回(广度优先不能直接返回了，不然队列里面的顶点全部会直接返回)
      //只要没被访问过，再输出当前元素，后面的for循环再遍历这个顶点的这一行
      if (!isExist){
            //输出当前顶点，并标记为已访问，入队列
            System.out.print(vertexList.get(vertex)+"==>");
            isExist = true;
            queue.add(vertex);
      }

      //继续遍历当前顶点的邻接顶点(一行）
      for (int i = vertex + 1; i < vertexList.size(); i++) {
            //下一条边存在且未被访问
            if (edges != 0 && !isExist){
                System.out.print(vertexList.get(i)+"==>");
                isExist = true;
                queue.add(i);
            }
      }
      //队列没空就一直循环
      while (!queue.isEmpty()){
            //linkedlist.remove()表示移除第一个元素，并返回
            bfs((Integer) queue.remove());
      }
    }
    /**
   * 作用：
   * 遍历那些孤立的节点
   */
    public void bfs(){
      for (int i = 0; i < vertexList.size(); i++) {
            if (!isExist){
                bfs(i);
            }
      }
    }
```

逸帅 发表于 2021-4-4 22:43

QingYi. 发表于 2021-4-4 22:00
vertex1 and vertex2
vertex 不是顶点的意思吗 就是你传入的参数可以在进行操作之前进行有效值判断

哦哦，明白了，可以的，感谢哈，还有啥可以改进的地方不{:301_987:}

逸帅 发表于 2021-4-4 21:51

QingYi. 发表于 2021-4-4 21:38
在getWeight这个方法中，可以添加一个验证两个点是否有效，同理 其他方法也可以调用一个“valid”方法来验 ...

请问两个点是否有效是什么意思呀，是边吗？

Anyling 发表于 2021-4-4 21:29

先收藏起来。将来学了拿出来看看

zpent 发表于 2021-4-4 21:32

4、深度优先遍历（DFS）
4.3、前言
注意DFS方法的重载，为什么要重载？第二个不带参数的DFS方法作用是什么？

这个 “4.3、前言” 强迫症犯了
大佬能改下不

QingYi. 发表于 2021-4-4 21:37

zpent 发表于 2021-4-4 21:32
4、深度优先遍历（DFS）
4.3、前言
注意DFS方法的重载，为什么要重载？第二个不带参数的DFS方法作用是什 ...

两个联通分量

逸帅 发表于 2021-4-4 21:38

QingYi. 发表于 2021-4-4 21:37
两个联通分量

改了改了

逸帅 发表于 2021-4-4 21:38

zpent 发表于 2021-4-4 21:32
4、深度优先遍历（DFS）
4.3、前言
注意DFS方法的重载，为什么要重载？第二个不带参数的DFS方法作用是什 ...

好了，改好了。。。{:301_978:}

QingYi. 发表于 2021-4-4 21:38

在getWeight这个方法中，可以添加一个验证两个点是否有效，同理 其他方法也可以调用一个“valid”方法来验证

QingYi. 发表于 2021-4-4 22:00

逸帅 发表于 2021-4-4 21:51
请问两个点是否有效是什么意思呀，是边吗？

vertex1 and vertex2
vertex 不是顶点的意思吗 就是你传入的参数可以在进行操作之前进行有效值判断

Tazear 发表于 2021-4-4 22:14

勾起了我学数据结构的恐惧，当时学这东西和离散数学没把我直接送走

查看完整版本: 图的创建、遍历