文档章节

数据结构——图(Graph)

 丰田破产标志
发布于 09/08 23:57
字数 1724
阅读 11
收藏 1

图的概念
图(Graph)是一些顶点的集合,顶点之间通过边连接。
边可以有权重(weight),即每条边可以被赋值,正负皆可。
边分为有向边(Directed Edge)、无向边(Undirected Edge)。
顶点的度指连接该顶点的边的数目。

图的表示方法

对于如上的图,有两种主要的表示方法:

  • 邻接表(Adjaccency List)
    邻接表的优点是节省空间,只存储实际存在的边。
    缺点是关注顶点的度时,可能要遍历一个链表。
    实现图解如下图:

    Java实现代码:
/**
 * 有向带权图的邻接表实现
 */
public class LinkGraph {

    //顶点
    private class Vertex {
        char data;          //顶点的名称(值)
        Node firstEdge;     //顶点的第一个邻接点
    }

    //某个顶点的邻接点的相关信息
    private class Node {
        int index;       //代表此Node在vertex数组中的序号
        int weight;      //顶点与此邻接点的边的权值
        Node nextNode;   //点的下一个邻接点
    }

    //边
    static class Edge {
        char start;        //起点的顶点名称(值)
        char end;          //重点的顶点名称(值)
        int weight;        //边的权值

        public Edge(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    private Vertex[] vertexNameList;    //所有顶点名的数组

    public LinkGraph(char[] vert, Edge[] edge){
        //读入顶点,并初始化
        vertexNameList = new Vertex[vert.length];
        parent = new int[vert.length];

        for (int i = 0; i < vert.length; i++) {
            vertexNameList[i] = new Vertex();
            vertexNameList[i].data = vert[i];   //顶点名称
            vertexNameList[i].firstEdge = null; //还没有邻接点,当然没边
        }

        //初始化边
        for (int i = 0; i < edge.length; i++) {
            char start = edge[i].start;
            char end = edge[i].end;

            //获取顶点对应的序号
            int startRank = getPosition(start);
            int endRank = getPosition(end);

            //1.endRank是startRank的邻接点,把endRank连接在以startRank为头的链表中
            Node endRankNode = new Node();
            endRankNode.index = endRank;
            endRankNode.weight = edge[i].weight;
            linkedLast(startRank,endRankNode);
        }
    }
	
    //尾插法,将顶点连接到链表的尾巴
    private void linkedLast(int index, Node node) {
        if(vertexNameList[index].firstEdge == null)
            vertexNameList[index].firstEdge = node;
        else{
            Node tmp = vertexNameList[index].firstEdge;
            while(tmp.nextNode != null){
                tmp = tmp.nextNode;
            }
            tmp.nextNode = node;
        }
    }

    //获取某个顶点在数组中序号
    private int getPosition(char v) {
        for (int i = 0; i < vertexNameList.length; i++) {
            if(vertexNameList[i].data == v) return i;
        }
        //不存在这样的顶点则返回-1
        return -1;
    }

    public static void main(String[] args) {
        char[] vexs = {'A', 'B', 'C', 'D', 'E'};   //顶点
        Edge[] edges = {                           //边
                // 起点      终点    权
                new Edge('A', 'B', 5.6),
                new Edge('A', 'C', 1.0),
                new Edge('A', 'D', 4.2),
                new Edge('B', 'C', 2.7),
                new Edge('C', 'A',  1.0),
                new Edge('C', 'B',  2.7),
                new Edge('E', 'B',  -3.0)
        };
        LinkGraph graph = new LinkGraph(vexs,edges);
    }
  • 邻接矩阵(Adjacency Matrix)
    邻接矩阵的优点是可快速添加和删除边,可快速判断两个点之间是否存在边。
    缺点是如顶点之间的边比较少,会浪费空间,因为是一个n*n的矩阵。
    实现图解如下图:

    Java实现代码:
/**
 * 邻接矩阵的实现
 */
public class MatrixGraph {

    private char[] vertex;     //顶点名的集合

    private int[][] edges;     //邻接矩阵,存储边

    private int numOfEdges;     //边的个数

    public MatrixGraph(int n){
        edges = new int[n][n];
        vertex = new char[n];
    }

    //顶点的个数
    public int getNumOfVertexs(){
        return vertex.length;
    }

    //边的数目
    public int getNumOfEdges(){
        return numOfEdges;
    }

    //获取序号v1顶点到序号v2顶点的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    //插入一条边
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        numOfEdges++;
    }

    //获取某顶点下标v的第一个邻接点在vertex数组的下标
    public int getFirstNeighbor(int v){
        for (int i = 0; i < vertex.length; i++) {
            if(edges[v][i] != 0)
                return i;
        }
        return -1;
    }

    //根据顶点下标v1的前一个邻接点下标v2,获取v1的下一个邻接点
    public int getNextNeighbor(int v1,int v2){
        for (int i = v2+1; i < vertex.length; i++) {
            if(edges[v1][i] != 0)
                return i;
        }
        return -1;
    }
}

图的遍历算法(基于邻接表)

