RBAC 权限

article/2025/9/16 9:04:37

RBAC权限分析

RBAC 全称为基于角色的权限控制,本段将会从什么是RBAC,模型分类,什么是权限,用户组的使用,实例分析等几个方面阐述RBAC

 

什么是RBAC

RBAC 全称为用户角色权限控制,通过角色关联用户,角色关联权限,这种方式,间阶的赋予用户的权限,如下图所示

对于通常的系统而言,存在多个用户具有相同的权限,在分配的时候,要为指定的用户分配相关的权限,修改的时候也要依次的对这几个用户的权限进行修改,有了角色这个权限,在修改权限的时候,只需要对角色进行修改,就可以实现相关的权限的修改。这样做增加了效率,减少了权限漏洞的发生。

 

模型分类

对于RBAC模型来说,分为以下几个模型 分别是RBAC0,RBAC1,RBAC2,RBAC3,这四个模型,这段将会依次介绍这四个模型,其中最常用的模型有RBAC0.

RBAC0

RBAC0是最简单的RBAC模型,这里面包含了两种。

用户和角色是多对一的关系,即一个用户只充当一种角色,一个角色可以有多个角色的担当。用户和角色是多对多的关系,即,一个用户可以同时充当多个角色,一个角色可以有多个用户。 

此系统功能单一,人员较少,这里举个栗子,张三既是行政,也负责财务,此时张三就有俩个权限,分别是行政权限,和财务权限两个部分。

RBAC1

相对于RBAC0模型来说,增加了子角色,引入了继承的概念。

 

RBAC2 模型

这里RBAC2模型,在RBAC0模型的基础上,增加了一些功能,以及限制

基数约束

即,用一个角色,所拥有的成员是固定的,例如对于CEO这种角色,同一个角色,也只能有一个用户。

先决条件

即,对于该角色来说,如果想要获得更高的角色,需要先获取低一级别的角色。举个栗子,对于副总经理和经理这两个权限来说,需要先有副总经理权限,才能拥有经理权限,其中副总经理权限是经理权限的先决条件。

运行时互斥

即,一个用户可以拥有两个角色,但是这俩个角色不能同时使用,需要切换角色才能进入另外一个角色。举个栗子,对于总经理和专员这两个角色,系统只能在一段时间,拥有其一个角色,不能同时对这两种角色进行操作。

RBAC3模型

即,RBAC1,RBAC2,两者模型全部累计,称为统一模型。

 

什么是权限

权限是资源的集合,这里的资源指的是软件中的所有的内容,即,对页面的操作权限,对页面的访问权限,对数据的增删查改的权限。举个栗子。对于下图中的系统而言,

 拥有,计划管理,客户管理,合同管理,出入库通知单管理,粮食安全追溯,粮食统计查询,设备管理这几个页面,对这几个页面的访问,以及是否能够访问到菜单,都属于权限。

用户组的使用

对于用户组来说,是把众多的用户划分为一组,进行批量授予角色,即,批量授予权限。举个栗子,对于部门来说,一个部门拥有一万多个员工,这些员工都拥有相同的角色,如果没有用户组,可能需要一个个的授予相关的角色,在拥有了用户组以后,只需要,把这些用户全部划分为一组,然后对该组设置授予角色,就等同于对这些用户授予角色。

优点:减少工作量,便于理解,增加多级管理,等。

SpringSecurity 简单使用

首先添加依赖

<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId>
</dependency>

然后添加相关的访问接口

package com.example.demo.web;import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;@RestController
@RequestMapping("/test")
public class Test {@RequestMapping("/test")public String test(){return "test";}
}

最后启动项目,在日志中查看相关的密码

 访问接口,可以看到相关的登录界面

 输入用户名和相关的密码

用户名:user
密码 984cccf2-ba82-468e-a404-7d32123d0f9c

登录成功

增加用户名和密码

在配置文件中,书写相关的登录和密码

spring:security:user:name: mingpassword: 123456roles: admin

在登录页面,输入用户名和密码,即可正常登录。

基于内存的认证

需要自定义类继承WebSecurityConfigurerAdapter代码如下

 即,配置的用户名为admin,密码为123,角色为admin

HttpSecurity

这里对一些方法进行拦截

 即,这里完成了对所有的方法访问的拦截

SpringSecurity 集成JWT

这是一个小demo,目的,登录以后返回jwt生成的token

导入依赖

添加web依赖

 导入JWT和Security依赖

