IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 图的概念和展示 -> 正文阅读

[数据结构与算法]图的概念和展示

为什么要有图:
线性表局限于一个前驱一个直接的后继关系
树也只能有一个前驱也就是父节点
当我们需要多对多的关系时,我们就用到了图

图是一种数据结构,节点可以具有零个或者多个相邻的元素,两个结点之间的连接称之为边,结点也可以成为顶点。

举例 :北京市地铁图。。。

在这里插入图片描述

概念

1,顶点
2,边
3,路径
4,无向图

请添加图片描述
无向图:顶点之间的连接没有方向,比如 A - B , 也可以是 B - A
路径 :比如从D -> C 的路径有
1):D -> B -> C
2):D -> A -> B -> C

5,有向图

请添加图片描述

有向图:顶点之间的连接方向,
比如 A -> B , 只能是A -> B , 不能是B -> A .

6,带权图

请添加图片描述

这种边带也全值的图也叫网

图的表示方式

1,二维数组
2,链表表示(邻接表)

邻接矩阵是表示图形中的顶点之间的矩阵,对于N个顶点的图而言,矩阵的row和col 表示的是 1…n 个点

请添加图片描述

邻接表,邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失,邻接表的实现,只关心存在的边,不关心不存在的边,因此,没有空间浪费,邻接表由数组+链表组成

在这里插入图片描述

图的快速入门案例

1)要求代码实现如下图结构

请添加图片描述
在这里插入图片描述2)思路分析:

  • 顶点存储用String ,使用ArrayList 保存顶点
  • 保存矩阵用 int[][] edges
  • 代码实现

代码

package com.huan.graph;

import java.util.ArrayList;
import java.util.Arrays;

public class Graph {

    private ArrayList<String> vertexList;//存储顶点集合
    private int[][] edges; // 存储图对应的邻接矩阵
    private int numOfEdges; //表示边的数目

    public static void main(String[] args) {
        //测试图是否创建ok
        int n = 5; //结点的个数
        String Vertexs[] = {"A","B","C","D","E"};
        //创建图对象
        Graph graph = new Graph( 5 );
        //循环的添加顶点s
        for (String vertex : Vertexs){
            graph.insertVertex( vertex );
        }

        //添加边
        // A - B , A - C , B-C , B-D , B-E
        graph.insertEdge( 0,1,1 );  //A - B
        graph.insertEdge( 0,2,1 );  //A - C
        graph.insertEdge( 1,2,1 );  //B - C
        graph.insertEdge( 1,3,1 );  //B - D
        graph.insertEdge( 1,4,1 );  //B - E
        graph.insertEdge( 1,0,1 );  //B - A

        //显示邻结矩阵
        graph.showGraph();

    }

    //构造器
    public Graph(int n) {
        //初始化矩阵
        edges = new int[n][n];
        //初始化顶点集合
        vertexList = new ArrayList<String>(n);
        //初始化边的数目
        numOfEdges = 0;
    }

    //图中常用的方法,
    //返回结点的个数
    public int getNumOfVertex(){
        return vertexList.size();
    }

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

    //返回结点i(下标)对应的数据 0 -> "A" , 1 -> "B" , 2 -> "C"
    public String getValueByIndex(int i){
        return vertexList.get( i );
    }

    //返回v1 v2 的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    //显示图对应的矩阵
    public void showGraph(){
        for (int[] link : edges){
            System.err.println( Arrays.toString( link ) );
        }
    }

    //插入结点
    public void insertVertex(String vertex){
        vertexList.add( vertex );
    }

    //添加边
    /**
     * @param v1 表示点的下标即使第几个顶点 “A” - "B" , "A" -> 0  "B" -> 1
     * @param v2 表示第二个顶点对应的下标
     * @param weight 全值 , 表示矩阵里面的值,你想用什么值来表示 AB之间的关系 , 证明他们是关联的。
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-22 14:55:44  更:2021-09-22 14:57:01 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 2:39:28-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码