图论专题(各类算法和蓝桥杯真题例题)

这篇具有很好参考价值的文章主要介绍了图论专题(各类算法和蓝桥杯真题例题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.图论入门

1.1存边方式

1.1.1 数组存边

图论专题(各类算法和蓝桥杯真题例题)

 1.1.2 临接矩阵存边

图论专题(各类算法和蓝桥杯真题例题)

 1.1.3 临接表存边

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

 1.2 图的遍历和连通性

通过DFSBFS遍历每一个图

对于非连通图,循环对每一个点dfs操作

也可以通过并查集来判断连通性

1.2.1全球变暖例题

图论专题(各类算法和蓝桥杯真题例题)

import sys
sys.setrecursionlimit(60000)  # 设置最大递归深度,默认递归深度有点小,不设置递归会出问题
 
def dfs(x,y):
  d=[(-1,0),(0,1),(1,0),(0,-1)]  # 左 上 右 下
  global flag
  vis[x][y] =1
  if mp[x][y+1]=='#' and mp[x][y-1] =='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':
    # 说明点(x,y)四周都是陆地
    flag = 1  # 高地标记,不会被淹没
  for i in range(4):
    nx=x+d[i][0]
    ny=y+d[i][1]
    if vis[nx][ny] ==0 and mp[nx][ny] =='#':
      # 如果当前没有遍历点(nx,ny)同时地图上面该点不是陆地
      dfs(nx,ny)
 
n=int(input())
mp = []   # 记录地图
for i in range(n):
  mp.append(list(input()))
vis =[]   # 判断是否走过
for i in range(n):
  vis.append([0]*n)
 
ans =0
for i in range(n):  # 遍历每一点
  for j in range(n):
    if vis[i][j] ==0 and mp[i][j] =='#':  # 相当于找连通分量
      flag = 0
      dfs(i,j)
      if flag==0:
        ans+=1
 
print(ans)
    

1.3 欧拉路和欧拉回路

图论专题(各类算法和蓝桥杯真题例题)

 哈密顿回路:图中每个点通过且只通过一次

1.3.1欧拉路和欧拉回路判定

        无向图

        如果图中的点全都是偶点,则存在欧拉回路;任意一点都可以作为起点和终点。

        如果只有2个奇点,则存在欧拉路,其中一个奇点是起点,另一个是终点。不可能出现有奇数个奇点的无向图。

        有向图

        把一个点上的出度记为1,入度记为 -1,这个点上所有出度和入度相加,就是它的度数。
        一个有向图存在欧拉回路,当且仅当该图所有点的度数为零。
        如果只有一个度数为1的点,一个度数为-1的点,其它所有点的度数为0,那么存在欧拉路径,其中度数为1的是起点,度数为–1的是终点。

1.3.2 欧拉路劲例题

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

## 不全,没看懂
import sys
import collections
import itertools
import heapq
sys.setrecursionlimit(300000)

def dfs(u):
    i=d[u]   # 从点u的第一条边i=0开始
    while(i<len(G[u])):
        d[u]=i+1  # 后面继续走u的下一条边
        dfs(G[u][i]) # 继续走这条边的邻居点
        i=dp[u]   # 第i条边走过了,不再重复走
    rec.append(u)

M=100100
n,m = map(int,input().split())  # n个点,m条边
du=[[0 for _ in range(2)] for _ in range(M)]  # 记录入度,出度
G=[[] for _ in range(n+1)]  # 临接表存图
d=[0 for _ in range(M)]  # d[u]=i : 当前走u的第i个边
rec=[]   #记录欧拉路
    

for i in range(m):
    u,v =map(int,input().split())
    G[u].append(v)
    du[u][1]+=1   #出度
    du[v][0]+=1   #入度
for i in range(1,n+1):
    G[i].sort()   # 对邻居点排序,字典序
    S=1

2.Floyd算法

2.1 Floyd介绍

图论专题(各类算法和蓝桥杯真题例题)

 算法对比图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

 2.2算法模板

import sys
import collections
import itertools
import heapq
sys.setrecursionlimit(300000)

def floyd():
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if dp[i][k]+dp[k][j] <dp[i][j]:
                    dp[i][j]=dp[i][k]+dp[k][j] 

 2.3 算法总结

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

 2.4 算法例题

2.4.1 蓝桥公园

图论专题(各类算法和蓝桥杯真题例题)

import sys
import collections
import itertools
import heapq
sys.setrecursionlimit(300000)



def floyd():
  for i in range(1,n+1):
    for j in range(1,n+1):
      for k in range(1,n+1):
        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
 
n,m,q = map(int,input().split())
inf=2**120  #自定义无穷大
dp=[[inf]*(n+1) for i in range(n+1)]  # 初始为无穷大
choice=[]
for i in range(m):
  u,v,w=map(int,input().split())   # 无向图,临接矩阵存边
  dp[u][v]=w
  dp[v][u]=w 
for i in range(q):   # 读 起点和终点
  s,d = map(int,input().split()) 
  choice.append((s,d))
floyd()
for s,d in choice:
  if dp[s][d]!=inf:
    print(dp[s][d])
    continue
  print(-1)
   

2.4.2 路径

图论专题(各类算法和蓝桥杯真题例题)

 标准的floyd算法

import sys
import collections
import itertools
import heapq
import math
sys.setrecursionlimit(300000)


# 标准的floyd


def lcm(x,y):   # 求最下公倍数
    return x//math.gcd(x,y)*y

def floyd():
    for k in range(1,2022):
        for i in range(1,2022):
            for j in range(1,2022):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

        
dp=[[int(0x3f3f3f3f3f3f3f) for _ in range(2022)] for _ in range(2022)]
for i in range(1,2022):
    for j in range(1,2022):
        if abs(i-j)<=21:  # 题意中的如果两个结点的差的绝对值不大于21
            dp[i][j]=lcm(i,j)

print(dp[1][2021]

 简化版Floyd算法

import sys
import collections
import itertools
import heapq
sys.setrecursionlimit(300000)


import math
def lcm(i,j):
  return i//math.gcd(i,j)*j
 
dp=[[2**50]*2022 for i in range(2022)]
# 创建图
for i in range(1,2022):
  for j in range(i,2022):  
    if abs(i-j)<=21:
      dp[i][j]=lcm(i,j)
 
# 找最短路径
for k in range(1,2022):
  for i in range(1,2):
    for j in range(1,2022):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
print(dp[1][2021])  # 1026837
 

Bellman-Ford算法

import sys
import collections
import itertools
import heapq
import math
sys.setrecursionlimit(300000)


# Bellman_Ford算法


def lcm(x,y):   # 求最下公倍数
    return x//math.gcd(x,y)*y
        
dp=[int(0x3f3f3f3f3f3f3f) for _ in range(2022)]
for i in range(1,2022):
    for j in range(i+1,i+22): # 题意中的如果两个结点的差的绝对值不大于21
        if j>2021: break
            dp[j]=min(dp[j],dp[i]+lcm(i,j))  # 更新最短路

print(dp[2021])

3.Dijstra算法

3.1 算法简介

图论专题(各类算法和蓝桥杯真题例题)

 图论专题(各类算法和蓝桥杯真题例题)

 3.2算法举例

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题) 

 

 3.3 例题模板

3.3.1 蓝桥王国

图论专题(各类算法和蓝桥杯真题例题)

import sys
import collections
import itertools
import heapq   # 默认小顶堆
import math
sys.setrecursionlimit(300000)


def dij(s):
    vis=[0 for i in range(n+1)]  # 标志是否访问过
    hp=[]  # 堆
    dis[s]=0  # 自身到自身的距离为0
    heapq.heappush(hp,(0,s))  # 列表堆化同时入堆
    while hp:
        u=heapq.heappop(hp)[1]  # 出堆,出的是结点
        if vis[u]: # 判断是否处理过
            continue
        vis[u]=1
        for i in G[u]:
            v,w=i[0],i[1]
            if vis[v]:
                continue
            if dis[v]>dis[u]+w:
                dis[v]=dis[u]+w
                heapq.heappush(hp,(dis[v],v))
    

n,m=map(int,input().split())
s=1
G=[[]for i in range(n+1)]  # 临接表存图
inf=2**64
dis=[inf]*(n+1)   # 从1到其他点的距离
for i in range(m):  # 邻接表存m条边
    u,v,w=map(int,input().split())
    G[u].append((v,w))
dij(s)   # 以s为起点到其他点的最短路径
for i in range(1,n+1):
    if dis[i]>=inf :
        print("-1",end=' ')
    else:
        print(dis[i],end=" ")
    

3.3.2 矩阵矩阵形式的Dijstra模板

 图论专题(各类算法和蓝桥杯真题例题)图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)
 
 
 
