图论基本知识

图的基本概念

图示一个复杂的结构,节点之间的关系可以是任意的,图中的任意两个元素之间都可能相关。

图分为有向图和无向图,无向图为两个节点之间互相可以到达,有向图只能根据箭头所指的方向到达另一个节点。上图中(a)为有向图,(b)为无向图

有时边或者弧具有与它相关的数,这种数字叫做权,这种带权的图常常称为网。

回路:第一个顶点和最后一个顶点相同的路径称之为回路或者环,路径中顶点不重复出现为简单路径,回路中无重复顶点为简单回路。

连通:如果两个顶点之间有路径,则称这两个顶点是连通的,如果图中的任意一点都可以到其他的所有顶点,则称这个图为连通图。

连通分量:无向图中的极大连通子图(N个顶点构成一个连通图),连通图必然有连通分量,有连通分量不一定为连通图,两者无必然联系。

有向图的连通图成为强连通图和强连通子图,概念和无向图的相同

图的存储结构

邻接矩阵

用矩阵来存储图的结构

0表示两个顶点之间无联系,1表示有联系(无向图中由于没有方向所以V3可以到达V2 V2也可以到达V3)

构建邻接矩阵

import java.util.Scanner;
public class UDN {
    String vex[] = new String[100];  // 邻接矩阵
    int a[][];   // 顶点存储数组

    // 创建邻接矩阵
    public void createChart() {
        int i = 0;
        int t = 0;
        Scanner in = new Scanner(System.in);
        System.out.println("请输入顶点");
        String str = in.nextLine();
        while (str.length() != 0) {
            vex[t] = str;
            t++;
            str = in.nextLine();
        }
        System.out.println(t);
        a = new int[t][t]; // 邻接矩阵
        for (i = 0; i < t; i++) {
            System.out.println("请输入一条边的依附顶点");
            String d1 = in.nextLine();
            String d2 = in.nextLine();
            int d1Index = findLine(d1);
            int d2Index = findLine(d2);
            a[d2Index][d1Index] = 1;
            a[d1Index][d2Index] = 1;
        }
    }

    // 输出
    public void print() {

        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

    // 查找输入顶点对应的下标
    public int findLine(String d1) {
        int i = 0;

        for (int t = 0; t < vex.length; t++) {
            if (vex[t].equals(d1)) {
                i = t;
                break;
            }
        }
        return i;
    }

    public static void main(String[] args) {
        UDN i = new UDN();
        i.createChart();
        i.print();
    }

}

邻接表存储

邻接表是一种链式的存储结构,存储结构示意图(a):

数组中存储的为节点,每个节点后面为此节点邻接节点的下标

头节点
public class VNode {
    private String data; // 该弧的顶点信息
    private ArcNode firstArc; // 第一条弧

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public ArcNode getFirstArc() {
        return firstArc;
    }

    public void setFirstArc(ArcNode firstArc) {
        this.firstArc = firstArc;
    }

}

表节点

public class VNode {
    private String data; // 该弧的顶点信息
    private ArcNode firstArc; // 第一条弧

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public ArcNode getFirstArc() {
        return firstArc;
    }

    public void setFirstArc(ArcNode firstArc) {
        this.firstArc = firstArc;
    }

}

图的信息

public class AlGraph {
    private VNode nodeList[];
    private int vexnum, arcnum; // 图的定点数和弧数
    private int kind; // 弧的种类

    public VNode[] getNodeList() {
        return nodeList;
    }

    public void setNodeList(VNode[] nodeList) {
        this.nodeList = nodeList;
    }

    public int getVexnum() {
        return vexnum;
    }

    public void setVexnum(int vexnum) {
        this.vexnum = vexnum;
    }

    public int getArcnum() {
        return arcnum;
    }

    public void setArcnum(int arcnum) {
        this.arcnum = arcnum;
    }

    public int getKind() {
        return kind;
    }

    public void setKind(int kind) {
        this.kind = kind;
    }

}

构建

public class AdjancecyListDemo {
    AlGraph alGraph = new AlGraph();

