用圖來(lái)表達(dá)更為復(fù)雜的數(shù)據(jù)關(guān)系課件

1、課時(shí)1用圖來(lái)表達(dá)更為復(fù)雜的數(shù)據(jù)關(guān)系圖的應(yīng)用舉例圖的定義、圖的方向和權(quán)重圖和樹的區(qū)別圖的實(shí)現(xiàn)和內(nèi)存表達(dá)課時(shí) 13圖的應(yīng)用舉例社交網(wǎng)絡(luò)是典型的網(wǎng)絡(luò)結(jié)構(gòu)可以用點(diǎn)來(lái)表達(dá)社交關(guān)系中的人，用點(diǎn)與點(diǎn)之間的連接來(lái)表達(dá)人與人的關(guān)系比如我們想要去表示誰(shuí)認(rèn)識(shí)誰(shuí)、誰(shuí)和誰(shuí)溝通、誰(shuí)能夠影響誰(shuí)等人與人之間的關(guān)系一個(gè)具體的例子是在小紅書上，比如，A 關(guān)注了 B 的小紅書，可以用 A 指向 B 的線來(lái)連接表示 這些人與人的社交信息，可以用來(lái)去解釋社交網(wǎng)絡(luò)的信息流動(dòng)圖的應(yīng)用舉例交通網(wǎng)絡(luò)也可以用圖來(lái)表達(dá)比如所有的城市可以用圖的節(jié)點(diǎn)來(lái)表示，城市間的交通渠道可以用邊來(lái)表示像最近大家關(guān)注的疫情封城措施，也可以用數(shù)據(jù)結(jié)構(gòu)來(lái)理解，就是把交通

2、網(wǎng)絡(luò)圖的一些邊進(jìn)行了阻隔圖的應(yīng)用舉例互聯(lián)網(wǎng)網(wǎng)站連接我們經(jīng)?？吹骄W(wǎng)站上會(huì)有指向其他網(wǎng)址的超鏈接如果我們把互聯(lián)網(wǎng)所有的網(wǎng)頁(yè)定義成圖的節(jié)點(diǎn)，那么網(wǎng)頁(yè)與網(wǎng)頁(yè)之間的邊就是這些鏈接了如果大家熟悉 Google 經(jīng)典的網(wǎng)頁(yè)排名算法 PageRank，就會(huì)知道，搜索引擎正是用指向一個(gè)網(wǎng)頁(yè)的引用數(shù)量去判斷一個(gè)網(wǎng)頁(yè)的質(zhì)量圖的定義、圖的方向和權(quán)重從數(shù)學(xué)規(guī)范上來(lái)講一個(gè)圖可以被定義成一個(gè)集合 G， G = (V,A)其中：V 是圖的節(jié)點(diǎn)集合A V V 是節(jié)點(diǎn)與節(jié)點(diǎn)之間的連接的邊，邊可以是有向或者是無(wú)向的圖的定義、圖的方向和權(quán)重ABDC有向圖以理解成生活中比如微博上的關(guān)注你可能關(guān)注了一個(gè)大 V，但是大 V 并不一定關(guān)注了

3、你 這就是一個(gè)單向的關(guān)系，可以用有向圖來(lái)建模圖的定義、圖的方向和權(quán)重?zé)o向圖比如在前面提到的交通網(wǎng)絡(luò)上海如果能通向北京的話，那北京也是能到達(dá)上海的圖的定義、圖的方向和權(quán)重012373465比如在交通網(wǎng)絡(luò)中假設(shè)北京去上海的交通費(fèi)用是 1000 元，而上海去武漢的交通費(fèi)用是 2000 元比如在商品交易網(wǎng)絡(luò)中如果把世界上所有的商品做成一個(gè)圖，商品與商品之間的交易價(jià)格定義成邊那么如果要用人民幣購(gòu)買口罩，則可能是 10 元人民幣但如果用人民幣兌換成美元，則需要 7 元人民幣圖的邊也可以有權(quán)重圖和樹的區(qū)別樹也是有節(jié)點(diǎn)和邊，那么圖和樹究竟有啥區(qū)別昵樹表達(dá)的是層級(jí)化的結(jié)構(gòu)，圖是用來(lái)表達(dá)網(wǎng)絡(luò)化的結(jié)構(gòu)圖的實(shí)現(xiàn)和內(nèi)存

4、表達(dá)圖有兩種常見的實(shí)現(xiàn)方式一種是鄰接矩陣法，另一種是鄰接鏈表法圖的實(shí)現(xiàn)和內(nèi)存表達(dá)1.鄰接矩陣法使用鄰接矩陣法的基本思想是開一個(gè)超大的數(shù)組，用數(shù)組中間元素的 true / false 來(lái)表達(dá)邊 具體什么意思呢？比如你有 V 個(gè)節(jié)點(diǎn)的圖，那么就需要一個(gè) VV 大小的數(shù)組圖的實(shí)現(xiàn)和內(nèi)存表達(dá)V2V1V4V3可以用 Gij 這樣的尋址方式來(lái)找到第 i 行第 j 列的元素在這個(gè)例子中規(guī)定，如果有從 Vi 指向 Vj 的邊，那么 Gij = true，反之如果沒有邊，則 Gij = falseV0圖的實(shí)現(xiàn)和內(nèi)存表達(dá)2.鄰接鏈表法核心思想是把每一個(gè)節(jié)點(diǎn)所指向的點(diǎn)給存儲(chǔ)起來(lái)V0V2V1V4V3圖的實(shí)現(xiàn)和內(nèi)存表達(dá)這兩種實(shí)現(xiàn)方式有什么區(qū)別昵鄰接矩陣法可以更快地添加和刪除邊，也可以更快地判斷邊是否存在但是鄰接矩陣法需要一個(gè) O(V2) 的內(nèi)存空間，相對(duì)來(lái)說(shuō)更適合邊比較多的圖鄰接鏈表法可以更快地操作一個(gè)節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，在一個(gè)稀疏的圖中也就是邊比較少的圖中，鄰接鏈表法的效率其實(shí)