def dij():
   dist[1]=0  #很重要
   for _ in range(n-1): # 还有n-1个点没有遍历
      t=-1
      for j in range(1,n+1):
         if st[j]==0 and (t==-1 or dist[t]>dist[j]):  #找到没处理过得最小距离点
            t=j
      for j in range(1,n+1):
         dist[j]=min(dist[j],dist[t]+gra[t][j])  # t-j的距离,找最小值
      st[t]=1  # 标记处理过
   return dist[n]
      
n,m=map(int,input().split())
 #下标全部转为从1开始
stay=[0]+list(map(int,input().split()))
stay[n]=0   
gra = [[float('inf')] * (n+1) for _ in range(n+1)]
dist = [float('inf')] * (n+1)
st=[0]*(n+1)  # 标志是否处理
 
 
for i in range(m):
   u,v,w=map(int,input().split()) #这里重构图
   gra[u][v]=stay[v]+w
   gra[v][u]=stay[u]+w
 
 
print(dij())
   

4.Bellman-Ford算法

4.1 算法简介

单源最短路径问题:给定一个起点s,求它到图中所有n个结点的最短路径。

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

 4.2 算法模板和例题

4.2.1 出差问题

图论专题(各类算法和蓝桥杯真题例题)

 Bellman——Ford实现