<!-- https://mvnrepository.com/artifact/io.jsonwebtoken/jjwt --><dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.9.1</version></dependency><!-- https://mvnrepository.com/artifact/org.springframework.boot/spring-boot-starter-security --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId><version>2.3.1.RELEASE</version></dependency>

创建一个JwtUser实现UserDetails

创建 一个相关的JavaBean

package com.example.demo;import org.springframework.security.core.GrantedAuthority;
import org.springframework.security.core.userdetails.UserDetails;import java.util.Collection;public class JwtUser implements UserDetails {private String username;private String password;private Integer state;private Collection<? extends GrantedAuthority> authorities;public JwtUser(){}public JwtUser(String username, String password, Integer state,  Collection<? extends GrantedAuthority> authorities){this.username = username;this.password = password;this.state = state;this.authorities = authorities;}@Overridepublic Collection<? extends GrantedAuthority> getAuthorities() {return authorities;}@Overridepublic String getPassword() {return this.password;}@Overridepublic String getUsername() {return this.username;}@Overridepublic boolean isAccountNonExpired() {return true;}@Overridepublic boolean isAccountNonLocked() {return true;}@Overridepublic boolean isCredentialsNonExpired() {return true;}@Overridepublic boolean isEnabled() {return true;}
}

编写工具类生成令牌

编写工具类,用来生成token,以及刷新token,以及验证token

package com.example.demo;import io.jsonwebtoken.Claims;
import io.jsonwebtoken.Jwts;
import io.jsonwebtoken.SignatureAlgorithm;
import org.springframework.security.core.userdetails.UserDetails;import java.io.Serializable;
import java.util.Date;
import java.util.HashMap;
import java.util.Map;public class JwtTokenUtil implements Serializable {private String secret;private Long expiration;private String header;private String generateToken(Map<String, Object> claims) {Date expirationDate = new Date(System.currentTimeMillis() + expiration);return Jwts.builder().setClaims(claims).setExpiration(expirationDate).signWith(SignatureAlgorithm.HS512, secret).compact();}private Claims getClaimsFromToken(String token) {Claims claims;try {claims = Jwts.parser().setSigningKey(secret).parseClaimsJws(token).getBody();} catch (Exception e) {claims = null;}return claims;}public String generateToken(UserDetails userDetails) {Map<String, Object> claims = new HashMap<>(2);claims.put("sub", userDetails.getUsername());claims.put("created", new Date());return generateToken(claims);}public String getUsernameFromToken(String token) {String username;try {Claims claims = getClaimsFromToken(token);username = claims.getSubject();} catch (Exception e) {username = null;}return username;}public Boolean isTokenExpired(String token) {try {Claims claims = getClaimsFromToken(token);Date expiration = claims.getExpiration();return expiration.before(new Date());} catch (Exception e) {return false;}}public String refreshToken(String token) {String refreshedToken;try {Claims claims = getClaimsFromToken(token);claims.put("created", new Date());refreshedToken = generateToken(claims);} catch (Exception e) {refreshedToken = null;}return refreshedToken;}public Boolean validateToken(String token, UserDetails userDetails) {JwtUser user = (JwtUser) userDetails;String username = getUsernameFromToken(token);return (username.equals(user.getUsername()) && !isTokenExpired(token));}}

编写拦截器

编写Filter 用来检测JWT

package com.example.demo;import org.apache.commons.lang.StringUtils;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.security.authentication.UsernamePasswordAuthenticationToken;
import org.springframework.security.core.context.SecurityContextHolder;
import org.springframework.security.core.userdetails.UserDetails;
import org.springframework.security.core.userdetails.UserDetailsService;
import org.springframework.security.web.authentication.WebAuthenticationDetailsSource;
import org.springframework.stereotype.Component;
import org.springframework.web.filter.OncePerRequestFilter;import javax.servlet.FilterChain;
import javax.servlet.ServletException;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.io.IOException;@Component
public class JwtAuthenticationTokenFilter  extends OncePerRequestFilter {@Autowiredprivate UserDetailsService userDetailsService;@Autowiredprivate JwtTokenUtil jwtTokenUtil;@Overrideprotected void doFilterInternal(HttpServletRequest httpServletRequest, HttpServletResponse httpServletResponse, FilterChain filterChain) throws ServletException, IOException {String authHeader = httpServletRequest.getHeader(jwtTokenUtil.getHeader());if (authHeader != null && StringUtils.isNotEmpty(authHeader)) {String username = jwtTokenUtil.getUsernameFromToken(authHeader);if (username != null && SecurityContextHolder.getContext().getAuthentication() == null) {UserDetails userDetails = this.userDetailsService.loadUserByUsername(username);if (jwtTokenUtil.validateToken(authHeader, userDetails)) {UsernamePasswordAuthenticationToken authentication  =new UsernamePasswordAuthenticationToken(userDetails,null,userDetails.getAuthorities());authentication.setDetails(new WebAuthenticationDetailsSource().buildDetails(httpServletRequest));SecurityContextHolder.getContext().setAuthentication(authentication);}}}filterChain.doFilter(httpServletRequest, httpServletResponse);}
}

