图论中的算法

这篇具有很好参考价值的文章主要介绍了图论中的算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

图论的概念:图论是数学的一个分支,它是以图为研究对象,图论中的图是由若干个给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些实体之间的某种特定的关系,用点代表实体,用连接两点之间的线表示两个实体之间具有某种关系。

图的分类:

  • 无权无向图

图论中的算法

 无向就是可以互相通向,没有进行方向的限制,就好比双向指向:

图论中的算法

  • 无权有向图

图论中的算法

无权就是好比每条路线占的权重一致,没有区别,故我们可以把无权图假设为每个权重都是1的有权图:

图论中的算法

  • 有权无向图

图论中的算法

  • 有权有向图

图论中的算法

BFS和DFS

我们首先来了解什么是BFS?什么又是DFS?图论中的算法

       DFS俗称深度优先算法,有一种不撞南墙不回头的感觉,认准一条路,一致往下走,直到走不通位置,然后再重新返回再重复刚才的操作,直到找到目标节点为止。DFS关键点是递归以及回溯,一般用栈进行操作。在图中我们经常这样:

图论中的算法

图论中的算法

       BFS俗称广度优先算法,相对于深度优先算法,如果把深度优先算法当成是一个莽夫的话,广度优先算法像是一个文人墨客,广度优先算法在面临一个路口时,把所有的路口记录下来,然后选择其中一个进入,然后再回退再进入另一个路口,直到找到目标节点为止。BFS关键点是状态的选取和标记,一般用队列去解决问题,在图中我们经常这样:

图论中的算法

 图的存储结构

  • 邻接矩阵

概念所谓邻接矩阵存储结构就是每个顶点用一个一维数组存储边的信息,这样所有点合起来就是用矩阵表示图中各顶点之间的邻接关系。所谓矩阵其实就是二维数组。对于有n个顶点的图 G=(V,E) 来说,我们可以用一个 n× n 的矩阵A来表示G中各顶点的相邻关系

图论中的算法

 对应的邻接矩阵为:

图论中的算法

 与对应点直接相连为1,不直接相连为0

构建邻接矩阵:

package graphtheory;

import java.util.Arrays;

/**
 * 图的表示--使用邻接矩阵
 */
public class Graph01 {
    private char[] V;//顶点上的值

    private Vertex[] vertexs;//顶点数组

    private int N;


    //邻接矩阵
    private int[][] adj;

    //图的构造函数
    public Graph01(char[] arr) {//{'A','E','F','G','H','P'}
        //拿到数组的长度
        int length = arr.length;
        this.N = length;
        V = new char[length];
        //arr元素赋值 到V
        this.V = Arrays.copyOf(arr, length);
        //构建图中的结点
        vertexs = new Vertex[length];
        for (int i = 0; i < length; i++) {
            vertexs[i] = new Vertex(i,this.V[i]);//

        }
        this.adj = new int[length][length];
    }

    //打印邻接矩阵
    public void show() {
        System.out.print("    ");
        for (int i = 0; i < this.N; i++) {
            System.out.format("%4c", this.V[i]);
        }
        System.out.println();
        for (int i = 0; i < this.N; i++) {
            System.out.format("%4c",this.V[i]);
            for (int j = 0; j < this.N; j++) {
                System.out.format("%4s", this.adj[i][j] > 0?(this.adj[i][j]):"-");
            }
            System.out.println();
        }
    }

    /**
     * 创建顶点类
     */
    private class Vertex {
        char v;//值
        int index;//索引

        public Vertex(int index, char c) {
            this.index = index;
            this.v = v;
        }

    }

    public static void main(String[] args) {
        char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
        //构建graph01
        Graph01 graph01 = new Graph01(arr);
        //进行连接
        int[][] adjMatrix = graph01.adj;
        adjMatrix[0][1]=1;
        adjMatrix[0][2]=1;
        adjMatrix[0][3]=1;

        adjMatrix[1][0]=1;
        adjMatrix[1][3]=1;
        adjMatrix[1][4]=1;

        adjMatrix[2][0]=1;

        adjMatrix[3][0]=1;
        adjMatrix[3][1]=1;
        adjMatrix[3][4]=1;
        adjMatrix[3][5]=1;

        adjMatrix[4][1]=1;
        adjMatrix[4][3]=1;
        adjMatrix[4][5]=1;

        adjMatrix[5][3]=1;
        adjMatrix[5][4]=1;


        graph01.show();
    }
}

 图论中的算法

  • 邻接表