import sys
import collections
import itertools
import heapq   # 默认小顶堆
import math
sys.setrecursionlimit(300000)

n,m = map(int,input().split())
t=[0]+list(map(int,input().split()))  # 从t=1开始
e=[]  # 数组存边
for i in range(1,m+1):
    a,b,c = map(int,input().split())
    e.append([a,b,c])
    e.append([b,a,c])    # 双向边

dist=[2**64]*(n+1)  # 存储到终点的距离
dist[1]=0
for k in range(1,n+1):  # 最大循环n次,即n个点
    for a,b,c in e:  # 检查每条边
        res=t[b]  # b的隔离时间
        if b==n:
            res=0
        dist[b]=min(dist[b],dist[a]+c+res)   # 问邻居是否能到达起点
print(dist[n])

 Dijstra实现

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)
 
 
 
def dij():
   dist[1]=0  #很重要
   for _ in range(n-1): # 还有n-1个点没有遍历
      t=-1
      for j in range(1,n+1):
         if st[j]==0 and (t==-1 or dist[t]>dist[j]):  #找到没处理过得最小距离点
            t=j
      for j in range(1,n+1):
         dist[j]=min(dist[j],dist[t]+gra[t][j])  # t-j的距离,找最小值
      st[t]=1  # 标记处理过
   return dist[n]
      
n,m=map(int,input().split())
 #下标全部转为从1开始
stay=[0]+list(map(int,input().split()))
stay[n]=0   
gra = [[float('inf')] * (n+1) for _ in range(n+1)]
dist = [float('inf')] * (n+1)
st=[0]*(n+1)  # 标志是否处理
 
 
for i in range(m):
   u,v,w=map(int,input().split()) #这里重构图
   gra[u][v]=stay[v]+w
   gra[v][u]=stay[u]+w
 
 
print(dij())
   

图论专题(各类算法和蓝桥杯真题例题)  

5.SPFA算法

5.1 算法简介

改进的Bellman-Ford算法

图论专题(各类算法和蓝桥杯真题例题)

 5.2 算法步骤

图论专题(各类算法和蓝桥杯真题例题)

5.3 算法例题和模板

5.3.1 随机数据下的最短路问题

图论专题(各类算法和蓝桥杯真题例题)

图论专题(各类算法和蓝桥杯真题例题)

import sys
import collections
import itertools
import heapq   # 默认小顶堆
import math
sys.setrecursionlimit(300000)