  1. 深度优先遍历(DFS: Depth First Search)
    深度优先算法的过程,简单来说是从起点开始,找到一条最深的路径,到头之后,返回上一个节点,继续找一条最深的路径(每个节点只能访问一次)。
    Java实现代码:
    //深度优先搜索(DFS)遍历图,从第一个顶点开始遍历图
    public void DFS(){
        boolean[] visited = new boolean[vertexNameList.length];  //顶点是否已被遍历,默认为false
        int[] path = new int[vertexNameList.length];             //遍历时,顶点出现的顺序,按序记录其下标
        int index = 0;                                           //path[]的索引

        /**
         * MyStack:表示数据结构——栈;先进后出
         * 栈的基本操作: 
         * 1) push(Object o):元素入栈 
         * 2) Object pop():返回栈顶元素,并把该元素从栈中删除。
         * 3) Object peek():返回栈顶元素,但不把该元素删除。
         */
        MyStack stack = new MyStack(vertexNameList.length);

        for (int i = 0; i < visited.length; i++)
        {
            //利用栈的先进后出特性,先找到一条最深的路径
            stack.push(i);

            if(!visited[i])
            {
                visited[i] = true;                                     //下标i的顶点被遍历
                path[index++] = i;                                     //第一个被遍历的顶点,其下标是i

                while(!stack.isEmpty())
                {
                    int v = getUnVisitedVertex(stack.peek(),visited);
                    //如果不存在没有访问的邻接点,就出栈,原路返回
                    if(v == -1) stack.pop();
                    else
                    {
                        path[index++] = v;   //访问邻接点顺序
                        visited[v] = true;   //邻接点v已访问
                        stack.push(v);       //入栈
                    }

                }
            }
            else
            {
                stack.pop();
            }
        }

        //打印DFS路径
        System.out.println("DFS路径:");
        for (int i = 0; i < path.length; i++) {
            System.out.print(vertexNameList[path[i]].data + " ");
        }

    }

    //返回某个顶点还没有被访问的邻接点的序号
    private int getUnVisitedVertex(Integer v, boolean[] visited) {
        Node tmp = vertexNameList[v].firstEdge;

        //如果存在邻接点,且邻接点还没有被遍历,返回此邻接点下标;
        while(tmp != null){
            if(!visited[tmp.index]) return tmp.index;
            tmp = tmp.nextNode;
        }
        //不存在没有被访问的邻接点
        return -1;
    }

stack进出栈顺序:

  1. 广度优选遍历(BFS: Breadth First Search)
    广度优先算法,是从起点开始,找到这个点所有的邻接点,到头之后,从它的第一个邻接点开始,继续找一条最广的路径(每个节点只能访问一次)。
    Java实现代码:
    //广度优先搜索,从第一个顶点开始遍历
    public void BFS(){
        boolean[] visited = new boolean[vertexNameList.length];  //顶点是否已被遍历,默认为false
        int[] path = new int[vertexNameList.length];             //遍历时,顶点出现的顺序,按序记录其下标
        int index = 0;                                           //path[]的索引

        /**
         * MyQueue:表示数据结构——队列;先进先出
         * 队列的基本操作: 
         * 1) enqueue(T t):元素入队 
         * 2)  T dequeue():元素出队,并把该元素从队列中删除。
         * 3)     T peek():返回队列头元素,但不把该元素删除。
         */
        MyQueue<Integer> queue = new MyQueue<Integer>(vertexNameList.length);

        for (int i = 0; i < visited.length; i++)
        {
            //利用队列的先进先出特性,先找到一条最广的路径
            queue.enqueue(i);

            if(!visited[i])
            {
                visited[i] = true;                                     //下标i的顶点被遍历
                path[index++] = i;                                     //第一个被遍历的顶点,其下标是i

                while(!queue.isEmpty())
                {
                    int v = getUnVisitedVertex(queue.peek(),visited);
                    //如果不存在没有访问的邻接点,就出队
                    if(v == -1) queue.dequeue();
                    else
                    {
                        path[index++] = v;
                        visited[v] = true;
                        queue.enqueue(v);
                    }
                }
            }
            else
            {
                queue.dequeue();
            }

        }


        //打印BFS路径
        System.out.println("BFS路径:");
        for (int i = 0; i < path.length; i++) {
            System.out.print(vertexNameList[path[i]].data + " ");
        }
    }

queue进出队列顺序:

© 著作权归作者所有

粉丝 0
博文 9
码字总数 9957
作品 0
杭州
私信 提问
GNN 系列(一):Graph 基础知识介绍 - 知乎

写在前面 图卷积神经网络(Graph Convolutional Network)作为最近几年兴起的一种基于图结构的广义神经网络结构,因为其独特的计算能力,而受到广泛学者的关注与研究。传统深度学习模型 LSTM 和...

机器学习理论与数据竞赛实战
前天
0
0
Spring Data Graph 1.1.0 发布,支持 Neo4j

Spring Data Graph 1.1.0 正式版发布了,该版本最大的改进就是支持 Neo4j。 Spring Data 项目的目的是为了简化构建基于 Spring 框架应用的数据访问计数,包括非关系数据库、Map-Reduce 框架、...

红薯
2011/08/25
632
0
MIT 开发廉价闪存设备,处理图数据性能堪比服务器

在数据科学的说法中,图(graph)是指用于映射大量复杂的数据关系的节点(nodes)和连接线(connecting lines)的结构。分析graph在许多应用中非常有用,例如网页排名、分析社交网络以获取政...

技术小能手
2018/06/04
0
0
Tensorflow核心代码解析之计算图篇其三:图的构建

介绍 如果你翻过Tensorflow的核心代码,一定会奇怪表示图的class如此之多像GraphDef/Graph等。通常GraphDef表示一组与Graph相关的属性Jason对(本质上是Graph的Protocol buffer表示)。而真正...

manofmountain
2018/06/21
0
0
Spring Data Graph 1.0 发布,支持 Neo4j

Spring Data Graph 1.0 正式版发布了,这是 Spring Data 的一个子项目用于实现基于POJO的编程模型。该版本最大的亮点就是完全支持 Neo4j (Neo是一个网络——面向网络的数据库——也就是说,它...

红薯
2011/04/20
706
0

没有更多内容

加载失败,请刷新页面

加载更多

Java 文件类操作API与IO编程基础知识

阅读目录: https://www.w3cschool.cn/java/java-io-file.html Java 文件 Java 文件 Java 文件操作 Java 输入流 Java 输入流 Java 文件输入流 Java 缓冲输入流 Java 推回输入流 Java 数据输入...

boonya
18分钟前
2
0
SDKMAN推荐一个好

是在大多数基于Unix的系统上管理多个软件开发工具包的并行版本的工具。它提供了一个方便的命令行界面(CLI)和API来安装,切换,删除和列出sdk相关信息。以下是一些特性: By Developers, fo...

hotsmile
43分钟前
8
0
什么是 HDFS

是什么? HDFS 是基于 Java 的分布式文件系统,允许您在 Hadoop 集群中的多个节点上存储大量数据。 起源: 单机容量往往无法存储大量数据,需要跨机器存储。统一管理分布在集群上的文件系统称...

Garphy
46分钟前
5
0
一起来学Java8(四)——复合Lambda

在一起来学Java8(二)——Lambda表达式中我们学习了Lambda表达式的基本用法,现在来了解下复合Lambda。 Lambda表达式的的书写离不开函数式接口,复合Lambda的意思是在使用Lambda表达式实现函...

猿敲月下码
今天
10
0
debian10使用putty配置交换机console口

前言:Linux的推广普及,需要配合解决实际应用方能有成效! 最近强迫自己用linux进行实际工作,过程很痛苦,还好通过网络一一解决,感谢各位无私网友博客的帮助! 系统:debian10 桌面:xfc...

W_Lu
今天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部