邻接表的概念:邻接表的思想是,对于图中的每一个顶点,用一个数组来记录这个点和哪些点相连。由于相邻的点会动态的添加,所以对于每个点,我们需要用List来记录。

图论中的算法

 对应的邻接表为:

图论中的算法

package graphtheory;

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

/**
 * 图的表示--使用邻接矩阵
 */
public class Graph02 {
    private char[] V;//顶点上的值

    private Vertex[] vertexs;//顶点数组
    private int N;


    //邻接矩阵
    private List<Integer>[] adj;

    //图的构造函数
    public Graph02(char[] arr) {//{'A','E','F','G','H','P'}
        //拿到数组的长度
        int length = arr.length;
        this.N = length;
        V = new char[length];
        //arr元素赋值 到V
        this.V = Arrays.copyOf(arr, length);
        //构建图中的结点
        vertexs = new Vertex[length];
        for (int i = 0; i < length; i++) {
            vertexs[i] = new Vertex(i, this.V[i]);

        }
        this.adj = new List[length];
        for (int i = 0; i < this.N; i++) {
            this.adj[i]=new ArrayList<>();
        }
    }

    //打印邻接矩阵
    public void show() {
        System.out.println("    ");
        for (int i = 0; i < this.N; i++) {
            System.out.format("%-4c", this.V[i]);
            //拿到邻接表相邻结点的集合
            List<Integer> linkedList = this.adj[i];
            for (int j = 0; j < linkedList.size(); j++) {
                System.out.print(this.V[linkedList.get(j)] + "---->");
            }
            System.out.println();
            System.out.format("%-4d",vertexs[i].index);
            for (int j = 0; j < linkedList.size(); j++) {
                System.out.print(vertexs[linkedList.get(j)].index + "---->");
            }
            System.out.println();

            }
        }



    /**
     * 创建顶点类
     */
    private class Vertex {
        char v;//值

        int index;//索引

        int weight;//权值

        public Vertex(int index, char c) {
            this.index = index;
            this.v = v;
            this.weight = weight;
        }

        public Vertex(int index) {

        }
    }

    public static void main(String[] args) {
        char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
        //构建graph01
        Graph02 graph02 = new Graph02(arr);
        //邻接表
        List<Integer>[] adj = graph02.adj;
        adj[0].add(1);
        adj[0].add(2);
        adj[0].add(3);

        adj[1].add(0);
        adj[1].add(3);
        adj[1].add(4);

        adj[2].add(0);

        adj[3].add(0);
        adj[3].add(1);
        adj[3].add(4);
        adj[3].add(5);

        adj[4].add(1);
        adj[4].add(3);
        adj[4].add(5);

        adj[5].add(3);
        adj[5].add(4);


        graph02.show();
    }
}

图论中的算法

使用邻接表求出A--P的所有路径:

package graphtheory;


import java.util.*;

// 图的表示-- 使用邻接表
public class Graph03 {
    private char[] V;
    // 顶点数组
    private Vertex[] vertexs;
    private int N;
    // 邻接表
    private List<Integer>[] adj;

    public Graph03(char[] arr) { // {'A','E','F','G','H','P'}
        int length = arr.length;
        this.N = length;
        this.V = Arrays.copyOf(arr, length);
        // 构建图中的结点
        vertexs = new Vertex[length];
        for (int i = 0; i < length; i++) {
            vertexs[i] = new Vertex(0, this.V[i]);
        }
        this.adj = new List[length];
        for (int i = 0; i < this.N; i++) {
            this.adj[i] = new ArrayList<>();
        }
    }