def spfa(s):
    dis[s]=0
    hp=[]
    heapq.heappush(hp,s)
    inq=[0]*(n+1)   # 判断是否在队列中
    inq[s]=1
    while(hp):
        u=heapq.heappop(hp)
        inq[u]=0
        ''' 下面两句认为没用,因为队列中的u都是因为上一个结点的邻居更新后
            放进来的,删了之后一样AC '''
        if dis[u]==inf:   #到起点的距离为无穷大,没有必要更新邻居
            continue
        for v,w in e[u]:    # 遍历u的邻接表
            if dis[v]>dis[u]+w:
                dis[v]=dis[u]+w
                if(inq[v]==0):  # 状态有更新,v的邻居可以通过他得到更近路径
                    heapq.heappush(hp,v)
                    inq[v]=1
n,m,s = map(int,input().split())
e=[[] for i in range(n+1)]  # 临接表存边
inf=2**64
dis=[inf]*(n+1)
for i in range(m):  # 读边
    u,v,w = map(int,input().split())
    e[u].append((v,w))   # 邻接表存边,有向图
spfa(s)
for i in range(1,n+1):
    if dis[i]>=inf:
        print('-1',end=' ')
    else:
        print(dis[i],end=' ')

 5.4 Dijstra和SPFA对比

图论专题(各类算法和蓝桥杯真题例题)图论专题(各类算法和蓝桥杯真题例题)

6.最小生成树算法

6.1 Prim算法

图论专题(各类算法和蓝桥杯真题例题)

6.1.1 修建公路(例题模板)

图论专题(各类算法和蓝桥杯真题例题)

import sys
import collections
import itertools
import heapq   # 默认小顶堆
import math
sys.setrecursionlimit(300000)


def prim():
    ans,cnt=0,0   # cnt 是加入MST的点的数量
    q=[]
    vis=[0 for i in range(n+1)]   # 1 表示点在MST中
    heapq.heappush(q,(0,1))
    while q and cnt<n:
        w,u = heapq.heappop(q)   # 出距离集合最近的点
        if  vis[u] !=1:  # 不再MST中
            vis[u]=1
            ans+=w
            cnt+=1
            for v,w in e[u]:   # 遍历点u的邻居,边长为w
                heapq.heappush(q,[w,v])  # 加入MST的点的数量不等于n,说明原图不连通
    if cnt!=n:   # 加入MST的点的数量不等于n,说明原图不连通
        print('-1')
    else:
        print(ans)

        
n,m = map(int,input().split())
e=[[] for i in range(n+1)]
for i in range(m):
    u,v,w  =map(int,ipnut().split())
    e[u].append((v,w))  # u的邻居是v,边长w
    e[v].append((u,w))  # 双向边

prim()

6.2 Krusal算法

图论专题(各类算法和蓝桥杯真题例题)

通过并查集实现

 6.2.1 例题模板(修建公路)

图论专题(各类算法和蓝桥杯真题例题)

import sys
import collections
import itertools
import heapq   # 默认小顶堆
import math
sys.setrecursionlimit(300000)


def find(x):
    if s[x] ==x:
        return x
    s[x]=find(s[x])  # 路径压缩
    return s[x]

def merge(x,y):
     s[find(y)]=find(x)
def kruskal():
    cnt=0
    ans=0
    e.sort(key=lambda x: x[2])  # 将边从小到大排序
    for i in range(n+1):   # 并查集初始化
       s.append(i)
    for i in range(m):  # 遍历所有边
        x,y=e[i][0],e[i][1]
        e1,e2 =find(x),find(y)
        if e1==e2:  # 属于同一个集,要这条边的话产生圈
            continue
        else:
            ans+=e[i][2]
            merge(x,y)
            cnt+=1
        if cnt==n-1:
            break
    if cnt!=n-1:   # 边的数量不等于n-1,说明有点不再MST上面
        print(-1)
    else:
        print(ans)
    return
e=[]  # 数组存边
s=[]  # 并查集
n,m=map(int,input().split())
for i in range(m): # 存m条边
    u,v,w = map(int,input().split())
    e.append((u,v,w))   # 存边
kruskal()

6.3 两种算法对比

图论专题(各类算法和蓝桥杯真题例题)

7.一道国赛题的4种解法

图论专题(各类算法和蓝桥杯真题例题)文章来源地址https://www.toymoban.com/news/detail-436248.html

import os
import sys
import itertools
import heapq

