1. 图概念 - 多对多关系

提出背景

1、 线性表只能局限于一个直接前驱、直接后继的关系**(一对一关系)** ;
2、 树只能局限于一个父节点的关系**(一对多关系)** ;

专有名词

1、 边:两个结点之间的连接;

2、 结点(顶点):可以具有零个或多个相邻元素;

3、 无(有)向图:顶点之间的连接没有(有)方向-即边没有方向;

4、 带权图(网):边带数值的图;

5、 图的表示;

①:数组形式 - 邻接矩阵

②:数组+链表形式 - 邻链表

无向图 - 数据结构
 

有向图 - 数据结构
 

带权图(也称网) - 数据结构
 

1.1 图的表式

1.1.1 矩阵 - 数组

缺点:浪费太多的空间 - 标记某个结点与图中所有结点的关系

 

1.1.2 邻接表 - 数组+链表

优势:只记录某个结点与该结点有联系的结点信息

 

2. 代码

2.1 矩阵

 

2.1.1 基本类创建#

/**
 * @Classname UndirectedWeightGraph
 * @Description
 * @Date 2022/4/16 13:32
 * @Created by lrc
 */

//无向带权图
public class UndirectedWeightGraph {
   
     

    //存储结点
    ArrayList<String> vertexs;

    // 存储结点之间的权值 - 结点之间的关系 -- 矩阵
    int[][] edges;

    // 存储图中边的个数
    int numOfEdges;
    
    
    //存储是否遍历过的节点信息 false未遍历  true已经遍历过
    boolean[] isVisable;
    
    
    public static void main(String[] args) {
   
     

        //1, 结点信息
        String[] vertexs = {
   
     "v1", "v2", "v3", "v4"};
        Integer n = vertexs.length;

        // 2. 创建带5个结点的无序带权图
        UndirectedWeightGraph graph = new UndirectedWeightGraph(n);

        // 3. 添加结点
        for(String vertex : vertexs) {
   
     
            graph.insertVertex(vertex);
        }

        // 4. 添加结点之间的权值 - 这里的权值1仅表示两结点之间有连接关系
        graph.insertWeight(0,1, 1);
        graph.insertWeight(0,2, 1);
        graph.insertWeight(1,2, 1);
        graph.insertWeight(1,3, 1);
        // 5. 显示图的矩阵
        //System.out.println(graph.getGraph());
        graph.showGrpah();

    }

    //初始化 - 结点个数
    UndirectedWeightGraph(int vertexsNum) {
   
     

        this.vertexs = new ArrayList<>(vertexsNum);
        this.edges = new int[vertexsNum][vertexsNum];
        this.numOfEdges = 0;

    }

    //获取边的个数
    public int getNumOfEdges() {
   
     
        return numOfEdges;
    }

    //获取结点个数
    public int getVertexsNum() {
   
     
        return this.vertexs.size();
    }
    //添加新结点
    public void insertVertex(String vertex) {
   
     
        this.vertexs.add(vertex);
    }

    //获取两结点之间的边的权值 "A结点表示0" "B节点表示1"
    public int getWeight(int firstVertex, int secondVertext) {
   
     
        return edges[firstVertex][secondVertext];
    }
    //获取矩阵 - 即把数组Edges权值图打印出来
    public String getGraph() {
   
     
        return Arrays.deepToString(edges);
    }

    //显示矩阵
    public void showGrpah() {
   
     
        for(int[] edgeWeight : edges) {
   
     
            System.out.println(Arrays.toString(edgeWeight));
        }
    }

    //添加结点之间的关系 - 即权值 - 因为无向图的关系必须赋值数组中两个元素相同的权值
    public void insertWeight(int firstVertex, int secondVertext, int weight) {
   
     
        edges[firstVertex][secondVertext] = weight;
        edges[secondVertext][firstVertex] = weight;
        numOfEdges++;
    }
}

 

2.1.2 遍历图的结点#

遍历

深度优先遍历(Depth First Search)

广度优先遍历(Board First Search)

2.1.2.1 深度优先遍历(DFS)#

DFS思想:访问到某个结点,就以某个结点访问该结点的第一个邻接结点 —纵向挖掘访问

找到W

未被访问

访问过

未找到W

1、 访问并输出初始结点V,并标记该V结点已被访问;

2、 查找V结点某个邻接结点W;

3、 是否找到W?;

是否W已经被访问过?

对W进行深度遍历 - 递归进入该结点(即V为W,重复1、2、3步骤)

查找V的下一个邻接结点 - 从步骤3开始

未找到

返回到上一层递归

深度优先遍历代码
写法1

    //得到第一个邻接点的小标 - 找到返回W的小标,未找到返回-1 - 下一个小标的结点
    public int getFirstNeigbor(int index) {
   
     

        for(int j = 0; j <vertexs.size(); j++) {
   
     
            if(edges[index][j] > 0) {
   
     
                return j;
            }
        }
        return -1;
    }
    
    
    //根据前一个邻结点的小标来获取一个邻接点- 找到返回新的W的小标,未找到返回-1
    public int getNextNeigbor(int index, int w) {
   
     

        for(int j = w+1; j<vertexs.size(); j++ ) {
   
     
            if(edges[index][j] > 0) {
   
     
                return j;
            }
        }
        return -1;
    }
    

    //深度优先遍历
    public void dfs(boolean[] isVisited, int i) {
   
     

        System.out.println(vertexs.get(i));

        isVisited[i] = true;

        int w = getFirstNeigbor(i);

        while(w != -1) {
   
     
            if(!isVisited[w]) {
   
     
                dfs(isVisited, w);
            }

            w = getNextNeigbor(i, w);
        }
    }
    
    
    //重载深度优先算法
    public void dfs() {
   
     

        for(int i = 0; i<getVertexsNum(); i++) {
   
     

            //如果未访问过,则从该结点开始访问
            if(isVisable[i] == false) {
   
     
                dfs(i);
            }
        }
        
        //遍历完后修改回原来的状态
        for(int i = 0; i < isVisable.length; i++) {
   
     
            isVisable[i] = false;
        }        

    }