    // 打印邻接矩阵
    public void show() {
        for (int i = 0; i < this.N; i++) {
            System.out.format("%-4c", this.V[i]);
            List<Integer> linkedList = this.adj[i];
            for (int j = 0; j < linkedList.size(); j++) {
                System.out.print(this.V[linkedList.get(j)] + "---->");
            }
            System.out.println();
            System.out.format("%-4c", this.V[i]);
            for (int j = 0; j < linkedList.size(); j++) {
                System.out.print(linkedList.get(j) + "---->");
            }
            System.out.println();
        }
    }


    public void bfs(int startIndex){
        boolean visited[] = new boolean[this.N];
        List<List<Integer>> result = new ArrayList<>();
        // 使用队列
        Queue<AbstractMap.SimpleEntry<Integer,Integer>> queue = new LinkedList<>();
        // 将开始顶点入队
        queue.add(new AbstractMap.SimpleEntry<>(startIndex,0));
        // 设置startIndex已经被访问
        visited[startIndex]=true;
        while(!queue.isEmpty()){
            AbstractMap.SimpleEntry<Integer,Integer> pair =  queue.poll();
            int key = pair.getKey(); //顶点的索引

            int val = pair.getValue();// 层

            if(result.size() == val){
                ArrayList list = new ArrayList();
                result.add(list);
            }
            List<Integer> levelList = result.get(val);
            levelList.add(key);
           // 找和key顶点直接相连的的索引
           List<Integer> list =  this.adj[key];
           for(int i=0;i<list.size();i++){
               if(!visited[list.get(i)]){
                   queue.add(new AbstractMap.SimpleEntry(list.get(i),val+1));
                   visited[list.get(i)]=true;
               }
           }
        }
       for(int i=0;i<result.size();i++){
           System.out.println("level:"+(i+1));
           for(int j=0;j<result.get(i).size();j++){
               System.out.format("%-4d",result.get(i).get(j));
           }
           System.out.println();
       }
    }



    public void dfs(int startIndex,int endIndex){
        //创建一个数组,用来记录是否已经被访问
        boolean visited[] = new boolean[this.N];
        // 标记开始结点已经被访问过
        LinkedList<Character> path = new LinkedList<>();
        dfs(startIndex,endIndex,visited,path);
    }

    // 递归向下去找
    private void dfs(int startIndex,int endIndex,boolean[] visited, LinkedList<Character> path){
        // 递归终止的条件
        if(startIndex == endIndex){
            path.offerLast(this.V[startIndex]);
            System.out.println(path);
            // 从路径的尾部删掉最后的顶点
            path.pollLast();
            return;
        }
        // 将当前顶点加到路径中去
        path.offer(this.V[startIndex]);
        // 标识startIndex已经被访问了
        visited[startIndex]=true;
        //  递归操作
        // 1、先找和startIndex直接连接的顶点有哪些
        List<Integer> list = this.adj[startIndex];
        // 2、处理每一个直接连接的顶点
        for(int i=0;i<list.size();i++){
            if(!visited[list.get(i)]){
                dfs(list.get(i),endIndex,visited,path);
            }
        }
        visited[startIndex]=false; // 回溯
        path.pollLast();
    }


    private class Vertex {
        char v;
        int index;

        //权值
        int weight;

        public Vertex(int index, char v, int weight) {
            this.index = index;
            this.v = v;
            this.weight = weight;
        }

        public Vertex(int index, char v) {
            this(index, v, 1);
        }
    }

    public static void main(String[] args) {
        char arr[] = {'A', 'E', 'F', 'G', 'H', 'P' };
        Graph03 graph03 = new Graph03(arr);
        // 邻接表
        List<Integer>[] adj = graph03.adj;
        adj[0].add(1);
        adj[0].add(2);
        adj[0].add(3);
        adj[1].add(0);
        adj[1].add(3);
        adj[1].add(4);
        adj[2].add(0);
        adj[3].add(0);
        adj[3].add(1);
        adj[3].add(4);
        adj[3].add(5);
        adj[4].add(1);
        adj[4].add(3);
        adj[4].add(5);
        adj[5].add(3);
        adj[5].add(4);
      
        graph03.bfs(5);
    }

}

迪杰斯特拉算法