编写userDetailsService的实现类

在上方代码中,编写userDetailsService,类,实现其验证过程

package com.example.demo;import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.security.core.authority.SimpleGrantedAuthority;
import org.springframework.security.core.userdetails.User;
import org.springframework.security.core.userdetails.UserDetails;
import org.springframework.security.core.userdetails.UserDetailsService;
import org.springframework.security.core.userdetails.UsernameNotFoundException;
import org.springframework.stereotype.Service;import javax.management.relation.Role;
import java.util.List;@Service
public class JwtUserDetailsServiceImpl  implements UserDetailsService {@Autowiredprivate UserMapper userMapper;@Overridepublic UserDetails loadUserByUsername(String s) throws UsernameNotFoundException {User user = userMapper.selectByUserName(s);if (user == null) {throw new UsernameNotFoundException(String.format("'%s'.这个用户不存在", s));}List<SimpleGrantedAuthority> collect = user.getRoles().stream().map(Role::getRolename).map(SimpleGrantedAuthority::new).collect(Collectors.toList());return new JwtUser(user.getUsername(), user.getPassword(), user.getState(), collect);}
}

编写登录

编写登录业务的实现类 其login方法会返回一个JWTUtils 的token

@Service
public class UserServiceImpl  implements UserService {@Autowiredprivate UserMapper userMapper;@Autowiredprivate AuthenticationManager authenticationManager;@Autowiredprivate UserDetailsService userDetailsService;@Autowiredprivate JwtTokenUtil jwtTokenUtil;public User findByUsername(String username) {User user = userMapper.selectByUserName(username);return user;}public RetResult login(String username, String password) throws AuthenticationException {UsernamePasswordAuthenticationToken upToken = new UsernamePasswordAuthenticationToken(username, password);final Authentication authentication = authenticationManager.authenticate(upToken);SecurityContextHolder.getContext().setAuthentication(authentication);UserDetails userDetails = userDetailsService.loadUserByUsername(username);return new RetResult(RetCode.SUCCESS.getCode(),jwtTokenUtil.generateToken(userDetails));}
}

最后配置Config

@EnableGlobalMethodSecurity(prePostEnabled = true)
@EnableWebSecurity
public class WebSecurity extends WebSecurityConfigurerAdapter {@Autowiredprivate UserDetailsService userDetailsService;@Autowiredprivate JwtAuthenticationTokenFilter jwtAuthenticationTokenFilter;@Autowiredpublic void configureAuthentication(AuthenticationManagerBuilder authenticationManagerBuilder) throws Exception {authenticationManagerBuilder.userDetailsService(this.userDetailsService).passwordEncoder(passwordEncoder());}@Bean(name = BeanIds.AUTHENTICATION_MANAGER)@Overridepublic AuthenticationManager authenticationManagerBean() throws Exception {return super.authenticationManagerBean();}@Beanpublic PasswordEncoder passwordEncoder() {return new BCryptPasswordEncoder();}@Overrideprotected void configure(HttpSecurity http) throws Exception {http.csrf().disable().sessionManagement().sessionCreationPolicy(SessionCreationPolicy.STATELESS).and().authorizeRequests().antMatchers(HttpMethod.OPTIONS, "/**").permitAll().antMatchers("/auth/**").permitAll().anyRequest().authenticated().and().headers().cacheControl();http.addFilterBefore(jwtAuthenticationTokenFilter, UsernamePasswordAuthenticationFilter.class);ExpressionUrlAuthorizationConfigurer<HttpSecurity>.ExpressionInterceptUrlRegistry registry = http.authorizeRequests();registry.requestMatchers(CorsUtils::isPreFlightRequest).permitAll();}@Beanpublic CorsFilter corsFilter() {final UrlBasedCorsConfigurationSource urlBasedCorsConfigurationSource = new UrlBasedCorsConfigurationSource();final CorsConfiguration cors = new CorsConfiguration();cors.setAllowCredentials(true);cors.addAllowedOrigin("*");cors.addAllowedHeader("*");cors.addAllowedMethod("*");urlBasedCorsConfigurationSource.registerCorsConfiguration("/**", cors);return new CorsFilter(urlBasedCorsConfigurationSource);}
}

