用邻接矩阵存储图

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

一 点睛

邻接矩阵通常采用一个一维数组存储图中节点的信息,采用一个二维数组存储图中节点之间的邻接关系。

邻接矩阵可以用来表示无向图、有向图和网。

1 无向图的邻接矩阵

在无向图中,若从节点 Vi 到节点 Vj 有边,则邻接矩阵 M[i][j] = M[j][i ]= 1,否则 M[i][j] = 0。

无向图的邻接矩阵的特定如下。

a 无向图的邻接矩阵是对称矩阵,并且是唯一的。

b 第 I 行或第 i 列非零的个数正好是第 i 个节点的度。

2 有向图的邻接矩阵

在有向图中,若从节点 Vi 到节点 Vj 有边,则邻接矩阵 M[i][j]=1,否则 M[i][j]=0 。

有向图的邻接矩阵的特定如下。

a 有向图的邻接矩阵不一定是对称的。

b 第 i 行非零元素的个数正好是第 i 个节点的出度,第 i 列非零元素的个数正好是第 i 个节点的入度。

3 网的邻接矩阵

网是带权图,需要存储边的权值,则邻接矩阵表示为:M[i][j] = Wij,其他情况为无穷大。

二 算法步骤

1 输入节点数和边数。

2 依次输入节点信息,将其存储到节点数组 Vex[] 中。

3 初始化邻接矩阵,如果是图,则将其初始化为0,如果是网,则将其初始化为无穷大。

4 依次输入每条边依附的两个节点,如果是网,则还需要输入该边的权值。

  • 如果是无向图,则输入a,b,查询节点a、b在节点数组 Vex[] 中的存储下标 i、j,让 Edge[i][j]=Edge[j][i]=1。
  • 如果是有向图,则输入a,b,查询节点a、b在节点数组 Vex[] 中的存储下标 i、j,让 Edge[i][j]=1。
  • 如果是无向网,则输入a,b,w,查询节点a、b在节点数组 Vex[] 中的存储下标 i、j,让 Edge[i][j]=Edge[j][i]=w。
  • 如果是有向网,则输入a,b,w,查询节点a、b在节点数组 Vex[] 中的存储下标 i、j,让 Edge[i][j]=w。

三 实现

package graph;

import java.util.Scanner;

public class CreateAMGraph {
    static final int MaxVnum = 100;  // 顶点数最大值

    static int locatevex(AMGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
            if (x == G.Vex[i])
                return i;
        return -1; // 没找到
    }

    static void CreateAMGraph(AMGraph G) {
        Scanner scanner = new Scanner(System.in);
        int i, j;
        char u, v;
        System.out.println("请输入顶点数:");
        G.vexnum = scanner.nextInt();
        System.out.println("请输入边数:");
        G.edgenum = scanner.nextInt();
        System.out.println("请输入顶点信息:");

        // 输入顶点信息,存入顶点信息数组
        for (int k = 0; k < G.vexnum; k++) {
            G.Vex[k] = scanner.next().charAt(0);
        }
        //初始化邻接矩阵所有值为0,如果是网,则初始化邻接矩阵为无穷大
        for (int m = 0; m < G.vexnum; m++)
            for (int n = 0; n < G.vexnum; n++)
                G.Edge[m][n] = 0;

        System.out.println("请输入每条边依附的两个顶点:");
        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);

            i = locatevex(G, u);// 查找顶点 u 的存储下标
            j = locatevex(G, v);// 查找顶点 v 的存储下标
            if (i != -1 && j != -1)
                G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1
            else {
                System.out.println("输入顶点信息错!请重新输入!");
                G.edgenum++; // 本次输入不算
            }
        }
    }

    static void print(AMGraph G) { // 输出邻接矩阵
        System.out.println("图的邻接矩阵为:");
        for (int i = 0; i < G.vexnum; i++) {
            for (int j = 0; j < G.vexnum; j++)
                System.out.print(G.Edge[i][j] + "\t");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AMGraph G = new AMGraph();
        CreateAMGraph(G);
        print(G);
    }
}

class AMGraph {
    char Vex[] = new char[CreateAMGraph.MaxVnum];
    int Edge[][] = new int[CreateAMGraph.MaxVnum][CreateAMGraph.MaxVnum];
    int vexnum; // 顶点数
    int edgenum; // 边数
}

四 测试

绿色为输入,白色为输出。

用邻接矩阵存储图

 文章来源地址https://www.toymoban.com/news/detail-474402.html

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

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

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

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包