概念即先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。

图论中的算法

 假设我们求A点到各点的最短距离

图论中的算法
迪杰斯特拉算法过程(原理)
package graphtheory;


import java.util.*;

// 图的单源最最短路径-迪杰斯特拉算法(从一个顶点到图中各个顶点的最短距离)
public class Graph04 {
    private char[] V;
    // 顶点数组
    private Vertex[] vertexs;
    private int N;
    // 邻接表
    private List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj; // key:顶点索引,val:权值

    public Graph04(char[] arr) { // {'A','E','F','G','H','P'}
        int length = arr.length;
        this.N = length;
        this.V = Arrays.copyOf(arr, length);
        // 构建图中的结点
        vertexs = new Vertex[length];
        for (int i = 0; i < length; i++) {
            vertexs[i] = new Vertex(i, this.V[i]);
        }
        this.adj = new List[length];
        for (int i = 0; i < this.N; i++) {
            this.adj[i] = new ArrayList<>();
        }
    }


    public int[] dijkstra(int sourceIndex) {
        // 1、创建距离表
        int[] dist = new int[this.N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 2、创建一个标识顶点是否被访问的数组
        boolean[] visited = new boolean[this.N];
        // 3、初始化距离表
        // 3-1
        dist[sourceIndex] = 0; // 自身到自身的距离
        visited[sourceIndex] = true;
        // 3-2、找和sourceIndex直接相连的顶点
        List<AbstractMap.SimpleEntry<Integer, Integer>> list = this.adj[sourceIndex];
        for (int i = 0; i < list.size(); i++) {
            AbstractMap.SimpleEntry<Integer, Integer> vertex = list.get(i);
            int key = vertex.getKey();//顶点索引
            int val = vertex.getValue();//权值
            // 3-3  更新距离表
            dist[key] = val;
        }

        for (int k = 1; k < this.N; k++) {
            //4、在上述的最短路径dist[]中,从未被访问的顶点中选一条最短的路径长度
            int minDist = Integer.MAX_VALUE;
            int minDistIndex = -1;
            for (int i = 0; i < this.N; i++) {
                if (!visited[i] && dist[i] != Integer.MAX_VALUE && dist[i] < minDist) {
                    minDist = dist[i];
                    minDistIndex = i;
                }
            }

            // 最最短的路径长度所在的顶点与其它顶点都没有相连
            if (minDistIndex == -1) {
                break;
            }

            //5、更新距离表()
            // 5-1 将最最短的路径长度所在的顶点设置成已访问
            visited[minDistIndex] = true;
            // 5-2 找到和最短路径长度所在顶点直接相连的顶点
            List<AbstractMap.SimpleEntry<Integer, Integer>> list2 = this.adj[minDistIndex];
            // 5-3 minDist+权值与距离表中的数据进行比较
            for (int i = 0; i < list2.size(); i++) {
                AbstractMap.SimpleEntry<Integer, Integer> vertex = list2.get(i);
                int key = vertex.getKey();//顶点索引
                int val = vertex.getValue();//权值
                int newVal = minDist + val;
                if (!visited[key] && newVal < dist[key]) {
                    dist[key] = newVal;
                }
            }
        }
        return dist;
    }


    private class Vertex {
        char v;
        int index;

        public Vertex(int index, char v) {
            this.index = index;
            this.v = v;
        }
    }

    public static void main(String[] args) {
        char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
        Graph04 graph04 = new Graph04(arr);
        // 邻接表
        List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj = graph04.adj;

        adj[0].add(new AbstractMap.SimpleEntry<>(1, 5));
        adj[0].add(new AbstractMap.SimpleEntry<>(2, 4));
        adj[0].add(new AbstractMap.SimpleEntry<>(5, 2));

        adj[1].add(new AbstractMap.SimpleEntry<>(0, 5));
        adj[1].add(new AbstractMap.SimpleEntry<>(5, 1));
        adj[1].add(new AbstractMap.SimpleEntry<>(4, 3));

        adj[2].add(new AbstractMap.SimpleEntry<>(0, 4));
        adj[3].add(new AbstractMap.SimpleEntry<>(4, 3));
        adj[3].add(new AbstractMap.SimpleEntry<>(5, 4));
        adj[4].add(new AbstractMap.SimpleEntry<>(1, 3));
        adj[4].add(new AbstractMap.SimpleEntry<>(5, 2));
        adj[4].add(new AbstractMap.SimpleEntry<>(3, 3));
        adj[5].add(new AbstractMap.SimpleEntry<>(0, 2));
        adj[5].add(new AbstractMap.SimpleEntry<>(1, 1));
        adj[5].add(new AbstractMap.SimpleEntry<>(4, 2));
        adj[5].add(new AbstractMap.SimpleEntry<>(3, 4));

        int[] dist = graph04.dijkstra(0);
        System.out.println(Arrays.toString(dist));
    }

}

