邻接矩阵无向图(三) Java详解

邻接矩阵无向图的介绍

邻接矩阵无向图是指通过邻接矩阵表示的无向图。

上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。由于这是无向图,所以边(A,C)和边(C,A)是同一条边;这里列举边时,是按照字母先后顺序列举的。

上图右边的矩阵是G1在内存中的邻接矩阵示意图。A[i][j]=1表示第i个顶点与第j个顶点是邻接点,A[i][j]=0则表示它们不是邻接点;而A[i][j]表示的是第i行第j列的值;例如,A[1,2]=1,表示第1个顶点(即顶点B)和第2个顶点(C)是邻接点。

邻接矩阵无向图的代码说明

1. 基本定义

public class MatrixUDG {

    private char[] mVexs;       // 顶点集合
    private int[][] mMatrix;    // 邻接矩阵

    ...
}

MatrixUDG是邻接矩阵对应的结构体。mVexs用于保存顶点,mMatrix则是用于保存矩阵信息的二维数组。例如,mMatrix[i][j]=1,则表示"顶点i(即mVexs[i])"和"顶点j(即mVexs[j])"是邻接点;mMatrix[i][j]=0,则表示它们不是邻接点。

2. 创建矩阵

这里介绍提供了两个创建矩阵的方法。一个是用已知数据,另一个则需要用户手动输入数据

2.1 创建图(用已提供的矩阵)

/*
 * 创建图(用已提供的矩阵)
 *
 * 参数说明:
 *     vexs  -- 顶点数组
 *     edges -- 边数组
 */
public MatrixUDG(char[] vexs, char[][] edges) {

    // 初始化"顶点数"和"边数"
    int vlen = vexs.length;
    int elen = edges.length;

    // 初始化"顶点"
    mVexs = new char[vlen];
    for (int i = 0; i < mVexs.length; i++)
        mVexs[i] = vexs[i];

    // 初始化"边"
    mMatrix = new int[vlen][vlen];
    for (int i = 0; i < elen; i++) {
        // 读取边的起始顶点和结束顶点
        int p1 = getPosition(edges[i][0]);
        int p2 = getPosition(edges[i][1]);

        mMatrix[p1][p2] = 1;
        mMatrix[p2][p1] = 1;
    }
}

该函数的作用是利用已知数据来创建一个邻接矩阵无向图。 实际上,在本文的测试程序源码中,该方法创建的无向图就是上面图G1。具体的调用代码如下:

char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char[][] edges = new char[][]{
        {'A', 'C'},
        {'A', 'D'},
        {'A', 'F'},
        {'B', 'C'},
        {'C', 'D'},
        {'E', 'G'},
        {'F', 'G'}};
    MatrixUDG pG;

    pG = new MatrixUDG(vexs, edges);

更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索数组
, int
, 矩阵
, 无向图 邻接表数
, java 矩阵
, char
, 顶点
, char a[]和int a[]c
, 矩阵拓扑信息参数图
, #Char图
, 数组 矩阵 C
, 螺旋矩阵详解
邻接矩阵
java邻接矩阵、java邻接矩阵最短路径、邻接矩阵、有向图的邻接矩阵、图的邻接矩阵,以便于您获取更多的相关知识。

时间: 2024-10-28 22:35:42

邻接矩阵无向图(三) Java详解的相关文章

邻接表无向图(三) Java详解

邻接表无向图的介绍 邻接表无向图是指通过邻接表表示的无向图. 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边. 上图右边的矩阵是G1在内存中的邻接表示意图.每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号".例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3":而这"

邻接矩阵有向图(三) Java详解

邻接矩阵有向图的介绍 邻接矩阵有向图是指通过邻接矩阵表示的有向图. 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9条边.   上图右边的矩阵是G2在内存中的邻接矩阵示意图.A[i][j]=1表示第i个顶点到第j个顶点是一条边

Dijkstra算法(三) Java详解

迪杰斯特拉算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径. 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止. 基本思想 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算). 此外,引进两个集合S和U.S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离). 初始时,S中只有起点s:U中是除s之外的顶点,并且U中

Floyd算法(三) Java详解

弗洛伊德算法介绍 和Dijkstra算法一样,弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法.该算法名称以创始人之一.1978年图灵奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名. 基本思想 通过Floyd计算图G=(V,E)中各个顶点的最短路径时,需要引入一个矩阵S,矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离. 假设图G中顶点个数为N,则需要对矩阵S进行N次更新.初始时,矩阵S中顶点a[i][j]的距离为顶点i到顶点

邻接表有向图(三) Java详解

邻接表有向图的介绍 邻接表有向图是指通过邻接表表示的有向图. 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9条边. 上图右边的矩阵是G2在内存中的邻接表示意图.每一个顶点都包含一条链表,该链表记录了"该顶点所对应的

邻接矩阵无向图(二) C++详解

邻接矩阵无向图的介绍 邻接矩阵无向图是指通过邻接矩阵表示的无向图. 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边.由于这是无向图,所以边(A,C)和边(C,A)是同一条边:这里列举边时,是按照字母先后顺序列举的. 上图右边的矩阵是G1在内存中的邻接矩阵示意图.A[i][j]=1表示第i个顶点与第j个顶点是邻接点,A[i][j]=0则表示它们不是邻接

哈夫曼树(三) Java详解

哈夫曼树的介绍 Huffman Tree,中文名是哈夫曼树或霍夫曼树,它是最优二叉树. 定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树.这个定义里面涉及到了几个陌生的概念,下面就是一颗哈夫曼树,我们来看图解答. (01) 路径和路径长度 定义:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1. 例子:100和80的路径长度是

拓扑排序(三) Java详解

拓扑排序介绍 拓扑排序(Topological Order)是指,将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列. 这样说,可能理解起来比较抽象.下面通过简单的例子进行说明! 例如,一个项目包括A.B.C.D四个子部分来完成,并且A依赖于B和D,C依赖于D.现在要制定一个计划,写出A.B.C.D的执行顺序.这时,就可以利用到拓扑排序,它就是用来确定事物发生的顺序的. 在拓扑排序中,如果存在一条从顶点A到顶点B的路径,那么在排序结果中B

Kruskal算法(三) Java详解

最小生成树 在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树. 例如,对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树. 克鲁斯卡尔算法介绍 克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法. 基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路. 具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回