数据结构-图的详解

男娘i 2023-10-02 19:44 6阅读 0赞

## 1.概述 ##

在计算机科学中，一个图就是一些*顶点*的集合，这些顶点通过一系列*边*结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。

在计算机中有了数组链表，可以满足基本需求，为什么还需要图呢？

很多人有这样疑惑，因为我们拥有者一对一，一对多的数据结构，但是没有多对多的数据结构，所以，图就是为了满足多对多的一种需求所以创造出来的数据结构

## 2.分类 ##

**1.无向图（undirected graph）**

如果一个图结构中，所有的边都没有方向性，那么这种图便称为无向图。典型的无向图，如图二所示。由于无向图中的边没有方向性，这样我们在表示边的时候对两个顶点的顺序没有要求。例如顶点VI和顶点V5之间的边，可以表示为(V2， V6),也可以表示为(V6，V2)。

![db624d384d3238e9b65fba09544adbca.png][]

**图二 无向图**

对于图二无向图，对应的顶点集合和边集合如下：

V（G）= \{V1，V2，V3，V4，V5，V6\}

E（G）= \{（V1,V2），（V1，V3），（V2，V6），（V2，V5），（V2，V4），（V4，V3），（V3，V5），（V5，V6）\}

**2.有向图（directed graph）**

一个图结构中，边是有方向性的，那么这种图就称为有向图，如图三所示。由于图的边有方向性，我们在表示边的时候对两个顶点的顺序就有要求。我们采用尖括号表示有向边，例如<V2，V6>表示从顶点V2到顶点V6，而<V6，V2>表示顶点V6到顶点V2。

![0abd12bfd81cec5f658aebb70c2a9126.png][]

**图三 有向图**

对于图三有向图，对应的顶点集合和边集合如下：

V（G）= \{V1，V2，V3，V4，V5，V6\}

E（G）= \{<V2，V1>，<V3，V1>，<V4，V3>，<V4，V2>，<V3，V5>，<V5，V3>，<V2，V5>，<V6，V5>，<V2，V6>，<V6，V2>\}

**注意：**

无向图也可以理解成一个特殊的有向图，就是边互相指向对方节点，A指向B，B又指向A。

**3.混合图（mixed graph）**

**　　**一个图结构中，边同时有的是有方向性有的是无方向型的图。

在生活中混合图这种情况比较常见，比如城市道路中有些道路是单向通行，有的是双向通行。

**4.顶点的度**

连接顶点的边的数量称为该顶点的度。顶点的度在有向图和无向图中具有不同的表示。对于无向图，一个顶点V的度比较简单，其是连接该顶点的边的数量，记为D(V)。 例如，图二所示的无向图中，顶点V5的度为3。而V6的度为2。

对于有向图要稍复杂些，根据连接顶点V的边的方向性，一个顶点的度有**入度**和**出度**之分。

*  入度是以该顶点为端点的入边数量， 记为ID(V)。
 *  出度是以该顶点为端点的出边数量， 记为OD(V)。

这样，有向图中，一个顶点V的总度便是入度和出度之和，即D(V) = ID(V) + OD(V)。例如，图三所示的有向图中，顶点V5的入度为3,出度为1，因此，顶点V5的总度为4。

**5.邻接顶点**

邻接顶点是指图结构中一条边的两个顶点。 邻接顶点在有向图和无向图中具有不同的表示。对于无向图，邻接顶点比较简单。例如，在图二所示的无向图中，顶点V2和顶点V6互为邻接顶点，顶点V2和顶点V5互为邻接顶点等。

对于有向图要稍复杂些，根据连接顶点V的边的方向性，两个顶点分别称为**起始顶点**(起点或始点)和**结束顶点**(终点)。有向图的邻接顶点分为两类：

*  **入边邻接顶点**：连接该顶点的边中的起始顶点。例如，对于组成<V2，V6>这条边的两个顶点，V2是V6的入边邻接顶点。
 *  **出边邻接顶点：**连接该顶点的边中的结束顶点。例如，对于组成<V2，V6>这条边的两个顶点，V6是V2的出边邻接顶点。

## 3. 图的遍历 ##

所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:

( 1)深度优先遍历

(2)广度优先遍历

###    3.1 图的深度优先遍历 ###

####    3.1.1 基本思想 ####

图的深度优先搜索（Depth First Search）

深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点,可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。  
我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。  
显然,深度优先搜索是一个递归的过程

####    3.1.2 算法步骤 ####

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

### 3.2 图的广度优先遍历 ###

####    3.2.1 基本思想 ####

图的广度优先搜索(Broad First Search).  
类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点

####    3.2.2 算法步骤 ####

1.  访问初始结点 v并标记结点 v为已访问
2.  结点v入队列
3.  当队列非空时，继续执行，否则算法结束
4.  出队列，取得队头结点u
5.  查找结点 u的第一个邻接结点 w。
6.  若结点 u的邻接结点 w不存在，则转到步骤 3；否则循环执行以下三个步骤：
7.  若结点 w尚未被访问，则访问结点 w并标记为已访问
8.  结点 w入队列
9.  查找结点 u的继 w邻接结点后的下一个邻接结点 w，转到步骤6

## 4.代码实现遍历 ##

