代碼隨想錄算法訓練營第50天 | 圖論理論基礎、深搜理論基礎、98. 所有可達路徑、廣搜理論基礎

圖論理論基礎

題目鏈接/文章講解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

了解圖的基本概念,連通性,圖的構造,圖的遍歷方式

深搜理論基礎

題目鏈接/文章講解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E6%B7%B1%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

了解dfs 和 bfs的大體區別,dfs的搜索過程以及代碼框架。

98. 所有可達路徑

題目鏈接/文章講解:https://www.programmercarl.com/kamacoder/0098.%E6%89%80%E6%9C%89%E5%8F%AF%E8%BE%BE%E8%B7%AF%E5%BE%84.html

深度優先搜索:

1. 確認遞歸函數,參數

首先我們dfs函數一定要存一個圖,用來遍歷的,需要存一個目前我們遍歷的節點,定義為x。

還需要存一個n,表示終點,我們遍歷的時候,用來判斷當 x==n 時候 標明找到了終點。

代碼如下:

vector<vector<int>> result; // 收集符合條件的路徑
vector<int> path; // 0節點到終點的路徑
// x:目前遍歷的節點
// graph:存當前的圖
// n:終點
void dfs (const vector<vector<int>>& graph, int x, int n) {

2. 確認終止條件

什么時候我們就找到一條路徑了?

當目前遍歷的節點 為 最后一個節點 n 的時候 就找到了一條 從出發點到終止點的路徑。

代碼如下:

// 當前遍歷的節點x 到達節點n 
if (x == n) { // 找到符合條件的一條路徑result.push_back(path);return;
}

3. 處理目前搜索節點出發的路徑

接下來是走 當前遍歷節點x的下一個節點。

首先是要找到 x節點指向了哪些節點呢? 遍歷方式是這樣的:

for (int i = 1; i <= n; i++) { // 遍歷節點x鏈接的所有節點if (graph[x][i] == 1) { // 找到 x指向的節點,就是節點i}
}

接下來就是將 選中的x所指向的節點,加入到 單一路徑來。

path.push_back(i); // 遍歷到的節點加入到路徑中來

進入下一層遞歸

dfs(graph, i, n); // 進入下一層遞歸

最后就是回溯的過程,撤銷本次添加節點的操作。

path.pop_back(); // 回溯,撤銷本節點

廣搜理論基礎?

題目鏈接/文章講解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E5%B9%BF%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

了解廣度優先搜索的使用場景、過程和代碼框架

總結

第50天,繼續加油

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/96507.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/96507.shtml
英文地址,請注明出處:http://en.pswp.cn/web/96507.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

華為HCIE-云計算培訓課程有哪些?

華為HCIE云計算認證是華為公司推出的高級別認證&#xff0c;對于想要在云計算領域發展&#xff0c;提高專業技能和競爭力的人來說具備極高的價值。接下里就來聊聊華為HCIE云計算的培訓課程都有哪些&#xff1f;如何高效備考呢&#xff1f;一&#xff0c;HCIE云計算培訓課程1、理…

DCS控制回路優化:基于WebSocket的實時參數遠程調校方法論

說起來&#xff0c;我前段時間剛啃完一個化工廠DCS控制回路優化的硬骨頭&#xff0c;用WebSocket搞成了實時參數遠程調校&#xff0c;現在回想起來&#xff0c;滿是能跟大家嘮的實操經驗&#xff0c;說不定你們以后碰到類似情況&#xff0c;能少走些冤枉路。先跟大家交代下背景…

《JVM如何排查OOM》

目錄 一、什么是OOM&#xff1f; 二、OOM排查的整體思路 三、OOM排查工具大全 四、實戰&#xff1a;不同OOM場景的排查方法 場景1&#xff1a;Java heap space 場景2&#xff1a;Metaspace 場景3&#xff1a;GC overhead limit exceeded 五、高級排查技巧 1. 使用Arth…

ubuntu22.04 安裝Docker

一、更新系統包索引sudo apt update && sudo apt upgrade -y二、安裝必要依賴安裝 curl、gnupg等工具&#xff0c;用于添加 Docker 官方 GPG 密鑰和倉庫&#xff1a;sudo apt install -y ca-certificates curl gnupg三、添加 Docker 官方 GPG 密鑰sudo install -m 0755…

高低壓隔離器的技術演進與行業賦能

電力電子系統的安全架構與效率升級&#xff0c;始終依賴高低壓電路間的可靠隔離。高低壓隔離器作為能量傳輸與信號控制的核心媒介&#xff0c;通過持續迭代的絕緣技術與結構創新&#xff0c;為新能源裝備、工業驅動系統提供底層安全屏障。其阻斷電位差傳導、抑制電磁干擾的能力…

嵌入式 - ARM5

一、led點燈代碼優化1. 配置寄存器volatile1.??禁止優化??不對該變量的讀寫操作進行任何優化&#xff08;如刪除“冗余”讀取或延遲寫入&#xff09;。2.??強制內存訪問??每次訪問該變量時&#xff0c;必須直接從內存&#xff08;或硬件寄存器&#xff09;中讀取或寫入…

SSH登錄管理

兩種配置方法-密碼 -密鑰&#xff08;免密&#xff09;ansible 默認 rhel9 禁止 root 用密碼登陸&#xff0c;不禁止用密鑰登陸 ---修改方式----vim /etc/ssh/sshd_config 修改此文件#PermitRootLogin prohibit-passwordPermitRootLogin yes 改為允許systemctl res…

遠程連接--向日葵

下載安裝卸載 向日葵語言設置 點擊下面的圖標,點擊"設置": 問題解決 向日葵被連接之后自動黑屏 取消下面的勾選框: 向日葵連接之后黑屏 檢查系統的協議: echo $XDG_SESSION_TYPE 如果是: wayland 需要切換為x11. 設置永久默認使用 X11: sudo vi /etc/gdm3/custom…

Liunx執行source /etc/profile 報錯, -bash: HISTTIMEFORMAT: readonly variable

今天在配置java環境變量時&#xff0c;執行source /etc/profile報錯&#xff0c;系統是統信OS&#xff0c;花了好長時間才解決&#xff0c;在這記錄一下&#xff0c;希望能幫助到大家問題截圖提示HISTTIMEFORMAT和PROMPT_COMMAND變量時只讀變量&#xff0c;不能設置屬性值解決辦…

什么是達林頓管?

簡單來說&#xff0c;達林頓管是一個“電流放大器中的大力士”。它的核心目的是用非常小的輸入電流&#xff08;基極電流&#xff09;去控制一個非常大的輸出電流&#xff08;集電極電流&#xff09;。達林頓管是由兩個三極管串聯而成&#xff0c;放大倍數是兩個三極管的放大倍…

嵌入式Linux學習_rk3588移植無線網卡驅動

記錄移植無線網卡驅動遇到的各種問題&#xff1a; 從官網上下載8821的驅動源碼復制一份上面的CONFIG_PLATFORM_ARM_RK2818&#xff0c;改成3588&#xff0c;然后選項改成y&#xff0c;并把autodetect關掉。 找到CONFIG_PLATFORM_ARM_RK2818&#xff0c;復制一份&#xff0c;改成…

MCP專題五、MCP 的未來趨勢與展望

MCP專題五:MCP 的未來趨勢與展望 5.1 引言 本專題前四章我們系統性地學習了 MCP(Model Context Protocol)的 發展背景、核心機制、Python 實戰方法以及典型應用場景。可以看到,MCP 并不僅僅是一個技術標準,它更像是 大模型與外部世界溝通的橋梁,推動了 AI 應用從“實驗…

C++ Dijkstra堆優化算法

時間復雜度為&#xff1a;O((nm)logn)算法特點&#xff1a;非負邊權、單源最短路、頂點數、邊數<1000000&#xff0c;數據結構前置&#xff1a;領接表、哈希表、二叉堆算法&#xff1a;第一步&#xff0c;建圖&#xff0c;任何算法我們都要去思考&#xff0c;用什么數據結構…

網頁設計作業02

<!DOCTYPE html> <html> <head><meta charset"utf-8"/><title>網頁設計作業</title> </head> <body><h2>問卷調查</h2><p><strong>1、你是通過什么途徑來到綠葉學習網的&#xff1f;</s…

每日算法題推送-->今日專題——雙指針法

題目1&#xff1a;https://leetcode.cn/problems/move-zeroes 小編剛看到這道題的時候&#xff0c;想到的第一個方法就是建立一個與原數組等大的新的數組&#xff0c;然后遍歷原數組&#xff0c;如果遇到元素值不為0的元素&#xff0c;就將這個元素放到新數組中&#xff0c;直到…

告別單次對話:上下文工程如何重塑AI應用架構

1. 前言人工智能應用開發領域正在經歷一場靜悄悄的變革。去年此時&#xff0c;提示工程&#xff08;Prompt Engineering&#xff09;還是各大技術論壇的熱門話題&#xff0c;開發者們熱衷于分享各種精心設計的提示詞模板&#xff0c;試圖通過單次交互獲得理想的大模型輸出。然而…

PM2 管理后端(設置項目自啟動)

查看pm2管理pm2 list ┌────┬──────────────┬─────────────┬─────────┬─────────┬──────────┬────────┬──────┬───────────┬──────────┬──────────┬──…

CCN中商再獲三項知識產權,為數字化服務添動能

上海中商網絡股份有限公司&#xff08;CCN中商&#xff09;依托持續的研發投入與深厚的技術積淀&#xff0c;在知識產權領域再獲重要突破——成功收獲三項知識產權&#xff0c;囊括實用新型專利《一種3D霓彩智感雙條光柱印刷用全自動生產線》、發明專利《一種一物一碼關聯系統及…

使用LTspice仿真一個異步BUCK電路

確定異步BUCK的規格 輸入電壓&#xff08;Vin&#xff09;&#xff1a;12V 輸出電壓&#xff08;Vout&#xff09;&#xff1a;6V 最大輸出電流&#xff08;Iout&#xff09;&#xff1a;3A 開關頻率&#xff08;fsw&#xff09;&#xff1a;400kHz 輸出電壓紋波&#xff08;Δ…

R語言對excel中多個sheet子表批量進行地理探測器計算

## 基本設置 ## 1) 設定你的工作目錄&#xff08;保持你的原路徑不變&#xff09; setwd("D:/*****/*****/******")## 2) 文件名&#xff08;與xlsx實際名字保持一致&#xff09; xlsx_file <- "驅動因素&#xff08;中低收入&#xff09;.xlsx"## 依…