运行,返回token

运行,返回结果为token

 

SpringSecurity JSON登录

这里配置SpringSecurity之JSON登录

这里需要重写UsernamePasswordAnthenticationFilter类,以及配置SpringSecurity

重写UsernamePasswordAnthenticationFilter

public class CustomAuthenticationFilter extends UsernamePasswordAuthenticationFilter {@Overridepublic Authentication attemptAuthentication(HttpServletRequest request, HttpServletResponse response) throws AuthenticationException {//attempt Authentication when Content-Type is jsonif(request.getContentType().equals(MediaType.APPLICATION_JSON_UTF8_VALUE)||request.getContentType().equals(MediaType.APPLICATION_JSON_VALUE)){//use jackson to deserialize jsonObjectMapper mapper = new ObjectMapper();UsernamePasswordAuthenticationToken authRequest = null;try (InputStream is = request.getInputStream()){AuthenticationBean authenticationBean = mapper.readValue(is,AuthenticationBean.class);authRequest = new UsernamePasswordAuthenticationToken(authenticationBean.getUsername(), authenticationBean.getPassword());}catch (IOException e) {e.printStackTrace();authRequest = new UsernamePasswordAuthenticationToken("", "");}finally {setDetails(request, authRequest);return this.getAuthenticationManager().authenticate(authRequest);}}//transmit it to UsernamePasswordAuthenticationFilterelse {return super.attemptAuthentication(request, response);}}
}

配置SecurityConfig

@Override
protected void configure(HttpSecurity http) throws Exception {http.cors().and().antMatcher("/**").authorizeRequests().antMatchers("/", "/login**").permitAll().anyRequest().authenticated()//这里必须要写formLogin(),不然原有的UsernamePasswordAuthenticationFilter不会出现,也就无法配置我们重新的UsernamePasswordAuthenticationFilter.and().formLogin().loginPage("/").and().csrf().disable();//用重写的Filter替换掉原有的UsernamePasswordAuthenticationFilterhttp.addFilterAt(customAuthenticationFilter(),UsernamePasswordAuthenticationFilter.class);
}//注册自定义的UsernamePasswordAuthenticationFilter
@Bean
CustomAuthenticationFilter customAuthenticationFilter() throws Exception {CustomAuthenticationFilter filter = new CustomAuthenticationFilter();filter.setAuthenticationSuccessHandler(new SuccessHandler());filter.setAuthenticationFailureHandler(new FailureHandler());filter.setFilterProcessesUrl("/login/self");//这句很关键,重用WebSecurityConfigurerAdapter配置的AuthenticationManager,不然要自己组装AuthenticationManagerfilter.setAuthenticationManager(authenticationManagerBean());return filter;
}

这样就完成使用json登录SpringSecurity。

Spring Security 密码加密方式

需要在Config 类中配置如下内容

    * 密码加密*/@Beanpublic BCryptPasswordEncoder passwordEncoder(){return new BCryptPasswordEncoder();}

即,使用此方法,对密码进行加密,在业务层的时候,使用此加密的方法

@Service
@Transactional
public class UserServiceImpl implements UserService {@Resourceprivate UserRepository userRepository;@Resourceprivate BCryptPasswordEncoder bCryptPasswordEncoder;  //注入bcryct加密@Overridepublic User add(User user) {user.setPassword(bCryptPasswordEncoder.encode(user.getPassword())); //对密码进行加密User user2 = userRepository.save(user);return user2;}@Overridepublic ResultInfo login(User user) {ResultInfo resultInfo=new ResultInfo();User user2 = userRepository.findByName(user.getName());if (user2==null) {resultInfo.setCode("-1");resultInfo.setMessage("用户名不存在");return resultInfo;}//判断密码是否正确if (!bCryptPasswordEncoder.matches(user.getPassword(),user2.getPassword())) {resultInfo.setCode("-1");resultInfo.setMessage("密码不正确");return resultInfo;}resultInfo.setMessage("登录成功");return resultInfo;}
}

即,使用BCryptPasswordEncoder 对密码进行加密,保存数据库

使用数据库认证

这里使用数据库认证SpringSecurity

设计数据表

这里设计数据表