# Bellman-Ford O(mn)
'''
n,m=map(int,input().split())
stay=[0]+list(map(int,input().split()))
stay[n]=0  # 终点不需要隔离
e=[]
for i in range(m):
  a,b,c=map(int,input().split())
  e.append([a,b,c])
  e.append([b,a,c])

dp=[sys.maxsize for i in range(n+1)] 
dp[1]=0  #到起点的距离为0
def Bellman_ford():
  for i in range(1,n+1): # n个点
    for j in e:  # m条边
      v1,v2,cost=j
      #if v2==n:  # n号城市不需要隔离时间
      dp[v2]=min(dp[v2],dp[v1]+cost+stay[v2])
Bellman_ford()
print(dp[n])
'''


# Dijstra  临接表写法 O(n*n)
'''
n,m=map(int,input().split())
stay=[0]+list(map(int,input().split()))
stay[n]=0  # 终点不需要隔离
edge=[[]for i in range(n+1)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[a].append([b,c+stay[b]])
  edge[b].append([a,c+stay[a]])

hp=[]
vis=[0 for i in range(n+1)]
dp=[sys.maxsize for i in range(n+1)]
dp[1]=0  # 自身到自身距离为0
def dijstra():
  heapq.heappush(hp,(0,1)) 
  while hp:
    u=heapq.heappop(hp)[1]
    if vis[u]:
      continue
    vis[u]=1
    for i in range(len(edge[u])): # 遍历u的边
      v,w=edge[u][i][0],edge[u][i][1]
      if vis[v]:
        continue
      if dp[v]>dp[u]+w:
        dp[v]=dp[u]+w
        heapq.heappush(hp,(dp[v],v))    
dijstra()

print(dp[n])
'''


# Dijstra临接矩阵写法  O(n*n)
'''
n,m=map(int,input().split())
stay=[0]+list(map(int,input().split()))
stay[n]=0  # 终点不需要隔离
edge=[[sys.maxsize for i in range(n+1)]for i in range(n+1)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[a][b]=c+stay[b]
  edge[b][a]=c+stay[a]

vis=[0 for i in range(n+1)]
dp=[sys.maxsize for i in range(n+1)]
dp[1]=0  # 自身到自身距离为0

def dijstra():
  for i in range(n-1):   #只需要处理n-1个点
    t=-1
    for j in range(1,n+1):   # 找到没处理过得并且距离最小的
      if vis[j]==0 and(t==-1 or dp[j]<dp[t] ):
        t=j
    for j in range(1,n+1):
      dp[j]=min(dp[j],dp[t]+edge[t][j])
    vis[t]=1
dijstra()
print(dp[n])
'''

# SPFA
'''
n,m=map(int,input().split())
stay=[0]+list(map(int,input().split()))
stay[n]=0  # 终点不需要隔离
edge=[[]for i in range(n+1)]   #临接表存边
for i in range(m):
  a,b,c=map(int,input().split())
  edge[a].append([b,c+stay[b]])
  edge[b].append([a,c+stay[a]])
  
dp=[sys.maxsize for i in range(n+1)]
dp[1]=0  # 自身到自身距离为0


def spfa():
  hp=[]
  heapq.heappush(hp,1)   #用堆实现相当于优先队列,加快一点效率罢了
  in_hp=[0 for i in range(n+1)]  # 标记数组换为了判断是否在队列中 
  in_hp[1]=1  # 1在队列
  while hp:
    u=heapq.heappop(hp)
    in_hp[u]=0  # 标记为不在队列
    if dp[u]==sys.maxsize:   # 没有处理过的点,直接跳过,只处理邻居点
      continue
    for i in range(len(edge[u])): # 遍历u的边
      v,w=edge[u][i][0],edge[u][i][1]
      if dp[v]>dp[u]+w:
        dp[v]=dp[u]+w
        if in_hp[v]==0: # 他的邻居不再队列,就把他入队,方便下下次更新邻居的邻居结点
          heapq.heappush(hp,v)    
          in_hp[v]=1
spfa()
print(dp[n])
'''

