這節(jié)課開始就是陳越姥姥的課了，開心~~
圖作為一個抽象概念鳞仙，在生活中有很多應(yīng)用實例：
圖書管理、社交網(wǎng)絡(luò)等
一些如最短路徑和最小生成樹問題也給我們很大的幫助
圖是一種多對多的結(jié)構(gòu)笔时，類似為線性表+樹的綜合
一些概念
一組頂點 V vertex的集合
一組邊 E edge的集合
一條邊=頂點對 （v,w）無向 <v棍好，w>有向
不考慮重邊和自回路
Graph的抽象數(shù)據(jù)類型G（V,E）由非空有限頂點集合V+有限邊集合E
如果帶上邊的權(quán)值 => 網(wǎng)絡(luò)
操作集
創(chuàng)建
插入頂點
插入變
DFS
BFS
最短距離
MST最小生成樹
程序?qū)崿F(xiàn)
1.鄰接矩陣
G[N][N]二維數(shù)組存儲
若<vi，vj>有邊=> G[i][j]=1 否則為0
最后生成一個N*N的數(shù)組
特點
①對角都是0
②對稱允耿，因為存了2次造成了浪費
我們把他化為一維數(shù)組借笙，長度為n（n+1）/2，只存下三角矩陣的元素
原某點的位置Gij->G（i（i+2）/2+j）
網(wǎng)絡(luò)的實現(xiàn)较锡，把原來G的值由1定義為邊的權(quán)重业稼，沒有邊為0，但對于網(wǎng)絡(luò)而言蚂蕴，這并不是好的表現(xiàn)方法
好處：
①直觀
②方便查邊
③方便查鄰接點
④方便計算度（相關(guān)邊的個數(shù)）
無向=非0個數(shù)
有向=非0個數(shù) 行（出度） 列（入度）
缺點：
①浪費空間 -對于稀疏圖而言低散，邊少
②浪費時間
2.鄰接表
G[N]數(shù)組指針俯邓，非0元素存成鏈表
特點：
①一條邊被存了2遍
②每個結(jié)點都是編號+指針，占位置
③帶權(quán)重的話處理很麻煩
和鄰接矩陣比要夠稀疏的話才合算
好處：
①好找鄰接點熔号，鏈表遍歷
②節(jié)約稀疏圖空間 N個頭結(jié)點+2E個結(jié)點（每個結(jié)點有2個域）
③算頂點的度
無向 好算
有向 麻煩 出度（好算） 入度（重新構(gòu)造逆鄰接表..麻煩）
是否方便檢查任兩點是否有邊稽鞭？NO！
3.圖的其他表示方法
具體問題具體分析
圖的遍歷
DFS
類似先序遍歷
復(fù)雜度：
鄰接表O（N+E）
鄰接矩陣O（NN）
BFS
類似層次遍歷
鄰接表O（N+E）
鄰接矩陣O（NN）
圖不連通問題
幾個概念
連通：
路徑：
連通圖：
連通分量：
這一節(jié)開始聽得迷迷糊糊的引镊，包括下面的兩個例子也都聽得似懂非懂朦蕴，需要去看書，加深理解
兩個例子
拯救007
六度空間理論
