图面试专题

一、概念

和二叉树的区别:图可能有环

常见概念

  1. 顶点(Vertex): 图中的节点或点。
  2. 边(Edge): 顶点之间的连接线,描述节点之间的关系。
  3. 有向图(Directed Graph): 边具有方向性的图,边有箭头表示方向。
  4. 无向图(Undirected Graph): 边没有方向性的图。
  5. 路径(Path): 顶点序列,通过边连接的顶点序列。
  6. 回路(Cycle): 闭合的路径,起点和终点相同的路径。
  7. 连通图(Connected Graph): 图中任意两个顶点之间都存在路径的图。
  8. 强连通图(Strongly Connected Graph): 有向图中任意两个顶点之间都存在双向路径的图。
  9. 连通分量(Connected Component): 无向图中的极大连通子图。
  10. 树(Tree): 无环连通图,任意两个节点都有唯一路径。
  11. 森林(Forest): 多个不相交树的集合。
  12. 度(Degree): 顶点的度是指与该顶点相关联的边的数量。
  13. 权重(Weight): 边或者顶点上的数值,表示边的代价或者顶点的属性。

邻接矩阵

ABCD
A0正无穷58
B正无穷09正无穷
C5904
D8正无穷40

邻接表法

Nodeweight
AC5
AD8
CB9
CD4
BC9
DA8
DC4

二、算法题

1、套路模板


/*** @author jeb_lin* 22:27 2023/11/29*/
public class Node {public int value; // 可以改成 Stringpublic int in;// 入度public int out;// 出度public ArrayList<Node> nexts; // 多个后继节点public ArrayList<Edge> edges; // 多条边,该节点指出去的public Node(int value){this.value = value;this.in = 0;this.out = 0;this.nexts = new ArrayList<>();this.edges = new ArrayList<>();}public int getValue() {return value;}public void setValue(int value) {this.value = value;}public int getIn() {return in;}public void setIn(int in) {this.in = in;}public int getOut() {return out;}public void setOut(int out) {this.out = out;}public ArrayList<Node> getNexts() {return nexts;}public void setNexts(ArrayList<Node> nexts) {this.nexts = nexts;}public ArrayList<Edge> getEdges() {return edges;}public void setEdges(ArrayList<Edge> edges) {this.edges = edges;}
}

/*** @author jeb_lin* 22:27 2023/11/29*/
public class Edge {public Node from;public Node to;public int weight;public Edge(Node from, Node to, int weight) {this.weight = weight;this.from = from;this.to = to;}// 复写下面这俩,是为了放入Set的时候能正确去重@Overridepublic boolean equals(Object obj) {if (this == obj) {return true;}if (obj == null || !(obj instanceof Edge)) {return false;}Edge edge = (Edge) obj;return this.weight == edge.weight && Objects.equals(edge.from, this.from) && Objects.equals(edge.to, this.to);}@Overridepublic int hashCode() {return this.weight * this.from.hashCode() * this.to.hashCode();}public Node getFrom() {return from;}public void setFrom(Node from) {this.from = from;}public Node getTo() {return to;}public void setTo(Node to) {this.to = to;}public int getWeight() {return weight;}public void setWeight(int weight) {this.weight = weight;}
}

/*** @author jeb_lin* 22:26 2023/11/29*/
public class Graph {public HashMap<Integer,Node> nodes; // 该图上面的所有Node,nodeVal -> Nodepublic HashSet<Edge> edges; // 该图上面的所有边public Graph(){this.nodes = new HashMap<>();this.edges = new HashSet<>();}public HashMap<Integer, Node> getNodes() {return nodes;}public void setNodes(HashMap<Integer, Node> nodes) {this.nodes = nodes;}public HashSet<Edge> getEdges() {return edges;}public void setEdges(HashSet<Edge> edges) {this.edges = edges;}
}

2、二维数组转化成图

012备注
0015Node0->Node1 ,weight=5
1123Node1->Node2 ,weight=3
2027Node0->Node2 ,weight=7