 着重配置SpringConfig

@Configurable
public class WebSecurityConfig extends WebSecurityConfigurerAdapter {@Autowiredprivate UserService userService;    // service 层注入@BeanPasswordEncoder passwordEncoder(){return new BCryptPasswordEncoder();}@Overrideprotected void configure(AuthenticationManagerBuilder auth) throws Exception {// 参数传入Service,进行验证auth.userDetailsService(userService);}@Overrideprotected void configure(HttpSecurity http) throws Exception {http.authorizeRequests().antMatchers("/admin/**").hasRole("admin").anyRequest().authenticated().and().formLogin().loginProcessingUrl("/login").permitAll().and().csrf().disable();}
}

这里着重配置SpringConfig


http://chatgpt.dhexx.cn/article/Ytp63A92.shtml

相关文章

RBAC模型

最近开始在找java项目&#xff0c;大部分时间都是跟着视频或者代码一步一步敲过来&#xff0c;但是对代码的理论层面还是有所欠缺&#xff0c;今天就来分享一个系统设计中的一个模型。不管是哪一个系统&#xff0c;都绕不开权限控制&#xff0c;因为现在的角色太多了&#xff0…

RBAC入门教程及实例演示

RBAC 一、RBAC的作用 在很多系统中&#xff0c;会要求不同的账户对应着不同的角色和权限。如教务管理系统&#xff0c;分为以下几种功能&#xff0c;不同的功能对应着不同的角色 如果要做到登录后根据账户的角色&#xff0c;给出相应的菜单&#xff0c;及规定当前角色只能做出…

RBAC简介(*)

一.RBAC是什么 1.RBAC模型概述 RBAC是Role Based Access Control的英文缩写&#xff0c;意思是 基于角色的访问控制。 RBAC实际上就是针对产品去挖掘需求时所用到的Who&#xff08;角色&#xff09;、What&#xff08;拥有什么资源&#xff09;、How&#xff08;有哪些操作&am…

什么是 RBAC 模型?

前言 RBAC&#xff08;Role-Based Access Control&#xff09;&#xff0c;基于角色的访问控制&#xff0c;现在主流的权限管理系统的权限设计都是 RBAC 模型&#xff0c;或者是 RBAC 模型的变形。 我们需要思考一个问题&#xff1a;为什么要做权限的管理&#xff1f; 我的理…

RBAC权限管理(详细)

RBAC权限设计思想 为了达成不同账号(员工、总裁)登录系统后看到不同页面&#xff0c;执行不同功能&#xff0c;RBAC(Role-Based Access control)权限模型&#xff0c;就是根据角色的权限&#xff0c;分配可视页面。 三个关键点: 用户:使用系统的人 角色&#xff1a;使用系统…

什么是RBAC

一、RBAC是什么 1、RBAC模型概述 RBAC模型&#xff08;Role-Based Access Control&#xff1a;基于角色的访问控制&#xff09;模型是20世纪90年代研究出来的一种新模型&#xff0c;但其实在20世纪70年代的多用户计算时期&#xff0c;这种思想就已经被提出来&#xff0c;直到…

最小生成树,秒懂!

&#x1f447;&#x1f447;关注后回复 “进群” &#xff0c;拉你进程序员交流群&#x1f447;&#x1f447; 作者丨bigsai 来源丨bigsai 前言 在数据结构与算法的图论中&#xff0c;(生成)最小生成树算法是一种常用并且和生活贴切比较近的一种算法。但是可能很多人对概念不是…

算法 - 最小生成树实现

算法能力是一个门槛&#xff0c;也是个有基础的门槛 无论你是iOS工程师&#xff0c;android工程师&#xff0c;java工程师&#xff0c;前端&#xff0c;后端还是全栈等等… 算法能力的强弱一方面在于思想&#xff0c;你是否有计算机思维抽象具体问题的能力 更重要的还在与基…

最小树形图(有向图的最小生成树)

我们知道&#xff0c;无向图的最小生成树的求法有Krusal和prime算法&#xff0c;一个是归点一个是归边&#xff0c;在具体实现上Krusal可以用并查集实现&#xff0c;难度不大。 这里稍微区别一下最短路径和最小生成树&#xff08;因为我又搞混了23333&#xff09; 最小生成树能…

Kruskal算法(最小生成树)

上篇Prim算法简要的讲解了最小生成树。也提到过Prim算法堆优化&#xff0c;但本蒟蒻并没有贴Prim &#xff08;堆优化的代码&#xff09;。至于为什么没有贴呢&#xff1f;上篇Prim算法blog末尾有说明。 好勒&#xff01;咱们接着讲Kruskal算法。这跟Prim算法有很大的…

最小生成树matlab求解

一、最小生成树 连通所有顶点且总路径最小修建连通7个城市的铁路网&#xff0c;可修建的路线和对应造价如图所示&#xff0c;如何修建使总费用最少&#xff1f; 问题分析&#xff1a; 连通7个城市&#xff1a;生成的图中&#xff0c;从任意顶点起步&#xff0c;沿着边一定可以…

最小生成树——贪心算法

文章目录 1.生成树和最小生成树1.1 问题的定义1.2 MST性质 2.普里姆算法&#xff08;Prim&#xff09;2.1 算法流程2.2 算法正确性证明2.3 算法实现2.4 时间复杂度2.5 测试代码 3.克鲁斯卡尔算法&#xff08;kruskal&#xff09;3.1 算法流程3.2 算法正确性证明3.3 算法实现 参…

C++ 最小生成树

目录&#xff1a; 前置知识 最小生成树 Prim 算法 kruskal 算法 前置知识&#xff1a; 连通图&#xff1a;在无向图中&#xff0c;若任意两个顶点 u 与 v 都有路径相通&#xff0c;则称该无向图为连通图。 强连通图&#xff1a;在有向图中&#xff0c;若任意两个顶点 u 与 …

最小生成树(C语言实现)

求这个网的最小生成树 /** 普里姆算法和克鲁斯卡尔算法求最小生成树* 采用邻接矩阵存储**/ #include<stdio.h>#define MAX_VERTEX_NUM 20 //图的定义 typedef struct {int vertexNum;int edgeNum;char vertex[MAX_VERTEX_NUM];int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]…

最小生成树(C语言)

最小生成树问题&#xff08;C语言&#xff09; 所谓一个 带权图 的最小生成树&#xff0c;就是原图中边的权值最小的生成树 &#xff0c;所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。 kruskal 克鲁斯卡尔算法&#xff08;Kruskal&#xff09;是一种使用贪…

最小生成树kruskal算法

最小生成树kruskal算法 概述算法分析代码 概述 克鲁斯卡尔 ( K r u s k a l ) (Kruskal) (Kruskal)算法是求连通网的最小生成树的另一种方法。与普里姆 ( P r i m ) (Prim) (Prim)算法不同&#xff0c;它的时间复杂度为 O ( e l o g e ) O(eloge) O(eloge)(e为网中的边数)&…

最小生成树:

定义&#xff1a; 将图中的 n 结点用 n-1 条边连接起来&#xff0c;使其各个边的权值之和最小的生成树。 普里姆算法&#xff1a; 从点的角度出发。 1、start 数组的值表示起始点的下标&#xff0c;start 的下标代表目的顶点&#xff1b;lowcost 数组的下标代表目的顶点&…

图——最小生成树

图——最小生成树 1. 基本概念 在一个连通无向图G(V, E)中&#xff0c;对于其中的每条边(u,v)∈E&#xff0c;赋予其权重w(u, v)&#xff0c;则最小生成树问题就是要在G中找到一个连通图G中所有顶点的无环子集T⊆E&#xff0c;使得这个子集中所有边的权重之和w(T) ∑ ( u , …

最小生成树的Kruskal算法-详解

最小生成树的Kruskal算法 一、 什么是最小生成树 1.1 最小生成树定义&#xff1a; 一个有 n 个结点的连通图的生成树是原图的极小连通子图&#xff0c;且包含原图中的所有 n 个结点&#xff0c;并且有保持图连通的最少的边。最小生成树可以用kruskal&#xff08;克鲁斯卡尔&a…

最小生成树(C语言简单实现)

最小生成树 本文参考自《大话数据结构》 一个连通图的生成树是一个极小的连通子图&#xff0c;它含有图中全部的顶点&#xff0c;但只有足以构成一棵树的n-1条边。我们把构造连通网的最小代价生成树称为最小生成树 。 找连通网的最小生成树&#xff0c;经典的有两种算法&#…