图的存储

1，邻接矩阵存储法

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。

图的存储

特点：无向图的邻接矩阵是对称的；

顶点i 的度＝第 i 行 (列) 中1 的个数；

java实现代码如下：

package com.graph;

import java.util.Scanner;

/*
 * 定义图的结构
 */
class Graph1 {
    //节点数目
    static final int MaxNum=20;
    //顶点数组
    static String[] Vertex = new String[MaxNum];
    //权值
    static int weight;
    //图的类型0：无向图  1：有向图
    static int GType;
    //顶点的数量
    static int VertxNum;
    //边的数量
    static int EdgeNum;
    //邻接矩阵
    static int[][] EdgeWeight = new int[MaxNum][MaxNum];

    //创建邻接矩阵图
    static void createGraph(){
        int i ,  j  ,  k;
        Scanner scan = new Scanner(System.in);
        System.out.println("输入顶点的个数");
        VertxNum = scan.nextInt();
        System.out.println("输入边的个数");
        EdgeNum = scan.nextInt();
        System.out.println("输入图的类型");
        GType = scan.nextInt();

        String EstartV,EndV;      //边的起始顶点

        System.out.println("输入各顶点");
        for(i=0; i < VertxNum; i++)
        {
            Vertex[i] = scan.next();
        }


        System.out.println("输入构成个遍的顶点和权值");
        for(k=0;k<EdgeNum;k++)
        {
            System.out.println("请按‘头节点 尾节点 权值 回车’的形式依次输入边的信息");
            EstartV = scan.next();
            EndV = scan.next();
            weight = scan.nextInt();

            //在已有顶点中查找开始节点的位置
            for(i=0; !EstartV.equals(Vertex[i]) ; i++);

            //在已有节点上查找终结点的位置
            for(j=0; !EndV.equals(Vertex[j]); j++);

            //对应位置保存权重
            EdgeWeight[i][j] = weight;

            //如果是无向图，在对角位置保存权重
            if(GType == 0) {
                EdgeWeight[j][i] = weight;
            }
        }
    }

    //输出邻接矩阵
    static void OutGraph(){
        int i,j;
        for(j = 0; j < VertxNum;j ++)
            System.out.print("\t" +Vertex[j]);      //在第一行输入顶点信息
        System.out.println();

        for(i =0 ;i <VertxNum; i ++)
        {
            System.out.print( Vertex[i]);
            for(j = 0;j < VertxNum; j++)
            {
                if(EdgeWeight[i][j] == 0)    //若权值为0
                    System.out.print("\t0");
                else
                    System.out.print("\t" + EdgeWeight[i][j]);  //输出边的权重
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        createGraph();
        OutGraph();
    }

}

输入顶点的个数
5
输入边的个数
7
输入图的类型
0
输入各顶点
v1 v2 v3 v4 v5
输入构成个遍的顶点和权值
请按‘头节点 尾节点 权值 回车’的形式依次输入边的信息
v1 v2 0
请按‘头节点 尾节点 权值 回车’的形式依次输入边的信息
v1 v4 1
请按‘头节点 尾节点 权值 回车’的形式依次输入边的信息
v2 v5 1
请按‘头节点 尾节点 权值 回车’的形式依次输入边的信息
v3 v2 1
请按‘头节点 尾节点 权值 回车’的形式依次输入边的信息
v3 v5 1
请按‘头节点 尾节点 权值 回车’的形式依次输入边的信息
v4 v3 1
请按‘头节点 尾节点 权值 回车’的形式依次输入边的信息
v4 v5 1
	v1	v2	v3	v4	v5
v1	0	0	0	1	0
v2	0	0	1	0	1
v3	0	1	0	1	1
v4	1	0	1	0	1
v5	0	1	1	1	0

优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。

缺点： n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。

2，邻接表存储法

对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来

图的存储

Java实现代码

package com.graph;

/**
 * 图的邻接表表示法
 */

import java.util.Scanner;

/**
 * 顶点表类
 * */
class Vertex{
    public String data;
    public Edge firstage;
}

/**
 * 边表类
 */
class Edge{
    public String adhvex;
    public Edge next;
}

public class Graph {
    /**
     * 顶点数目
     */
    static int vexnum;
    /**
     * 边数目
     */
    static int edagnum;

    private static Vertex[] vertexs;

    public static void createGraph(){
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入顶点的个数");
        vexnum = scanner.nextInt();
        System.out.println("请输入边的条数");
        edagnum = scanner.nextInt();

        vertexs = new Vertex[vexnum];
        System.out.println("请输入各顶点");
        /**
         * 输入各顶点
         */
        for(int i = 0;i <vexnum;i++) {
            vertexs[i] = new Vertex();
            vertexs[i].data = scanner.next();
            vertexs[i].firstage = null;
        }
        System.out.println("请按‘头节点 尾节点 回车’的形式依次输入边的信息");
        for(int i = 0;i < edagnum;i++) {
            String perName = scanner.next();
            String varName = scanner.next();
            Vertex preV = getVertex(perName);
            Vertex folV = getVertex(varName);
            if (preV == null || folV == null){
                System.out.println("输入错误，输入了不存在的顶点！请重新输入");
                i--;
                continue;
            }
            Edge cur = preV.firstage;
            //如果节点的链表不为空，则遍历链表找到最后一个节点进行插入
            if(preV.firstage != null) {
                while (cur.next != null) {
                    cur = cur.next;
                }
                Edge edge = new Edge();
                edge.adhvex = varName;
                //将边加入到节点的链表中去
                edge.next = null;
                cur.next = edge;
            }else {
                Edge edge = new Edge();
                edge.adhvex = varName;
                //将边加入到节点的链表中去
                edge.next = null;
                preV.firstage = edge;
            }
        }

    }
    /**
     * 根据节点名称获取该节点
     * @param verName 节点的名称
     * @return 节点或null
     */
    public static Vertex getVertex(String verName){
        for (int i=0;i<vexnum;i++){
            if (vertexs[i].data.equals(verName))
                return vertexs[i];
        }
        return null;
    }

    /**
     * 输出图的邻接表
     */
    public static void outputGraph(){
        for (int i=0;i<vexnum;i++){
            Vertex vertex = vertexs[i];
            System.out.print(vertex.data);

            Edge current = vertex.firstage;
            while (current != null){
                System.out.print("--"+current.adhvex);
                current = current.next;
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        createGraph();
        outputGraph();
    }
}

请输入顶点的个数
5
请输入边的条数
7
请输入各顶点
v1
v2
v3
v4
v5
请按‘头节点 尾节点 回车’的形式依次输入边的信息
v1 v4
v1 v2
v2 v5
v3 v2
v3 v5
v4 v3
v4 v5
v1--v4--v2
v2--v5
v3--v2--v5
v4--v3--v5
v5

图的存储

图的存储

1，邻接矩阵存储法

2，邻接表存储法

相关推荐