写法2

    //得到下一个邻接结点 - 寻找当前结点未被访问的邻接结点
    public int getNextNeigbor2(int index) {
   
     
        for(int j = 0; j<isVisable.length; j++) {
   
     

            if(edges[index][j] > 0 && isVisable[j] == false) {
   
     
                return j;
            }
        }
        return -1;

    }    
    
    
    //深度优先遍历2
    public void dfs2(int i) {
   
     

        System.out.println(vertexs.get(i));

        isVisable[i] = true;

        int w = getNextNeigbor2(i);

        while(w != -1) {
   
     
             dfs2(w);
            w = getNextNeigbor2(i);
        }
    }    
    
    //重载深度优先算法
    public void dfs2() {
   
     
           //图可能存在没有变得结点 - 故需要遍历所有结点
        for(int i = 0; i<getVertexsNum(); i++) {
   
     
            //如果未访问过,则从该结点开始访问
            if(isVisable[i] == false) {
   
     
                dfs2(i);
            }
        }
        
        //遍历完后修改回原来的状态
        for(int i = 0; i < isVisable.length; i++) {
   
     
            isVisable[i] = false;
        }

    }

 

测试

public static void main(String[] args) {
   
     

        //1, 结点信息
        String[] vertexs = {
   
     "v1", "v2", "v3", "v4"};
        Integer n = vertexs.length;

        // 2. 创建带5个结点的无序带权图
        UndirectedWeightGraph graph = new UndirectedWeightGraph(n);

        // 3. 添加结点
        for (String vertex : vertexs) {
   
     
            graph.insertVertex(vertex);
        }

        // 4. 添加结点之间的权值 - 这里的权值1仅表示两结点之间有连接关系
        graph.insertWeight(0, 1, 1);
        graph.insertWeight(0, 2, 1);
        graph.insertWeight(1, 2, 1);
        graph.insertWeight(1, 3, 1);
        // 5. 显示图的矩阵
        //System.out.println(graph.getGraph());
        graph.showGrpah();

        graph.dfs2();

}

流程讲解

1. 首先dfs2( 0 )  打印V1

2. 寻找与V1相邻并且未访问过的邻结点   找到V2即 1

3. 进入递归     dfs(1)   打印V2

4. 寻找与V2相邻并且未访问过的邻结点   找到V3即 2

5. 进入递归     dfs(2)   打印V3

6. 寻找与V3相邻并且未访问过的邻结点   未找到  退出dfs(2)这个递归  返回到dfs(1)这个递归

7. 寻找与V2相邻并且未访问过的邻结点   找到V4即 3

8. 进入递归     dfs(3)   打印V4

9. 寻找与V4相邻并且未访问过的邻结点   未找到  退出dfs(3)这个递归  返回到dfs(1)这个递归

10. 寻找与V2相邻并且未访问过的邻结点  未找到  退出dfs(1)这个递归  返回到dfs(0)这个递归

11. 寻找与V1相邻并且未访问过的邻结点   未找到   退出dfs(0)    结束函数

2.1.2.2 广度优先遍历(BFS)- 分层搜索#

BFS思想:从队列弹出的结点为基准,访问该结点的所有未被访问的邻结节点,并将其放入队列中。如果该弹出的结点所有邻接结点被访问完,则从队列弹出一个结点,重复前者动作

 

    
    //得到下一个邻接结点
    public int getNextNeigbor2(int index) {
   
     
        for (int j = 0; j < isVisable.length; j++) {
   
     

            if (edges[index][j] > 0 && isVisable[j] == false) {
   
     
                return j;
            }
        }
        return -1;

    }    
    
    public void bfs(int i) {
   
     

        // 创建队列
        LinkedList<Integer> queue = new LinkedList();

        //将i入队
        queue.addLast(i);

        //从队列中获取头结点
        int u = queue.removeFirst();
        // 打印并输出结点信息
        System.out.println(this.getVertexByIndex(i));
        isVisable[u] = true;
        //以弹出结点读出所有该结点的邻接结点
        while(true) {
   
     
            
            //获取u的未被访问的邻接结点
            int w = getNextNeigbor2(u);
            if(w != -1) {
   
     
                //打印邻接结点并将其放入队列中,并标记已经被访问
                System.out.println(getVertexByIndex(w));
                isVisable[w] = true;
                queue.addLast(w);
                //如果当前结点已经遍历过所有其邻接结点,则从队列中弹出一个结点,并访问该结点所有邻接结点
            }else {
   
     
                // 如果队列无元素可弹,结束循环
                if(queue.size() == 0) {
   
     
                    break;
                }
                u = queue.removeFirst();
            }
        }

    }

    //重载广度优先遍历
    public void bfs() {
   
     

        //所有结点必须遍历 - 因为存在没有边的结点
       for(int i = 0; i < getVertexsNum(); i++) {
   
     

            if( isVisable[i] == false) {
   
     
                bfs(i);
            }

        }

        //恢复遍历前的状态
        for(int i = 0; i < isVisable.length; i++) {
   
     
            isVisable[i] = false;
        }
    }

2.1.2.3 案例讲解#

 

#深度优先遍历DFS
1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7

#广度优先遍历BFS
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8