/**
     * @author wangli
     * @data 2022/6/1 10:54
     * @Description:
     */
    public class Graph {
            public static void main(String[] args) {
    
                    //测试一把图是否创建正确
                    String[] vertexs = new String[]{"A", "B", "C", "D", "E","F","G"};
                    //创建图的对象
                    Graph graph = new Graph(vertexs.length);
                    //循环的添加结点
                    for (String vertex : vertexs) {
                            graph.vertexList.add(vertex);
                    }
                    boolean[] booleans = new boolean[vertexs.length];
                    for (int i = 0; i < vertexs.length; i++) {
                            booleans[i]=false;
                    }
                    //添加边的操作
                    //A-B A-C B-C B-D B-E 这几个相连A0,B1,C2,D3,E4
                    graph.addEdge(0, 1, 1);//这个表示A-B已经相连接
                    graph.addEdge(0, 2, 1);//A-C
                    graph.addEdge(1, 2, 1);//B-C
                    graph.addEdge(1, 3, 1);//B-D
                    graph.addEdge(1, 4, 1);//B-E
                    graph.addEdge(3, 5, 1);//D-F
                    graph.addEdge(4, 6, 1);//E-G
                    //显示一把邻接矩阵
                    graph.showEdges();
    
                    //测试深度遍历
                    System.out.println("深度遍历");
                    graph.depthFirstSearch();
                    System.out.println();
                    //测试广度优先遍历
                    System.out.println("广度优先遍历测试");
                    graph.BreadthFirstSearch(booleans,0);
            }
            //存储节点
            private ArrayList<String> vertexList;
            //存储对应的邻接矩阵
            private int[][] edges;
            //边的数量
            private int numOFEdges;
            //表示节点是否被访问过
            private boolean[] isVisited;
    
            public Graph(ArrayList<String> vertexList, int[][] edges, int numOFEdges, boolean[] isVisited) {
                    this.vertexList = vertexList;
                    this.edges = edges;
                    this.numOFEdges = numOFEdges;
                    this.isVisited = isVisited;
            }
    
            //基本准备
            //构造器
            public Graph(int n) {//n表示构建这个图有多少个顶点
                    //初始化矩阵和vertexList
                    edges = new int[n][n];
                    vertexList = new ArrayList<>(n);
                    numOFEdges = 0;//初始化为0
            }
    
    
    
            /**
             * 深度优先遍历
             * @param isVisited
             * @param v 起始遍历节点
             */
            public void depthFirstSearch(boolean[] isVisited,int v){
                    System.out.print(vertexList.get(v)+"=>");
    //                1.将起始节点置为true，表示已经遍历过了
                    isVisited[v]=true;
    //                2.查询邻接点
                    int neighborNodeIndex = getNeighborNode(v);
    //                3.若邻接点不为空，以邻接点为起始节点开始递归遍历
                    while (neighborNodeIndex!=-1){
    //                        4.若没有被遍历过，递归遍历
                            if (!isVisited[v]){
                                    depthFirstSearch(isVisited,neighborNodeIndex);
                            }
    //                        5.若已经被访问过，继续下一个邻接节点
                            neighborNodeIndex = getNextNeighbor(v, neighborNodeIndex);
                    }
            }
            //对dfs进行重载，对应w不存在的情况
            public void depthFirstSearch() {
                    isVisited = new boolean[vertexList.size()];
                    //遍历所有的节点，进行dfs[回溯]
                    for (int i = 0; i < vertexList.size(); i++) {
                            if (!isVisited[i]) {
                                    depthFirstSearch(isVisited, i);
                            }
                    }
            }
    
            public void BreadthFirstSearch(boolean[] isVisited,int v){
                    System.out.print(vertexList.get(v)+"=>");
    //                1.将起始节点置为true，表示已经遍历过了
                    isVisited[v]=true;
    //                2.查询邻接点
                    int neighborNodeIndex = getNeighborNode(v);
                    for (int i = v; i < vertexList.size(); i++) {
                            for (int j = 0; j < vertexList.size(); j++) {
                                    if (!isVisited[j]&&edges[i][j]==1){
                                            System.out.print(vertexList.get(j)+"=>");
                                            isVisited[j]=true;
                                    }
                            }
                    }
            }
            /**
             * 获取邻接点
             */
            public int getNeighborNode(int v){
                    for (int i = 0; i < vertexList.size(); i++) {
                            if (edges[v][i]>0){
                                    return  i;
                            }
                    }
                    return -1;
            }
    
            /**
             * @param v1 指的是V1行
             * @param v2 指的是V2列，并且V2是V1的邻接结点，即edges[v1][v2]==1,这个方法是找v1的下一个邻接结点，所以j=v2+1
             *           上面那个只能得到第一个邻接结点的下标。而这个和那个不同，尤其对于邻接结点已经被访问，不能直接用上面那个
             * @return
             */
            public int getNextNeighbor(int v1, int v2) {
                    for (int j = v2 + 1; j < vertexList.size(); j++) {
                            if (edges[v1][j] > 0) {
                                    return j;
                            }
                    }
                    return -1;
            }
    
    
            /**
             * 显示对应的邻接矩阵
             */
            public void showEdges(){
                    for (int[] edge : edges) {
                            System.out.println(Arrays.toString(edge));
                    }
            }
            /**
             * 添加节点
             */
            public void addNode(String node){
                    vertexList.add(node);
            }
    
            /**
             * 添加边
             * @param v1 第一个顶点
             * @param v2 第二个顶点
             * @param weight 权重
             */
            public void addEdge(int v1,int v2,int weight){
                    edges[v1][v2]=weight;
                    edges[v2][v1]=weight;
                    numOFEdges++;
            }
    }

[db624d384d3238e9b65fba09544adbca.png]: https://img-blog.csdnimg.cn/img_convert/db624d384d3238e9b65fba09544adbca.png
[0abd12bfd81cec5f658aebb70c2a9126.png]: https://img-blog.csdnimg.cn/img_convert/0abd12bfd81cec5f658aebb70c2a9126.png