栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

蛮力法/邻接矩阵 深度优先 有向带权图 无方向带权图

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

蛮力法/邻接矩阵 深度优先 有向带权图 无方向带权图

有方向带权重图-邻接矩阵:

  • 出度看行
  • 入度看列

无向带权图-邻接矩阵:

  • 对称阵
  • 主对角线上全为0
package xcrj.kchalgorithm.bruteForce.graph;


public class DFS {
    static int n = 5;
    static int[] visited = new int[n];

    
    static void dfs(MGraph mGraph, int vertex) {
        // 访问 再 置于访问标识
//        System.out.println(" 点:" + vertex + " ");
        visited[vertex] = 1;
        // 获取这个点的所有邻接点&&没有访问的点 再 递归
        for (int i = 0; i < mGraph.getN(); i++) {
            if (mGraph.getEdges()[vertex][i] > 0 && mGraph.getEdges()[vertex][i] < Float.MAX_VALUE && visited[i] == 0) {
                System.out.println(" 点" + vertex + "-权值" + mGraph.getEdges()[vertex][i] + "->点" + i);
                dfs(mGraph, i);
            }
        }
    }

    
    public static void directedWeightedGraph() {
        int n = DFS.n;
        int e = 6;
        MVertex[] mVertices = new MVertex[n];
        for (int i = 0; i < n; i++) {
            mVertices[i] = new MVertex(i, (char) i);
        }
        int[][] edges = new int[n][n];
        edges[0][4] = 6;
        edges[1][0] = 9;
        edges[1][2] = 3;
        edges[2][0] = 2;
        edges[2][3] = 5;
        edges[3][4] = 1;
        MGraph mGraph = new MGraph(n, e, mVertices, edges);
        // 有方向带权值连通图
        for (int i = 0; i < n; i++) {
            System.out.println("从" + i + "出发");
            dfs(mGraph, i);
        }
    }

    
    public static void undirectedWeightedGraph() {
        int n = DFS.n;
        int e = 6;
        MVertex[] mVertices = new MVertex[n];
        for (int i = 0; i < n; i++) {
            mVertices[i] = new MVertex(i, (char) i);
        }
        int[][] edges = new int[n][n];
        edges[0][4] = 6;
        edges[4][0] = 6;
        edges[0][1] = 9;
        edges[1][0] = 9;
        edges[1][2] = 3;
        edges[2][1] = 3;
        edges[0][2] = 2;
        edges[2][0] = 2;
        edges[2][3] = 5;
        edges[3][2] = 5;
        edges[3][4] = 1;
        edges[4][3] = 1;
        MGraph mGraph = new MGraph(n, e, mVertices, edges);
        // 有方向带权值连通图
        for (int i = 0; i < n; i++) {
            System.out.println("从" + i + "出发");
            dfs(mGraph, i);
        }
    }

    public static void main(String[] args) {
        directedWeightedGraph();
//        undirectedWeightedGraph();
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/951045.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号