图的存储结构

简介: 一直想写一篇关于图的博客,但是奈何功力不够,迟迟没有下手。查看多方资料后,觉得写一篇笔记供自己参考,各位看官轻喷。感谢这个博客https://blog.csdn.net/qq_35644234/article/details/57083107图是顶点(vetex)和边(edge)的集合。

一直想写一篇关于图的博客,但是奈何功力不够,迟迟没有下手。查看多方资料后,觉得写一篇笔记供自己参考,各位看官轻喷。感谢这个博客https://blog.csdn.net/qq_35644234/article/details/57083107
图是顶点(vetex)和边(edge)的集合。因为图的数据结构有很多种表示方式,容易给我这种渣渣造成很多困扰。就是在没有搞会图的算法之前,先被这些存储方式搞晕了。简单来说,图有各种存储方式是因为每个存储方式有优缺点,我主要讲两种,一种是邻接矩阵,一种是邻接表。
下面待我一一道来。

1. 图的存储结构--邻接矩阵。

这种方式很简单,构建两个数组存储图的信息,一个一维数组存储顶点数据的信息,一个二维数组(也就是矩阵)存储边的信息。
如果图有n个顶点,那么邻接矩阵为n*n的方阵,方阵每个元素的值如下:


img_25da6fa8247f6bf627ed7946bedea844.png
邻接矩阵

举个栗子:


img_c381ea6a1bccafd439f6c08778497540.png
图实例

有向图类似,不在赘述。
这里再说一句,如果我们需要将图表示成一个网的时候(也就是边赋权重)。假设有n个顶点,公式如下:
img_2e498cb58825293c8ead2de7f734f53f.png

接下来是代码实现

import java.util.Scanner;

public class Graph {

    private int[] vex; //顶点数组
    private int[][] adjMatrix; //图的邻接矩阵
    private int vexNum; //顶点个数
    private int edge; //边的条数

    public void createGraph(){
        Scanner s = new Scanner(System.in);
        System.out.println("请输入顶点个数:");
        this.vexNum = s.nextInt();
        System.out.println("请输入边的个数:");
        this.edge = s.nextInt();

        this.vex = new int[vexNum];
        this.adjMatrix = new int[vexNum][vexNum];

        //后面省略
    }
    

2. 图的存储结构--邻接表

邻接表是一种链式存储结构。因为当图的顶点多边少的时候,矩阵将会很庞大,但是里边全都是0,浪费空间。邻接表主要是声明两个结构,一个是用来存储顶点信息的数组(对象数组,存储数据和被指向顶点的地址),一个是表节点(被指向的顶点)。


img_689bf4ce6616c08ed4f3bf4d031d0a49.png
邻接表结构

举个例子:


img_55e2b12164b3b966630012fde8ad3c0a.png
无向图例子

下面结合代码说明邻接表的结构:
import java.util.Scanner;

public class Graph2 {
    
    private int vexNum;//图的顶点数
    private int edge; //图的边数

    //存储被指向的顶点信息
    class ArcNode{
        int adjvex; //某条边指向的那个顶点的位置,一般是数组的下标
        ArcNode nextarc; //指向下一个表结点
    }

    //存储顶点的信息
    class Vnode{
        int data; //顶点信息
        ArcNode firstArc; //指向第一条依附于该顶点边的信息
    }

    public void createGraph(){
        Scanner s = new Scanner(System.in);
        System.out.println("请输入顶点个数:");
        this.vexNum = s.nextInt();
        System.out.println("请输入边的个数:");
        this.edge = s.nextInt();
        
        Vnode[] vnodes = new Vnode[vexNum];

        //后面省略
    }
}

后面还有针对有向图的存储结构---十字链表,针对无向图的存储结构,邻接多重表,只要理解了上面的这些,这些结构不难理解。

《算法第四版》推荐的存储结构,无论是有向图还是无向图,都用邻接表的形式,比较通用。还有,无向图的邻接表一般都是一条边<w,v>,w顶点要接v,v也要接w。
下面是完整的图的代码,代码的实现方式和上图中的结构有一丢丢的不同,是这样的图,不过大体上也差不多:

img_2cb6a66ad14ce8ea0554e03fa401e54e.png

package com.xushu.Undirectedgraph;



/**
 * Java: 邻接表表示的"无向图(List Undirected Graph)"
 */

import java.io.IOException;
import java.util.Scanner;

public class ListUDG {
    // 邻接表中表对应的链表的顶点
    private class ENode {
        int ivex;       // 该边所指向的顶点的位置
        ENode nextEdge; // 指向下一条弧的指针
    }

    // 邻接表中表的顶点
    private class VNode {
        char data;          // 顶点信息
        ENode firstEdge;    // 指向第一条依附该顶点的弧
    };