 怎么样才能求出我们距离最短的路径呢?

我们这里需要一个前置顶点表进行记录:

图论中的算法

 分图:

图论中的算法

图论中的算法

package graphtheory;


import java.util.*;

// 图的单源最最短路径-迪杰斯特拉算法(从一个顶点到图中各个顶点的最短距离)
public class Graph04 {
    private char[] V;
    // 顶点数组
    private Vertex[] vertexs;
    private int N;
    // 邻接表
    private List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj; // key:顶点索引,val:权值

    // 1、创建距离表
    private int[] dist;
    private int[] pre;
    public Graph04(char[] arr) { // {'A','E','F','G','H','P'}
        int length = arr.length;
        this.N = length;
        this.V = Arrays.copyOf(arr, length);

        this.dist = new int[this.N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 创建最短路径的前驱顶点表(为了表示最短路径)
        this.pre=new int[this.N];
        Arrays.fill(this.pre,-1);
        // 构建图中的结点
        vertexs = new Vertex[length];
        for (int i = 0; i < length; i++) {
            vertexs[i] = new Vertex(0, this.V[i]);
        }
        this.adj = new List[length];
        for (int i = 0; i < this.N; i++) {
            this.adj[i] = new ArrayList<>();
        }
    }


    public void dijkstra(int sourceIndex) {


        // 2、创建一个标识顶点是否被访问的数组
        boolean[] visited = new boolean[this.N];
        // 3、初始化距离表
        // 3-1
        dist[sourceIndex] = 0; // 自身到自身的距离
        visited[sourceIndex] = true;
        // 3-2、找和sourceIndex直接相连的顶点
        List<AbstractMap.SimpleEntry<Integer, Integer>> list = this.adj[sourceIndex];
        for (int i = 0; i < list.size(); i++) {
            AbstractMap.SimpleEntry<Integer, Integer> vertex = list.get(i);
            int key = vertex.getKey();//顶点索引
            int val = vertex.getValue();//权值
            // 3-3  更新距离表
            this.dist[key] = val;
            // 更新前驱顶点表
            this.pre[key]=sourceIndex;
        }

        for (int k = 1; k < this.N; k++) {
            //4、在上述的最短路径dist[]中,从未被访问的顶点中选一条最短的路径长度
            int minDist = Integer.MAX_VALUE;
            int minDistIndex = -1;
            for (int i = 0; i < this.N; i++) {
                if (!visited[i] && dist[i] != Integer.MAX_VALUE && dist[i] < minDist) {
                    minDist = dist[i];
                    minDistIndex = i;
                }
            }

            // 最最短的路径长度所在的顶点与其它顶点都没有相连
            if (minDistIndex == -1) {
                break;
            }

            //5、更新距离表()
            // 5-1 将最最短的路径长度所在的顶点设置成已访问
            visited[minDistIndex] = true;
            // 5-2 找到和最短路径长度所在顶点直接相连的顶点
            List<AbstractMap.SimpleEntry<Integer, Integer>> list2 = this.adj[minDistIndex];
            // 5-3 minDist+权值与距离表中的数据进行比较
            for (int i = 0; i < list2.size(); i++) {
                AbstractMap.SimpleEntry<Integer, Integer> vertex = list2.get(i);
                int key = vertex.getKey();//顶点索引
                int val = vertex.getValue();//权值
                int newVal = minDist + val;
                if (!visited[key] && newVal < dist[key]) {
                    this.dist[key] = newVal;
                    // 更新前驱顶点表
                    this.pre[key] = minDistIndex;
                }
            }
        }
    }

    public void showDist(){
        System.out.println(Arrays.toString(this.dist));
    }

    public void getMinDist(int sourceIndex ,int targetIndex){
        Stack<Integer> stack = new Stack<>();
        stack.push(targetIndex);
        int preIndex = this.pre[targetIndex];
        while(preIndex !=-1 && preIndex!=sourceIndex){
            stack.push(preIndex);
            preIndex = this.pre[preIndex];
        }
        // 将 sourceIndex放入栈
        if(preIndex !=-1){
            stack.push(sourceIndex);
        }

        // 出栈
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()){
            res.append(this.V[stack.pop()]+"-->");
        }
        System.out.println(res);
    }


