北一女中 資訊選手培訓營 圖論基礎 By Nan(2012.07.08 ).

Slides:



Advertisements
Similar presentations
1 曾老師、各位同學大家好 ! 首先自我介紹 ; 個人聯合大學電機系 畢業,服完兩年兵役後, 75 年開始就 業 ; 四年內換了幾個工作, 79 年創立貿 特科技, 90 年、 91 年分別於大陸寧波 與昆山設立特一電子與柏特電子,經 歷 20 年的工作磨鍊,今天事業上算是 穩定、成熟 ! 承蒙曾老師看重,利用一.
Advertisements

中正國中 特教組長 粘玉芳 校內分機 : /02/21. 下列條件擇一: 一、身心障礙手冊 二、特殊教育學生鑑定及就學輔導會證明.
示範課 -- 作文立意. 重溫作文構思課  構思嘗試深化  多角度思考  宜先剖析題目, 運用聯想, 循序漸進擴大範圍, 然後歸納材料, 定訂主題  同學的作品, 反映部分能夠掌握, 主線清晰, 層 層深入, 舉例恰當  但有部分同學只有枝葉, 欠缺主線, 更無中心思 想, 反映立意不足.
幼教人員法律事件探討 ─ 幼兒教育及照顧法 姚其壯 第一章 總則〈第一條至第六條〉 第二章 幼稚園設立及其教保服務 〈第七條至第十四條〉 第三章 幼稚園組織與人員資格及權益 〈第十五條至第二十八條〉 第四章 幼稚權益保障 〈第二十九條至第三十三條〉 第五章 家長之權利與義務 〈第三十四條至第四十條〉
畫面中的兩個人要去參加金融業儲備幹部的面試 活動,你認為誰的面試穿著是正確的? V.S 動動腦 V.S 動動腦 慎重 讓人感到 尊重 輕便 讓人聯想 隨便 畫面中的兩個人要去參加金融業儲備幹部的面試 活動,你認為誰的面試穿著是正確的?
IT 服务与业务发展融合 王维航 北京华胜天成科技股份有限公司 十分钟的悲剧.
高考心理辅导  福建中医药大学  林山  高考是什么?  真有那么 “ 苦大仇深 ” ?  为什么不能是 “ 快乐挑战 ” ?  高考(事) --- 认知(怎么个事 - 压力大小) --- 情绪反应(烦躁、焦虑、害怕 VS 自信、 从容、期盼) --- 行为表现(发挥正常.
蕭文生 中正大學法律系教授兼法學院院長.  壹、前言  貳、司法院釋字第六八四號解釋  參、大學生之受教權  肆、大學自治之範疇  伍、大學生之其他基本權利  陸、救濟管道之改善  柒、結語.
大陸學歷採認相關問題 楊景堯 淡江大學中國大陸研究所. 學歷採認的定義與範圍 廣義的定義 — 承認學歷 狹義的定義 — 具備任職, 任教, 考試資格 範圍 — 高等教育為主 台灣人取得大陸學歷的採認 大陸人取得大陸學歷的採認 外國人取得大陸學歷的採認.
提昇餐廳供餐品質 及服務滿意度 標竿學習主題 標竿學習計劃排定進度 分析客戶對餐廳供餐滿意度偏低原因:
第八課 謝 天. 第八課 謝 天 作者主旨文章作法 民國 陳之藩 謙卑感 恩,功 成不居 以「謝天」的傳統觀念 為中心,經由疑惑、思 索、領悟三個層次的敘 述,賦予新的意義 ★題目含義:表示對很多「人」的感謝。
蔬菜大觀園 V.S 大家來種菜 蔬菜的外觀及分類  蔬菜是我們常吃的食物,蔬菜的外觀形狀不 同,有各種不同的顏色、形狀、氣味等,嚐 起來的味道也不相同。  蔬菜的營養價值不盡相同,可實用的部位也 不同,有的是根、有的是莖、有的是葉、有 的是花、有的是果實,還有的是種子。  依據蔬菜種類和食用部位的不同,可以將蔬.
社工之路的通行證 --- 社工師證照 考試心得分享 東吳大學社工系碩一 呂錦綸. 一、考前準備 閱讀主流老師的書籍、掌握各科概要。 閱讀主流老師的書籍、掌握各科概要。 重視概念性的知識,打好基礎是很重要低 ~ 重視概念性的知識,打好基礎是很重要低 ~ 是必備讀物 ! 是必備讀物 ! 勤作考古題,參考當年度碩士班考試及高.
政府的权力:依法行使. 政府的权力:依法行使 重庆“最牛钉子户”事件 九龙坡区法院一名张院长称,法院已组织6次调解,有时1天就有2次调解。3月28日下午,九龙坡区委书记郑洪还专门接待吴苹3小时。1日,在法院组织下,拆迁双方基本达成口头协议,今天下午,双方签字生效。按协议,吴苹选择了异地实物安置方案,开发商将其在沙坪坝开发的一处门面房,按同样面积交付吴苹,吴同意此方案.
第八課 馮諼客孟嘗君 謀職達人 來也.
心理学辅导.
蔬菜大觀園V.S大家來種菜 高雄市楠梓區翠屏國中小教師 林珮如
“腸”保安康 現代人的腸胃保健.
那一段「詩聲戀」的日子 孟令今老師.
獨立國家國協 1.地形 2.氣候 3.產業.
綜合活動領域 教學分享.
诚信人生 ---高二(2)班主题班会.
兩岸融合教育之議題: 以東莞台商子弟學校為例
航向未來 飛揚國際 —關於華航與長榮的財務報表 指導老師: 組員:張甄芸 4A 鄭雅華 4A070079
世界史.
面对苦难 (约翰福音15:18-16:4) 2/22/15 我们不属世界,神从这世界中拣选了我们,却没有为我们另设一处“世外桃源”,乃是让我们住在地上,以他的信实为粮,以他的生命为光。既然在这被罪玷污的世界中,就会有苦难仇恨,然而它们不能打倒我们,因为它们 无目的 无缘故 无胜算 在世上我们虽有苦难,也可以放心,因为耶稣已经胜了世界。
如果你没法阻止战争,那你就把战争的真相告诉世界
102學年度第二學期 208家長座談會 歐陽美慧.
小綠葉蟬的『祕蜜』~ 蜜香烏龍茶.
個人投資理財與策略 富蘭克林:邱良弼.
第六章 中国公务员制度 干部 VS 公务员.
穿越迷雾,读懂全球化经济本质 谈美国次贷危机与人民币升值问题.
教育部 試辦中小學 教師專業發展評鑑基本概念 台中教育大學 徐照麗.
大陸教育基本現況認識 楊景堯 淡江大學中國大陸研究所.
第三章 魏晉南北朝的分合.
移民與文化--鄉愁的想像 王婉甄.
性別平權.
青龙偃月刀 韩少功. 青龙偃月刀 韩少功 走近作者 韩少功,湖南长沙人。1985年倡导“寻根文学”的主将。1996年出版的长篇小说《马桥词典》。比较著名的有《爸爸爸》、《女女女》等。
2008年3月8日 順德聯誼總會何日東小學上午及下午校
彰化基督教醫院 健康檢查科 / 家庭醫學科 吳美鳳醫師
經濟系 在學什麼專業? 經濟學是一門研究人類經濟行為的社會科學 為什麼鑽石會比水貴? 為什麼台灣中央銀行不多印一點台幣, 以增加大家的財富?
葉金源臨床心理師 台南市臨床心理師公會理事長 台南市社區大學生命與健康學程講師 台南縣家庭教育中心審查委員 台南地方法院家事調解委員
“三生教育”专题 生命·生存·生活.
公文寫作及實務.
校园信息管理系统 河北科技大学网络中心 2000/4/10.
“机票预定”操作流程.
寻觅节日诗情.
徵收苗栗市福全段147、1588及文心段10、11地號等4筆土地之
讲 义 大家好!根据局领导的指示,在局会计科和各业务科室的安排下,我给各位简要介绍支付中心的工作职能和集中支付的业务流程。这样使我们之间沟通更融洽,便于我们为预算单位提供更优质的服务。 下面我主要从三方面介绍集中支付业务,一是网上支付系统,二是集中支付业务流程及规定等,
中国人民公安大学经费管理办法(试行) 第一章总则 第四条:“一支笔” “一支笔”--仅指单位主要负责人。负责对本 单位的经费进行审核审批。
資料結構與C++程式設計進階 資料結構概論 講師:林業峻 CSIE, NTU 6/ 7, 2010.
Chap5 Graph.
Linked List Operations
第6章 佇列(Queues) 6-1 佇列的基礎 6-2 佇列的表示法 6-3 環狀佇列 6-4 雙佇列.
資料結構 第5章 佇列.
第8章 圖形結構(Graphs) 8-1 圖形的基本觀念 8-2 圖形的表示法 8-3 圖形的走訪 8-4 擴張樹
补充内容 结构体 概述 定义结构体类型和定义结构体变量 结构体变量的引用 结构体变量的初始化 指针与结构体 用typedef定义类型的别名.
101北一女中 資訊選手培訓營 快速排序函式qsort() Nan.
101北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
101北一女中 資訊選手培訓營 圖論基礎 Nan.
(Circular Linked Lists)
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
資料結構 第4章 堆疊.
101北一女中 資訊選手培訓營 深度優先搜尋(DFS)的進階應用 Nan.
微信商城系统操作说明 色卡会智能门店.
第三章 世界文明的蛻變與互動 第一節 歐洲社會的蛻變 第二節 世界文明的交匯 第三節 亞洲大帝國的發展 1.
北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
大綱 一.受試者之禮券/禮品所得稅規範 二.範例介紹 三.自主管理 四.財務室提醒.
第7章 图.
Presentation transcript:

北一女中 資訊選手培訓營 圖論基礎 By Nan(2012.07.08 )

圖論,到底是什麼呢?

圖論最常出現的形式: 點(Vertex or Node) 邊(Edge) 兩種在程式裡表示的方式: 鄰接矩陣跟鄰接串列 權重(Weight) <無向邊vs. 有向邊> 權重(Weight) 兩種在程式裡表示的方式: 鄰接矩陣跟鄰接串列

鄰接矩陣 [0] [1] [2] [3] [4] 1 map 無權重無向邊 int map[5][5] = 1 無權重無向邊 int map[5][5] = { {0, 0, 1, 1, 1}, {0, 0, 0, 0, 1}, {1, 0, 0, 0, 1}, {1, 0, 0, 0, 0}, {1, 1, 1, 0, 0} };

鄰接矩陣 [0] [1] [2] [3] [4] 1 6 INF 4 3 map 有權重無向邊 #define INF 2147483647 1 6 INF 4 3 有權重無向邊 #define INF 2147483647 int map[5][5] = { {0, 1, 6, INF, INF}, {1, 0, 4, 3, 1}, {6, 4, 0, 1, INF}, {INF, 3, 1, 0, 1}, {INF, 1, INF, 1, 0} };

鄰接矩陣 無權重有向邊 有權重有向邊 [0] [1] [2] [3] [4] 1 [0] [1] [2] [3] [4] 2 INF 1 5 map [0] [1] [2] [3] [4] 1 有權重有向邊 map [0] [1] [2] [3] [4] 2 INF 1 5 6 3

鄰接串列 2 3 4 1 [0] [1] [2] [3] [4] map 無權重無向邊 struct node * map[5]; 1 無權重無向邊 struct node { int id; struct node *next; }; struct node * map[5];

鄰接串列 [0] [1] [2] [3] [4] map 1/1 2/6 0/6 1/4 0/1 1/3 3/1 2/4 3/3 4/1 2/1 有權重無向邊 struct edge { int id; int weight; struct edge *next; }; struct edge* map[5];

鄰接串列 無權重有向邊 基本上跟無向的很像, 只是只會有一個方向有邊。 所以…換你畫囉~~ 有權重有向邊

補充:串接的方式 #include <stdlib.h> #define NEW(T, N) (T)malloc((N) * sizeof(T) ) struct edge { int id; int weight; struct edge *next; }; int main(){ struct edge *map[5]; struct edge *ptr = 0; ptr = NEW(struct edge, 1); ptr->id = 1; ptr->weight = 1; ptr->next = NULL; map[0] = ptr; ptr->id = 2; ptr->weight = 6; map[0]->next = ptr; //… }

你暈了嗎? 別擔心,我們目前比較常用的是鄰接矩陣的做法。 但真正在寫軟體什麼的話,是要用鄰接串列喔!