    private VNode[] mVexs;  // 顶点数组


//    /* 
//     * 创建图(自己输入数据)
//     */
//    public ListUDG() {
//
//        // 输入"顶点数"和"边数"
//        System.out.printf("input vertex number: ");
//        int vlen = readInt();
//        System.out.printf("input edge number: ");
//        int elen = readInt();
//        if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
//            System.out.printf("input error: invalid parameters!\n");
//            return ;
//        }
//        
//        // 初始化"顶点"
//        mVexs = new VNode[vlen];
//        for (int i = 0; i < mVexs.length; i++) {
//            System.out.printf("vertex(%d): ", i);
//            mVexs[i] = new VNode();
//            mVexs[i].data = readChar();
//            mVexs[i].firstEdge = null;
//        }
//
//        // 初始化"边"
//        //mMatrix = new int[vlen][vlen];
//        for (int i = 0; i < elen; i++) {
//            // 读取边的起始顶点和结束顶点
//            System.out.printf("edge(%d):", i);
//            char c1 = readChar();
//            char c2 = readChar();
//            int p1 = getPosition(c1);
//            int p2 = getPosition(c2);
//            // 初始化node1
//            ENode node1 = new ENode();
//            node1.ivex = p2;
//            // 将node1链接到"p1所在链表的末尾"
//            if(mVexs[p1].firstEdge == null)
//              mVexs[p1].firstEdge = node1;
//            else
//                linkLast(mVexs[p1].firstEdge, node1);
//            // 初始化node2
//            ENode node2 = new ENode();
//            node2.ivex = p1;
//            // 将node2链接到"p2所在链表的末尾"
//            if(mVexs[p2].firstEdge == null)
//              mVexs[p2].firstEdge = node2;
//            else
//                linkLast(mVexs[p2].firstEdge, node2);
//        }
//    }

    /*
     * 创建图(用已提供的矩阵)
     *
     * 参数说明:
     *     vexs  -- 顶点数组
     *     edges -- 边数组
     */
    public ListUDG(char[] vexs, char[][] edges) {
        
        // 初始化"顶点数"和"边数"
        int vlen = vexs.length;
        int elen = edges.length;

        // 初始化"顶点"
        mVexs = new VNode[vlen];
        for (int i = 0; i < mVexs.length; i++) {
            mVexs[i] = new VNode();
            mVexs[i].data = vexs[i];
            mVexs[i].firstEdge = null;
        }

        // 初始化"边"
        for (int i = 0; i < elen; i++) {
            // 读取边的起始顶点和结束顶点
            char c1 = edges[i][0];
            char c2 = edges[i][1];
            // 读取边的起始顶点和结束顶点
            int p1 = getPosition(edges[i][0]);
            int p2 = getPosition(edges[i][1]);
            
            
            //初始化两次,保证w后有v,v后有w
            
            // 初始化node1
            ENode node1 = new ENode();
            node1.ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == null)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
            // 初始化node2
            ENode node2 = new ENode();
            node2.ivex = p1;
            // 将node2链接到"p2所在链表的末尾"
            if(mVexs[p2].firstEdge == null)
              mVexs[p2].firstEdge = node2;
            else
                linkLast(mVexs[p2].firstEdge, node2);

        }
    }

    /*
     * 将node节点链接到list的最后
     */
    private void linkLast(ENode list, ENode node) {
        ENode p = list;

        while(p.nextEdge!=null)
            p = p.nextEdge;
        p.nextEdge = node;
    }

    /*
     * 返回ch位置
     */
    private int getPosition(char ch) {
        for(int i=0; i<mVexs.length; i++)
            if(mVexs[i].data==ch)
                return i;
        return -1;
    }

    /*
     * 读取一个输入字符
     */
    private char readChar() {
        char ch='0';

        do {
            try {
                ch = (char)System.in.read();
            } catch (IOException e) {
                e.printStackTrace();
            }
        } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));

        return ch;
    }

    /*
     * 读取一个输入字符
     */
    private int readInt() {
        Scanner scanner = new Scanner(System.in);
        return scanner.nextInt();
    }

    /*
     * 打印矩阵队列图
     */
    public void print() {
        System.out.printf("List Graph:\n");
        for (int i = 0; i < mVexs.length; i++) {
            System.out.printf("%d(%c): ", i, mVexs[i].data);
            ENode node = mVexs[i].firstEdge;
            while (node != null) {
                System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
                node = node.nextEdge;
            }
            System.out.printf("\n");
        }
    }

    public static void main(String[] args) {
        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'}};
        ListUDG pG;

        // 自定义"图"(输入矩阵队列)
        //pG = new ListUDG();
        // 采用已有的"图"
        pG = new ListUDG(vexs, edges);

        pG.print();   // 打印图
    }
}
目录
相关文章
|
5月前
|
存储 算法 C++
【C/C++ 数据结构 】无向图和有向图的差异
【C/C++ 数据结构 】无向图和有向图的差异
148 0
|
26天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
4月前
|
存储
技术心得记录:图的概念和存储(邻接矩阵,邻接表)
技术心得记录:图的概念和存储(邻接矩阵,邻接表)
16 0
|
5月前
|
存储 容器
图的存储结构之打印邻接表
图的存储结构之打印邻接表
|
存储 机器学习/深度学习 人工智能
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
|
5月前
|
存储 算法 C语言
【数据结构】— —邻接矩阵和邻接表存储图结构
【数据结构】— —邻接矩阵和邻接表存储图结构
|
存储 算法
【数据结构和算法】图的各类概念与图的存储结构(还有十字链表与邻接多重表的介绍)
【数据结构和算法】图的各类概念与图的存储结构(还有十字链表与邻接多重表的介绍)
230 0
【数据结构和算法】图的各类概念与图的存储结构(还有十字链表与邻接多重表的介绍)
|
12月前
|
存储
图的基本术语,邻接矩阵、邻接表表示方法
图的基本术语,邻接矩阵、邻接表表示方法
|
存储 算法
描述图的两种数据结构 - 邻接表和邻接矩阵
描述图的两种数据结构 - 邻接表和邻接矩阵
|
存储 C++
数据结构之 图(一) 图的存储结构
数据结构之 图(一) 图的存储结构