    private class Vertex {
        char v;
        int index;

        public Vertex(int index, char v) {
            this.index = index;
            this.v = v;
        }
    }

    public static void main(String[] args) {
        char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
        Graph04 graph04 = new Graph04(arr);
        // 邻接表
        List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj = graph04.adj;

        adj[0].add(new AbstractMap.SimpleEntry<>(1, 5));
        adj[0].add(new AbstractMap.SimpleEntry<>(2, 4));
        adj[0].add(new AbstractMap.SimpleEntry<>(5, 2));

        adj[1].add(new AbstractMap.SimpleEntry<>(0, 5));
        adj[1].add(new AbstractMap.SimpleEntry<>(5, 1));
        adj[1].add(new AbstractMap.SimpleEntry<>(4, 3));

        adj[2].add(new AbstractMap.SimpleEntry<>(0, 4));
        adj[3].add(new AbstractMap.SimpleEntry<>(4, 3));
        adj[3].add(new AbstractMap.SimpleEntry<>(5, 4));
        adj[4].add(new AbstractMap.SimpleEntry<>(1, 3));
        adj[4].add(new AbstractMap.SimpleEntry<>(5, 2));
        adj[4].add(new AbstractMap.SimpleEntry<>(3, 3));
        adj[5].add(new AbstractMap.SimpleEntry<>(0, 2));
        adj[5].add(new AbstractMap.SimpleEntry<>(1, 1));
        adj[5].add(new AbstractMap.SimpleEntry<>(4, 2));
        adj[5].add(new AbstractMap.SimpleEntry<>(3, 4));

        int sourceIndex = 5;
        graph04.dijkstra(sourceIndex);
        graph04.showDist();

        int targetIndex = 3;
        // 求从源到目标顶点的最短路径
        graph04.getMinDist(sourceIndex,targetIndex);
    }

}

弗洛伊德算法

具体思想邻接矩阵dist储存路径,同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值,而自身到自身的长度为0.

图论中的算法

 A和B不认识,所以A找不到B,但是这时候A的朋友D来了,说他可以介绍B给A认识,所以A就通过D找到了B

图论中的算法

 弗洛伊德算法就是用了这样的思想

图论中的算法图论中的算法

  • 把第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
  • 而上述试探具体方法为遍历图中每一个点(i,j双重循环),判断每一个点对距离,是否因为加入的点而发生最小距离变化。如果发生改变,那么两点(i,j)距离就更改。 
  •  转移方程::dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

图论中的算法

图论中的算法

图论中的算法文章来源地址https://www.toymoban.com/news/detail-474557.html

package graphtheory;


import java.util.*;

// 图的多源最最短路径-弗洛伊德算法Floyd(从任意顶点到图中各个顶点的最短距离)
public class Graph05 {
    private char[] V;
    // 顶点数组
    private Vertex[] vertexs;
    private int N;
    // 邻接表
    private List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj; // key:顶点索引,val:权值

    private int[][] dists;