    public void createAdjancency() {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入顶点数");

        int n = in.nextInt(); // 表内容初始化
        alGraph.setNodeList(new VNode[n]);
        alGraph.setVexnum(n);
        System.out.println("请输入弧数");
        alGraph.setArcnum(in.nextInt());

        VNode[] list = alGraph.getNodeList(); // 头结点初始化
        System.out.println(list.length);
        System.out.println("input Node:");
        for (int i = 0; i < list.length; i++) {
            VNode node = new VNode();
            node.setData(in.next());
            list[i] = node;
        }

        for (int i = 0; i < alGraph.getArcnum(); i++) {
            System.out.println("请输入弧依附的两个顶点"); // 构建邻接表
            String begin = in.next();
            String end = in.next();
            int ii = findIndex(begin);
            int jj = findIndex(end);
            if (ii == -1 || jj == -1) {
                System.out.println("输入的节点不存在");
                return;
            }
            ArcNode arcNode = new ArcNode();
            addArcNode(ii, jj, end);
            addArcNode(jj, ii, begin);
        }
    }

    public void prinfAlGralph() {  // 输出

        VNode[] list = alGraph.getNodeList();
        for (int i = 0; i < list.length; i++) {
            System.out.print(i + "-" + list[i].getData() + " : ");
            ArcNode arc = list[i].getFirstArc();
            while (arc != null) {
                System.out.print(arc.getAdjVex() + " | ");
                arc = arc.getNextArc();
            }
            System.out.println();
        }
    }

    public void addArcNode(int index, int end, String info) { // 添加表结点
        VNode[] list = alGraph.getNodeList();
        ArcNode tempArc = list[index].getFirstArc();
        ArcNode arcNode = new ArcNode();
        if (tempArc == null) {
            arcNode.setAdjVex(end);
            arcNode.setInfo(info);
            list[index].setFirstArc(arcNode);
        } else {
            while (tempArc.getNextArc() != null) {
                tempArc = tempArc.getNextArc();
            }
            arcNode.setAdjVex(end);
            arcNode.setInfo(info);
            tempArc.setNextArc(arcNode);
        }
    }

    public int findIndex(String node) {     // 查找给定节点的下标
        VNode[] list = alGraph.getNodeList();
        for (int i = 0; i < list.length; i++) {
            if (list[i].getData().equals(node)) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        AdjancecyListDemo demo = new AdjancecyListDemo();
        demo.createAdjancency();
        demo.prinfAlGralph();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Problem: Vertext Cover Problem

给定一个N个点M条边的无向图G(点的编号从1至N),问是否存在一个不超过K个点的集合S,使得G中的每条边都至少有一个点在集合S中。

692
来自专栏PingCAP的专栏

TiDB 源码阅读系列文章(七)基于规则的优化

本篇将主要关注逻辑优化。先介绍 TiDB 中的逻辑算子,然后介绍 TiDB 的逻辑优化规则,包括列裁剪、最大最小消除、投影消除、谓词下推、TopN 下推等等。

5.5K15
来自专栏数据结构与算法

Link-Cut-Tree(LCT)详解

1700
来自专栏大闲人柴毛毛

贪心算法(四)——最小代价生成树

问题描述 n个村庄间架设通信线路,每个村庄间的距离不同,如何架设最节省开销? 这个问题中,村庄可以抽象成节点,村庄之间的距离抽象成带权值的边,要求最节约...

4246
来自专栏数据结构与算法

Link-Cut-Tree(LCT)详解

LCT是一种解决动态树问题的方法,由tarjan(为什么又是他)在1982年提出,最原始的论文在这里,在论文中,tarjan除了介绍了均摊复杂度为$O(log^...

51913
来自专栏C/C++基础

C#用GDI画任意形状的form

Point[] points = list.ToArray();//将点集合赋给点数组

542
来自专栏素质云笔记

python+gensim︱jieba分词、词袋doc2bow、TFIDF文本挖掘

分词这块之前一直用R在做,R中由两个jiebaR+Rwordseg来进行分词,来看看python里面的jieba. 之前相关的文章: R语言︱文本挖掘之...

7469
来自专栏算法channel

Spark|有向无环图(DAG)检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

3718
来自专栏数据结构与算法

P1726 上白泽慧音(0分)

题目描述 在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够...

2488
来自专栏C/C++基础

图的周游

图的周游:是一种按某种方式系统地访问图中的所有节点的过程,它使每个节点都被访问且只访问一次。图的周游也称图的遍历。

772

扫码关注云+社区