/*** 把二维数组转换成图* [*      [0,1,5], // 表示 node0 -> node1 ,weight = 5*      [1,2,3],*      [0,2,7]* ]** @param matrix* @return*/public static Graph createGraph(int[][] matrix) {Graph graph = new Graph();HashMap<Integer, Node> nodes = new HashMap<>(); // 该图上面的所有Node,nodeVal -> NodeHashSet<Edge> edges = new HashSet<>(); // 该图上面的所有边graph.setEdges(edges);graph.setNodes(nodes);for (int i = 0; i < matrix.length; i++) {int[] row = matrix[i];if (!nodes.containsKey(row[0])) {nodes.put(row[0], new Node(row[0]));}if (!nodes.containsKey(row[1])) {nodes.put(row[1], new Node(row[1]));}Node from = nodes.get(row[0]);Node to = nodes.get(row[1]);from.setOut(from.getOut() + 1);to.setIn(to.getIn() + 1);from.getNexts().add(to);Edge edgeTemp = new Edge(from, to, row[2]);from.getEdges().add(edgeTemp);if(!edges.contains(edgeTemp)){edges.add(edgeTemp);}}return graph;}public static void main(String[] args) {int[][] arr = {{0, 1, 5}, {1, 2, 3}, {0, 2, 7}};Graph graph = createGraph(arr);System.out.println("ok");}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/205374.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于BP神经网络的手写体数字识别matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 filename dir(images\*.bmp); %图像文件格式 load BP.matfilename dir(test\*.bmp); …

[BJDCTF2020]The mystery of ip1

提示 ssti模板注入head头x-forwarded-for 每一次做题的最开始流程都大致因该是 信息收集找可以操控的地方 查看hint页面的源代码又发现它提示说 ####你知道为什么会知道你的ip吗 查看flag页面 从刚才给我的提示以及他这里显示的我的ip&#xff0c;大概找到了我可操作的可控点 …

【Java SE】带你在String类世界中遨游!!!

&#x1f339;&#x1f339;&#x1f339;我的主页&#x1f339;&#x1f339;&#x1f339; &#x1f339;&#x1f339;&#x1f339;【Java SE 专栏】&#x1f339;&#x1f339;&#x1f339; &#x1f339;&#x1f339;&#x1f339;上一篇文章&#xff1a;带你走近Java的…

ubuntu22.04系统下载程序和依赖,并拷贝到指定路径下

脚本1 apt install aptitude apt-get -d install xxx #xxx是待下载的安装包 mv /var/cache/apt/archives/* /home/tuners/1apt install aptitude apt-get -d install xxx mv /var/cache/apt/archives/*.deb /home/tuners/1 xxx 为程序包名称 /home/tuners/1为保存程序包的…

PM2 在线和离线部署uvicorn和fastapi项目过程

PM2介绍 PM2 is a daemon process manager that will help you manage and keep your application online 24/7 PM2是一个后台进程管理工具&#xff0c;能帮助管理应用和维持应用7*24小时运行。 PM2在线安装 npm install pm2 -gPM2离线安装(适用于内网) 参见 如何离线安装pm2…

git-4

1.在GitHub上创建个人仓库 现在仓库中有LICENSE文件&#xff0c;但本地没有这个文件&#xff0c;该怎么办呢&#xff1f;往下看 2.把本地仓库同步到GitHub 3.不同人修改了不同文件如何处理&#xff1f; 两个人在同一个分支上&#xff0c;两个人修改了不同文件 其中一人&…

案例研究|北京交通大学基于DataEase开展多场景校园数据分析与展示

北京交通大学是教育部直属&#xff0c;教育部、交通运输部、北京市人民政府和中国国家铁路集团有限公司共建的全国重点大学&#xff0c;是国家“211工程”“985工程优势学科创新平台”“双一流”建设高校。 多年来&#xff0c;北京交通大学积极发挥信息技术赋能学校人才培养、…

基于springboot实现乒乓球预约管理系统项目【项目源码】

基于springboot实现乒乓球预约管理系统演示 系统的开发环境 浏览器&#xff1a;IE 8.1&#xff08;推荐6.0以上&#xff09; 开发使用语言&#xff1a;JAVA JDK版本&#xff1a;JDK_8 数据库管理系统软件&#xff1a;Mysql 运行平台&#xff1a;Windows 7 运行环境&#…

【hacker送书第6期】深入理解Java核心技术

第6期图书推荐 内容简介作者简介精彩书评参与方式 内容简介 《深入理解Java核心技术&#xff1a;写给Java工程师的干货笔记&#xff08;基础篇&#xff09;》是《Java工程师成神之路》系列的第一本&#xff0c;主要聚焦于Java开发者必备的Java核心基础知识。全书共23章&#xf…

关于鸿蒙网络请求的问题

https://developer.huawei.com/consumer/cn/forum/topic/0204136145853212268?fid0102683795438680754 鸿蒙OS 代码 import http from ohos.net.http;export const httpUtils (url: string, data: any) > {return new Promise((resolve, reject) > {let httpRequest …

鸿蒙开发已成新趋势

随着华为鸿蒙操作系统的快速崭露头角&#xff0c;鸿蒙开发已然成为当前技术领域的热门新趋势。本文将深入探讨鸿蒙开发的重要性和独特优势&#xff0c;并详细介绍一些关键的鸿蒙开发技术和工具&#xff0c;以及它们对开发者个人和整个行业带来的深远影响。 首先&#xff0c;鸿蒙…

【Apifox】测试工具自动编写接口文档

在开发过程中&#xff0c;我们总是避免不了进行接口的测试&#xff0c; 而相比手动敲测试代码&#xff0c;使用测试工具进行测试更为便捷&#xff0c;高效 今天发现了一个非常好用的接口测试工具Apifox 相比于Postman&#xff0c;他还拥有一个非常nb的功能&#xff0c; 在接…

Table和HashBasedTable的使用案例

------------------- 1.普通使用 package org.example.testhashbasedtable;import com.google.common.collect.HashBasedTable; import com.google.common.collect.Table;import java.util.Map;public class TestHashBasedTable {public static void main(String[] args) {Ta…

福州大学《嵌入式系统综合设计》 实验八:FFMPEG视频编码

一、实验目的 掌握使用算能平台进行视频编码的流程&#xff0c;包括开发主机环境与云平台的配置&#xff0c;视频编码程序的编写与理解&#xff0c;代码的编译、运行以及学习使用码流分析工具分析视频压缩码流等。 二、实验内容 搭建实验开发环境&#xff0c;编译并运行编码…

小诺2.0开源版工程启动

小诺是一款开源的前后端开发框架&#xff0c;同若依、SpringBladex一样可作为私活、外包脚手架。 开源地址&#xff1a;Snowy: 最新&#xff1a;&#x1f496;国内首个国密前后分离快速开发平台&#x1f496;&#xff0c;采用Vue3AntDesignVue3 ViteSpringBootMpHuToolSaToke…

YOLOv5算法进阶改进(6)— 更换主干网络之ResNet18

前言:Hello大家好,我是小哥谈。ResNet18是ResNet系列中最简单的一个模型,由18个卷积层和全连接层组成,其中包含了多个残差块。该模型在ImageNet数据集上取得了很好的表现,成为了深度学习领域的经典模型之一。ResNet18的优点是可以解决深度神经网络中梯度消失的问题,使得性…

【Seata源码学习 】篇五 注册分支事务

【Seata源码学习 】篇五 分支事务注册 1.远程服务调用绑定XID 回到事务模版方法类TransactionalTemplate中 beginTransaction(txInfo, tx);Object rs;try {// Do Your Business// 执行执行拦截器链路rs business.execute();} catch (Throwable ex) {// 3. The needed busine…

Diffusion:通过扩散和逆扩散过程生成图像的生成式模型

在当今人工智能大火的时代&#xff0c;AIGC 可以帮助用户完成各种任务。作为 AIGC 主流模型的 DDPM&#xff0c;也时常在各种论文中被提起。DDPM 本质就是一种扩散模型&#xff0c;可以用来生成图片或者为图片去噪。 扩散模型定义了一个扩散的马尔科夫过程&#xff0c;每一步逐…

Day01 嵌入式 -----流水灯

一、简单介绍 嵌入式系统中的流水灯是一种常见的示例项目&#xff0c;通常用于演示嵌入式系统的基本功能和控制能力。流水灯由多个发光二极管&#xff08;LED&#xff09;组成&#xff0c;这些LED按照一定的顺序依次点亮和熄灭&#xff0c;形成一种像水流一样的流动效果。 二、…

VsCode连接远程Linux编译环境的便捷处理

1.免输登录密码 免输命令的正确方法是使用公钥和私鈅在研发设备&#xff0c;和linux服务器上校验身份。公钥和私钥可在windows系统上生成。公钥要发送到linux服务器。私钥需要通知给本地的ssh客户端程序&#xff0c;相关的操作如下&#xff1a; 生成 SSH Key&#xff1a; 打开…