    public Graph05(char[] arr) { // {'A','E','F','G','H','P'}
        int length = arr.length;
        this.N = length;
        this.V = Arrays.copyOf(arr, length);
        // 构建图中的结点
        vertexs = new Vertex[length];
        for (int i = 0; i < length; i++) {
            vertexs[i] = new Vertex(0, this.V[i]);
        }
        this.adj = new List[length];
        for (int i = 0; i < this.N; i++) {
            this.adj[i] = new ArrayList<>();
        }
        this.dists = new int[this.N][this.N];
        for (int i = 0; i < this.N; i++) {
            for (int j = 0; j < this.N; j++) {
                if (i == j) {
                    this.dists[i][j] = 0;
                } else {
                    this.dists[i][j] = Integer.MAX_VALUE;
                }
            }
        }
    }


    private class Vertex {
        char v;
        int index;

        public Vertex(int index, char v) {
            this.index = index;
            this.v = v;
        }
    }

    public void floyd() {
        // 对dists进一步初始化
        for (int i = 0; i < this.N; i++) {
            List<AbstractMap.SimpleEntry<Integer, Integer>> list = this.adj[i];
            for (int j = 0; j < list.size(); j++) {
                AbstractMap.SimpleEntry<Integer, Integer> pair = list.get(j);
                int key = pair.getKey();
                int val = pair.getValue();
                this.dists[i][key] = val;
            }
        }

        // 将每个顶点加到二维数组中(是给每个二维数组中的每个元素都加) 相当于矩阵,给每个元素进行相同的操作
        for (int i = 0; i < this.N; i++) { // 表示的添加顶点的索引
            for (int m = 0; m < this.N; m++) {
                //同行不用进行操作
                if (m == i) {
                    continue;
                }
                for (int n = 0; n < this.N; n++) {
                //距离无穷大也不用进行操作
                    if (this.dists[m][i] != Integer.MAX_VALUE && this.dists[i][n] != Integer.MAX_VALUE) {
                        this.dists[m][n] = Math.min(this.dists[m][n], this.dists[m][i] + this.dists[i][n]);
                    }
                }
            }
        }
        show();
    }

