前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图的邻接矩阵数据结构(基础) 顶

图的邻接矩阵数据结构(基础) 顶

作者头像
算法之名
发布2019-08-20 10:49:54
4150
发布2019-08-20 10:49:54
举报
文章被收录于专栏:算法之名
代码语言:javascript
复制
import java.util.Scanner;

/**
 * Created by Administrator on 2018-02-14.
 */
public class Graph {
    static final int MaxNum = 20;
    static final int MaxValue = 65535;

    public void CreateGraph(GraphMatrix GM) {
        int i, j, k;
        int weight;
        char EstartV, EendV;
        Scanner input = new Scanner(System.in);
        System.out.println("输入图中各顶点信息");
        for (i = 0; i < GM.VertexNum; i++) {
            System.out.printf("第%d个顶点:", i + 1);
            GM.Vertex[i] = (input.next().toCharArray())[0];
        }
        System.out.printf("输入构成各条边的顶点及权值:\n");
        for (k = 0; k < GM.EdgeNum; k++) {
            System.out.printf("第%d条边:", k + 1);
            EstartV = input.next().charAt(0);
            EendV = input.next().charAt(0);
            weight = input.nextInt();
            for (i = 0; EstartV != GM.Vertex[i]; i++) ;
            for (j = 0; EendV != GM.Vertex[j]; j++) ;
            GM.EdgeWeight[i][j] = weight;
            if (GM.GType == 0) {
                GM.EdgeWeight[j][i] = weight;
            }
        }
    }
    public void ClearGraph(GraphMatrix GM) {
        int i,j;
        for (i = 0;i < GM.VertexNum;i++) {
            for (j = 0;j < GM.VertexNum;j++) {
                GM.EdgeWeight[i][j] = MaxValue;
            }
        }
    }
    public void OutGraph(GraphMatrix GM) {
        int i,j;
        for (j = 0;j < GM.VertexNum;j++) {
            System.out.printf("\t%c",GM.Vertex[j]);
        }
        System.out.printf("\n");
        for (i = 0;i < GM.VertexNum;i++) {
            System.out.printf("%c",GM.Vertex[i]);
            for (j = 0;j < GM.VertexNum;j++) {
                if(GM.EdgeWeight[i][j] == MaxValue) {
                    System.out.printf("\tZ");
                }else {
                    System.out.printf("\t%d",GM.EdgeWeight[i][j]);
                }
            }
            System.out.printf("\n");
        }
    }
    public void DeepTraOne(GraphMatrix GM,int n) {
        int i;
        GM.isTrav[n] = 1;
        System.out.printf("->%c",GM.Vertex[n]);
        for (i = 0;i < GM.VertexNum;i++) {
            if(GM.EdgeWeight[n][i] != MaxValue && GM.isTrav[n] == 0) {
                DeepTraOne(GM,i);
            }
        }
    }
    public void DeepTraGraph(GraphMatrix GM) {
        int i;
        for (i = 0;i < GM.VertexNum;i++) {
            GM.isTrav[i] = 0;
        }
        System.out.printf("深度优先遍历结点:");
        for (i = 0;i < GM.VertexNum;i++) {
            if(GM.isTrav[i] == 0) {
                DeepTraOne(GM,i);
            }
        }
        System.out.printf("\n");
    }
    public static void main(String[] args) {
        GraphMatrix GM = new GraphMatrix();
        Graph gh = new Graph();
        System.out.printf("输入生成图的类型:");
        Scanner input = new Scanner(System.in);
        GM.GType = input.nextInt();
        System.out.printf("输入图的顶点数量:");
        GM.VertexNum = input.nextInt();
        System.out.printf("输入图的边数量:");
        GM.EdgeNum = input.nextInt();
        gh.ClearGraph(GM);
        gh.CreateGraph(GM);
        System.out.printf("该图的邻接矩阵数据如下:\n");
        gh.OutGraph(GM);
        gh.DeepTraGraph(GM);
    }
}
class GraphMatrix {
    char[] Vertex = new char[Graph.MaxNum];
    int GType;
    int VertexNum;
    int EdgeNum;
    int[][] EdgeWeight = new int[Graph.MaxNum][Graph.MaxNum];
    int[] isTrav = new int[Graph.MaxNum];
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档