103資訊學科培訓 圖論 - BFS & DFS & 應用 講者:林庭宇.

Slides:



Advertisements
Similar presentations
昆明机场. 目录  机场历史 机场历史  建设状况 建设状况  运行状况 运行状况  航线 航线.
Advertisements

青蘋果的代價 參考資料 : 國中性教育教學輔助媒體 (Power Point) 教師手冊. 影片欣賞 -- 愛的晚霞 單純的阿霞人生第一次的愛情,卻是帶來身心嚴重 的傷害,阿霞要如何面對感染愛滋後的生活 …
第十四章 人口(二) 高中地理(一). 第一節 人口成長 第二節 人口組成 第三節 人口問題 第十四章 人口(二)
中國歷史 社會主義文化大革命 我們的報告是關於中國著名的革命 —— 文化大革命。你可會立即想到它何時發 生、怎麼會發生等等。我們將會介紹文 化大革命,希望你細心欣賞。
党课讲座 入党的条件与程序.
中國大陸教育 督導制度探究 凌林煌教授/博士 講授 國立中山大學共同科歷史學程
温故知新 犬 戎 公元前 770年 周平王 公元前771年 东周 洛邑 西周 镐京.
让我们走进秋天.
日月光·伯爵居项目介绍.
香港故事之 三年零八個月的艱苦歲月 組員: 梁珮瑩 吳遠莉 李琪 李青儀 方松皓.
第一章 教育与教育学 讲授提纲 教育与教育学 思考题目 主讲: 白彦茹(教授) 阅读文献 教学目的与要求 教学重点与难点 退出.
我国政府受人民的监督 权力的行使:需要监督.
鹽酥蝦 蝦子先處理好 蝦頭剪至眼睛處,鬚及蝦頭的小腳也都剪乾淨 2 再用廚房用剪刀開背去腸泥
第四节 K线图研判技巧.
307暑假作業 自選部份,各項的範例!.
何谓学龄期 学龄期是指6~7岁入小学起至12~14岁进入青春期为止的一个年龄段。期小儿体格生长仍稳步增长,除生殖系统外其他器官的发育到本期末已接近成人水平。 这个时期发病率较前为低,但要注意预防近视眼和龋齿,矫治慢性病灶,端正坐、立、行姿势,安排有规律的生活、学习和锻炼,保证充足的营养和休息,注意情绪和行为变化,避免思想过度紧张。
我的故事 ————往事回首.
女生成功靠什么? 09英本四班 傅柏双.
国际投资环境罗氏评级法 美国.
彰化縣教師會 導護問題知多少? 理事長:許麗芳老師 報告人:廖銘潭老師   .
社会保障学 第5章 失业保险.
理想.
道路交通事故處理.
Chapter 10 Graphs.
固定与搬运技术 义乌市中心医院 陈红卫.
ACM/ICPC暑期集训讲座 二分图匹配 cnhawk
Chapter 12 圖形結構 12.1 圖形的一些專有名詞 12.2 圖形資料結構表示法 12.3 圖形追蹤 12.4 擴展樹
案例分析 胎记美容记 第6小组
歡 迎 各位視光界精英 蒞 臨 元培視光系 103校外學分班說明會.
高中地理(一) 第十六章 產業(二)林、漁、礦業.
班級:2年2班 座號:33 姓名:羅子惠 指導老師:黃源弘 資料來源:
第七章 人 口 第一節 種族的分布與現況 第二節 人口結構與成長 第三節 人口問題 總目錄.
第八組 組員:07黃佩瑄 13吳姿毅 14葉芷芸 26黃欣蓮 34林思妤 48潘婷蓉
人生五色臉 年輕十歲必學的小動作,九個保持身體健康的的小訣竅 人們常在不經意間做些小動作,並認為這是身體的本能反應,
第7章 图论基础与应用 PART A 《可视化计算》.
实践 课题 周围环境对当代大学生成长的影响 指导老师:王永章 小组成员:陈荣、刘若楠、张红艳、吕雪丹、樊金芳、李惠芬、黄婧
視野死角與內輪差 埔心國小交通安全團隊.
Minimum Spanning Trees
GRAPH THEORY 圖論 第二組 晏彩霞 陳弘益 王文斕.
Chap5 Graph.
Chap5 Graph.
第8章 圖形結構(Graphs) 8-1 圖形的基本觀念 8-2 圖形的表示法 8-3 圖形的走訪 8-4 擴張樹
Chapter 6 Graph Chang Chi-Chung
数学 九年级上、下册合订 新课标(ZJ).
Graph 2 Michael Tsai 2012/5/1 連載: 學生上課睡覺姿勢大全
Chapter 7 圖形與網路 資料結構導論 - C語言實作.
Chapter 7 圖形與網路 資料結構導論 - C語言實作.
資料結構 第7章 圖形結構.
Chapter12 Graphs Definitions Applications Properties
深度優先搜尋(DFS)與 廣度優先搜尋(BFS)
Ch07 圖形與網路 淡江大學 周清江
Chapter 2 Basic Concepts in Graph Theory
第9章 基本图算法 本章内容将包含基本的图形表示法,以及先深搜寻,先广搜寻,拓朴排序,Strongly Connected Components。
一位單身的女子孤單地獨自坐著 The Missing Piece Meets The Big O 失落的一角遇上大O 原者:雪兒、西斯丁 原文出自中文譯本:愛心樹 (The Giving Tree)
第十讲 刘少奇与中国革命和建设.
101北一女中 資訊選手培訓營 深度優先搜尋(DFS)的進階應用 Nan.
GOOD Afternoon 一条蛔虫的故事 上海市虹口区卫监所 潘瑜.
Teacher: 郭育倫 Mail: 演算法 Teacher: 郭育倫 Mail:
大圓小圓展風貌 ─圓面積 製作者:蔡怡真.
Course 8 回溯、分枝與限制 Backtracking, Branch-and-Bound
鄧姚文 資料結構 第八章:圖(Graph) 鄧姚文
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
霧台--魯凱族祕境.
Elementary Graph Algorithms
Advanced Competitive Programming
圖形結構 Graph Structure chapter 9 德明科技大學資訊科技系.
第二專長學分班第三次作業.
11506: Angry Programmer ★★★★☆ 題組:Contest Set Archive with Online Judge
Graph 1 Michael Tsai 2012/4/24 連載: 學生上課睡覺姿勢大全
JAVA 程式設計與資料結構 第二十一章 Graph.
Presentation transcript:

103資訊學科培訓 圖論 - BFS & DFS & 應用 講者:林庭宇

前情提要 各位認識圖嗎?

基本概念 Yes No BFS & DFS 就是圖形的「搜索」 實作時分別需要用到 Queue & Stack 可求取距離、連通等基礎資料 應用極廣 知道Stack和Queue嗎? Yes No

BFS 廣度優先搜索(Breadth-first Search) 先搜索完叉路再往下走 由近而遠的搜索 把走過的路連起來會變成一棵tree You need a Queue

範例

DFS 深度優先搜索(Depth-first Search) 先搜索完整條路再去走叉路 把走過的路連起來也會變成一棵tree You need a Stack

範例again

BUT 要記得剪枝!!! 時間複雜度 看資料型態而定 Adjacency matrix -> O(V^2) Adjacency lists -> O(V+E) BUT 要記得剪枝!!! 記下走過的點,以免重覆走浪費時間

練習時間 ZJ a290 b224 a753 d908

OAO~~~ 讓我們繼續看下去 DFS延伸概念 判斷DAG(Direct Acylic Graph) 拓樸排序(Topological Sort) 連通分量(Connected Components) 關節點(割點,Cut Point) OAO~~~

DFS延伸概念 Discovery time  Finishing time 1 5 7 6 2 4 3 2 4 1 8 7 6 8 5

DFS延伸2 Tree Edges: not yet discovered Back Edges: discovered but not yet finished Forward/Cross Edges: finished

DAG(Direct Acylic Graph) 有向無環圖 判斷方式:DFS 他沒有Back Edges!!!

拓樸排序 Topological Sort 將圖上的點進行排序 假如A -> B,則A要排在B之前 前提: 圖必須是一個DAG

做法: 1.先找出第一點 – 什麼點一定可以排在最前面? 2.進行拓樸排序 – 想想DFS延伸! => 1.任意一個沒有「入邊」的點 2.Finishing time!

拓樸範例 一個可行的拓樸排序: 9 2 0 5 6 3 7 8 1 4 Finishing time反排!!! 4 8 5 6 1 9 2 10 3

來個題目 ZJ a552 a454 d917

連通分量 連通關係(就有向圖來討論) 強連通>單向連通>弱連通 強連通-任兩點均有路來回 弱連通-化為無向圖後為相連圖形 單向連通-任兩點至少有單向路可走 強連通>單向連通>弱連通

強連通分量 strongly connected components(SCC) 用處:收縮圖形 怎麼找? -> 還是 DFS

關節點(割點,Cut Point) 無向圖中,少了就會使圖不連通的點

有圖有真相

怎麼找割點? -> DFS again!!! 用DFS tree來想

THE END P.S. 蒙地卡羅 is good!

補 - Stack 就像堆盤子一樣 遞迴就是一種Stack 陣列或STL

補 - Queue 就像排隊一樣(不考慮插隊) 陣列或STL Back