到了这里,关于图论专题(各类算法和蓝桥杯真题例题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯专题-真题版含答案-【贪吃蛇长度】【油漆面积】【绘制圆】【高次方数的尾数】

    点击跳转专栏=Unity3D特效百例 点击跳转专栏=案例项目实战源码 点击跳转专栏=游戏脚本-辅助自动化 点击跳转专栏=Android控件全解手册 点击跳转专栏=Scratch编程案例 点击跳转=软考全系列 点击跳转=蓝桥系列 专注于 Android/Unity 和各种游戏开发技巧,以及 各种资源分享 (网站、

    2024年02月16日
    浏览(44)
  • 题目3180:蓝桥杯2023年第十四届省赛真题-互质数的个数======及探讨互质专题

    https://www.dotcpp.com/oj/problem3162.html 已AC。 (1)首先大家要知道什么叫互质: 以及它们的性质: 在数论中,对正整数n,欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数(由高斯所命名)或是欧拉总计函数(totient fu

    2023年04月24日
    浏览(43)
  • 【C++算法模板】图论-拓扑排序,超详细注释带例题

    推荐视频链接:D01 拓扑排序 给定一张 有向无环图 ,排出所有顶点的一个序列 A A A 满足:对于图中的每条有向边 ( x , y ) (x,y) ( x , y ) , x x x 在 A A A 中都出现在 y y y 之前,则称 A A A 是该图的顶点的一个拓扑序 拓扑排序 可以判断有向图中是否有环,可以生成拓扑序列 对于下

    2024年04月15日
    浏览(39)
  • 浅谈图论——迪杰斯特拉算法(leetcode例题,C++演示)

    如果你想问这个世界上什么算法是最牛逼的?博主是回答不上来的。但是,如果你问博主 什么数据结构是最牛逼 ?博主个人认为 图是最牛逼的数据结构 。因为很多的问题,都可以用图这种数据结构来表示。链表、树这种数据结构博主认为可以看成一种 特殊的图 。所以,博

    2024年02月20日
    浏览(81)
  • 蓝桥杯专题-真题版含答案-【九宫幻方】【打鱼还是晒网】【阶乘尾数零的个数】【等差素数列】

    点击跳转专栏=Unity3D特效百例 点击跳转专栏=案例项目实战源码 点击跳转专栏=游戏脚本-辅助自动化 点击跳转专栏=Android控件全解手册 点击跳转专栏=Scratch编程案例 点击跳转=软考全系列 点击跳转=蓝桥系列 专注于 Android/Unity 和各种游戏开发技巧,以及 各种资源分享 (网站、

    2024年02月15日
    浏览(41)
  • 【蓝桥杯】高频算法考点及真题详解小结

    🙊🙊 作者主页 :🔗求不脱发的博客 📔📔 精选专栏 :🔗数据结构与算法 📋📋 精彩摘要 : 考前看一看,AC手拿软。蓝桥杯高频算法考点小结,包括各大算法、排序算法及图的优先遍历原则知识点小结。预祝大家取得优异成绩。 💞💞 觉得文章还不错的话欢迎大家点赞

    2023年04月11日
    浏览(36)
  • E - Souvenir(图论典型例题)

    思路:对于有很多询问的题,一般都是先初始化。我们求出每个点到其他点的最短路径以及相同路径下最大的价值和即可。 代码:

    2024年01月25日
    浏览(28)
  • 图论基础知识 并查集/例题

    学习记录自代码随想录 并查集常用来解决连通性问题。 判断两个元素是否在同一个集合里的时候,要想到用并查集。 并查集主要有两个功能: 1.将两个元素添加到一个集合中; 2.判断两个元素在不在同一个集合。 例题:20240410 Huawei机考

    2024年04月25日
    浏览(34)
  • 蓝桥杯第六讲--简单dp【例题】

    蓝桥杯官网:蓝桥杯大赛——全国大学生TMT行业赛事 ✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识,此博客为第六讲:简单dp【例题】 本篇博客所包含习题有: 👊 01背包问题 👊 摘花生 👊 最长上升子序列 简单dp【习题】见博客:蓝桥杯第六讲–简单dp【习题】 博客内容以

    2023年04月25日
    浏览(43)
  • 【数学建模常用模型】图论专题

            图论是研究点、线间关系的一门学科。现实生活中,凡是涉及到事物间的关系,都可以抽象为图论模型。图论模型也是各大数学建模中常见的一种模型,主要用于计算、规划最短距离、路线等问题。下面介绍几个基本概念和算法。   单源最短路         单源最短路

    2024年02月06日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包