    private void show() {
        System.out.format("%-4s", " ");
        for (int i = 0; i < this.N; i++) {
            System.out.format("%-4s", this.V[i]);
        }
        System.out.println();
        for (int i = 0; i < this.N; i++) {
            System.out.format("%-4s", this.V[i]);
            for (int j = 0; j < this.N; j++) {
                System.out.format("%-4s", this.dists[i][j] == Integer.MAX_VALUE ? "-" : this.dists[i][j] + "");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        char arr[] = {'A', 'E', 'F', 'G', 'H', 'P'};
        Graph05 graph05 = new Graph05(arr);
        // 邻接表
        List<AbstractMap.SimpleEntry<Integer, Integer>>[] adj = graph05.adj;

        adj[0].add(new AbstractMap.SimpleEntry<>(1, 5));
        adj[0].add(new AbstractMap.SimpleEntry<>(2, 4));
        adj[0].add(new AbstractMap.SimpleEntry<>(5, 2));

        adj[1].add(new AbstractMap.SimpleEntry<>(0, 5));
        adj[1].add(new AbstractMap.SimpleEntry<>(5, 1));
        adj[1].add(new AbstractMap.SimpleEntry<>(4, 3));

        adj[2].add(new AbstractMap.SimpleEntry<>(0, 4));
        adj[3].add(new AbstractMap.SimpleEntry<>(4, 3));
        adj[3].add(new AbstractMap.SimpleEntry<>(5, 4));
        adj[4].add(new AbstractMap.SimpleEntry<>(1, 3));
        adj[4].add(new AbstractMap.SimpleEntry<>(5, 2));
        adj[4].add(new AbstractMap.SimpleEntry<>(3, 3));
        adj[5].add(new AbstractMap.SimpleEntry<>(0, 2));
        adj[5].add(new AbstractMap.SimpleEntry<>(1, 1));
        adj[5].add(new AbstractMap.SimpleEntry<>(4, 2));
        adj[5].add(new AbstractMap.SimpleEntry<>(3, 4));

        graph05.floyd();
        int sourceIndex = 1;
        int targetIndex = 3;

    }

}

到了这里,关于图论中的算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 线性代数在图论中的应用

    图论是一门研究有限数量的点(节点)和它们之间的关系(边)的学科。图论在计算机科学、数学、物理、生物学和社会科学等领域具有广泛的应用。线性代数则是一门研究向量和矩阵的学科,它在许多领域中都有着重要的应用,包括物理学、生物学、经济学和人工智能等。

    2024年02月03日
    浏览(45)
  • 矩阵范数与图论: 在图论中的应用和理论基础

    矩阵范数和图论是计算机科学和数学领域中的两个重要概念。矩阵范数是一种用于衡量矩阵“大小”的度量,而图论则是用于描述和分析网络结构的工具。在本文中,我们将探讨这两个领域之间的联系,并讨论它们在实际应用中的重要性。 矩阵范数的概念可以追溯到19世纪的

    2024年04月10日
    浏览(35)
  • 图论中的聚类系数(Clustering coefficient)简单介绍

    在GraphSage论文的理论分析部分,涉及到一个概念叫做“ Clustering coefficient” ,直译过来就是 聚类系数 ,解释为“节点的一跳邻域内封闭的三角形的比例”,本文对其做一个简单的介绍。本文参考了 Wiki百科-Clustering coefficient。 更:关于GraphSage论文详解,请参见博文《GraphSag

    2023年04月09日
    浏览(39)
  • 图论与算法(1)图论概念

    在计算机科学中,图论与算法是两个重要且紧密相关的领域。图论研究图的性质和特征,而算法设计和分析解决问题的方法和步骤。图论提供了一种形式化的方法来描述和分析各种关系和连接,而算法则为解决图相关的问题提供了有效的解决方案。 图论是研究图的结构和性质

    2024年02月07日
    浏览(41)
  • Git的核心概念:探索Git中的提交、分支、合并、标签等核心概念,深入理解其作用和使用方法

    🌷🍁 博主 libin9iOak带您 Go to New World.✨🍁 🦄 个人主页——libin9iOak的博客🎐 🐳 《面试题大全》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 🌊 《IDEA开发秘籍》学会IDEA常用操作,工作效率翻倍~💐 🪁🍁 希望本文能够给您带来一定的帮助🌸文章粗浅,敬

    2024年02月16日
    浏览(48)
  • 详细介绍MATLAB中的图论算法

    MATLAB是一种功能强大的编程语言和环境,提供了许多用于图论算法的工具和函数。图论是研究图及其属性和关系的数学分支,广泛应用于计算机科学、网络分析、社交网络分析等领域。在MATLAB中,我们可以使用图论算法来解决各种问题,如最短路径问题、最小生成树问题、最

    2024年02月16日
    浏览(48)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(49)
  • 搜索与图论 - 搜索与图在算法中的应用【中】

    目录 迪杰斯特拉算法Dijkstra  Dijkstra求最短路 I Dijkstra求最短路 II 贝尔曼-福特算法 bellman-ford 有边数限制的最短路 SPFA算法 spfa求最短路  spfa判断负环 Floyd Floyd求最短路   该算法不能存在负权边 思路: 初始化距离数组, dist[1] = 0, dist[i] = inf; for n次循环 每次循环确定一个min加

    2023年04月08日
    浏览(78)
  • 聚类算法与图论的结合:社交网络中的社群发现

    社交网络是现代互联网的重要组成部分,它们为人们提供了一种高效的沟通和交流方式。社交网络中的社群发现是一种常见的数据挖掘任务,它旨在识别网络中的社群结构,以便更好地理解网络中的信息传播和社交行为。 社群发现是一种无监督的学习方法,它通过对网络中的

    2024年04月24日
    浏览(37)
  • 图论相关基本概念

    从逻辑结构上讲,图是一种典型的 非线性结构 。 图(Graph) 是由 顶点的有穷非空集合和顶点之间边的集合 组成的,通常表示为 G(V , E) ,其中, G表示—个图,V是图G中顶点的集合,E是图G中边的集合。其中: 顶点集合V={x|x属于某个数据对象集}是有穷非空集合 E={(x,y)|

    2024年02月01日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包