簡(jiǎn)介本資源是一份面向計(jì)算機(jī)專業(yè)本科生及數(shù)據(jù)結(jié)構(gòu)初學(xué)者的圖存儲(chǔ)結(jié)構(gòu)實(shí)踐教學(xué)材料聚焦鄰接矩陣與鄰接表兩種核心表示方法的原理對(duì)比、相互轉(zhuǎn)換及C語(yǔ)言實(shí)現(xiàn)。資源以完整可運(yùn)行的實(shí)驗(yàn)代碼為核心涵蓋有向圖的鄰接矩陣定義、鄰接表結(jié)構(gòu)體設(shè)計(jì)、MatToList與ListToMat雙向轉(zhuǎn)換函數(shù)、鄰接矩陣/鄰接表的打印輸出功能并附帶詳細(xì)實(shí)驗(yàn)?zāi)康?、?wèn)題描述、實(shí)現(xiàn)要求與手動(dòng)輸入擴(kuò)展說(shuō)明。壓縮包為1個(gè)55KB的docx文檔內(nèi)含結(jié)構(gòu)清晰的實(shí)驗(yàn)報(bào)告正文、完整源碼含注釋、關(guān)鍵算法邏輯解析及運(yùn)行示例截圖便于讀者理解內(nèi)存分配、鏈表頭插法、二維數(shù)組遍歷等底層操作細(xì)節(jié)。目前已有8612人學(xué)習(xí)下載適合用于課程實(shí)驗(yàn)復(fù)現(xiàn)、期末復(fù)習(xí)鞏固或算法崗筆試前的圖基礎(chǔ)強(qiáng)化訓(xùn)練。1. 圖的存儲(chǔ)不是“存圖”而是給關(guān)系建一張可查、可走、不卡頓的交通地圖你有沒(méi)有試過(guò)在手機(jī)地圖里搜“從A地到B地怎么走”結(jié)果等了三秒才彈出路線那背后很可能就藏著今天要講的兩個(gè)詞鄰接矩陣和鄰接表。它們不是什么高深算法而是圖這種數(shù)據(jù)結(jié)構(gòu)在電腦里“安家落戶”的兩種基本戶型——一個(gè)像全市統(tǒng)一規(guī)劃的網(wǎng)格狀地鐵線路圖橫縱坐標(biāo)全是站名交叉點(diǎn)標(biāo)著“有/無(wú)直達(dá)線”另一個(gè)像每個(gè)地鐵站自己貼的“本站可換乘”小紙條1號(hào)線站口貼著“去西站、去北廣場(chǎng)、去機(jī)場(chǎng)”2號(hào)線站口另貼一版。為什么非得搞兩種因?yàn)楝F(xiàn)實(shí)中的“關(guān)系網(wǎng)”千差萬(wàn)別有的圖密得像蜂巢比如朋友圈里人人互關(guān)用網(wǎng)格圖查“張三和李四熟不熟”快如閃電有的圖稀得像沙漠里的綠洲比如全國(guó)高速路網(wǎng)300個(gè)地級(jí)市只連了不到500條高速再畫滿600×600的表格99%格子都填“沒(méi)路”純屬浪費(fèi)內(nèi)存。學(xué)生做實(shí)驗(yàn)時(shí)總卡在“為什么轉(zhuǎn)換后輸出亂碼”“為什么鄰接表打印不出邊”其實(shí)問(wèn)題不在代碼而在沒(méi)想清你手里的圖到底是個(gè)“高密度老城區(qū)”還是個(gè)“低密度開(kāi)發(fā)區(qū)”選錯(cuò)了戶型房子蓋得再漂亮住著也憋屈。這份《數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)--圖的鄰接矩陣和鄰接表存儲(chǔ)》資源就是一套帶施工圖、驗(yàn)房清單和踩坑筆記的“圖結(jié)構(gòu)精裝房交付包”。2. 鄰接矩陣用一張固定尺寸的方格紙把所有可能的關(guān)系都攤開(kāi)寫死2.1 它長(zhǎng)什么樣——二維數(shù)組就是它的身份證鄰接矩陣的本質(zhì)是一張頂點(diǎn)數(shù)×頂點(diǎn)數(shù)的方格紙。假設(shè)圖里有6個(gè)頂點(diǎn)編號(hào)0到5那這張紙就是6行6列的二維數(shù)組arcs[6][6]。每個(gè)格子arcs[i][j]的含義非常直白從頂點(diǎn)i出發(fā)能不能一步走到頂點(diǎn)j如果是無(wú)權(quán)圖填1表示“能”0表示“不能”如果是有權(quán)圖比如帶距離、耗時(shí)、費(fèi)用就填具體數(shù)值比如arcs[0][3] 7表示“從0號(hào)點(diǎn)到3號(hào)點(diǎn)邊權(quán)是7”空缺或不存在的邊按慣例填一個(gè)極大值如代碼里的INF 32767或-1避免和有效權(quán)值混淆。提示代碼中#define MAX_VERTEX_NUM 20是預(yù)留的“最大戶型面積”。實(shí)際圖只有6個(gè)點(diǎn)但數(shù)組仍按20×20分配——這是為擴(kuò)展性留的余量不是浪費(fèi)。就像買房簽合同寫“建筑面積120㎡”實(shí)際得房率可能80%但承重墻位置早定死了。2.2 它最擅長(zhǎng)什么——三類操作快得像條件反射鄰接矩陣的強(qiáng)項(xiàng)全來(lái)自它“地址固定、索引直達(dá)”的物理結(jié)構(gòu)查邊存在性O(shè)(1)問(wèn)“0號(hào)點(diǎn)和3號(hào)點(diǎn)之間有邊嗎”——直接看arcs[0][3]是不是0或INFCPU一次內(nèi)存尋址搞定比翻通訊錄找人還快。改邊權(quán)O(1)把“0→3”的距離從7改成9arcs[0][3] 9一行賦值毫無(wú)拖泥帶水。遍歷所有邊O(n2)需要統(tǒng)計(jì)全圖有多少條邊把整個(gè)n×n表格掃一遍加總非零/非INF元素即可。雖然慢但邏輯極簡(jiǎn)不怕漏。// 示例快速判斷兩點(diǎn)是否連通鄰接矩陣核心能力 int isEdgeExist(MGraph *g, int i, int j) { if (i 0 || i g-vexnum || j 0 || j g-vexnum) return 0; // 越界檢查防玄學(xué)崩潰 return (g-arcs[i][j] ! 0 g-arcs[i][j] ! INF); }這段代碼沒(méi)有循環(huán)、沒(méi)有遞歸就是一次數(shù)組下標(biāo)訪問(wèn)。它之所以快是因?yàn)镃PU知道arcs[i][j]在內(nèi)存里的絕對(duì)地址base_address i * n jn是頂點(diǎn)數(shù)硬件直接算出位置伸手就拿。2.3 它的硬傷在哪——空間和稀疏度的生死局優(yōu)勢(shì)有多亮短板就有多刺眼。鄰接矩陣的空間占用是剛性的O(n2)100個(gè)頂點(diǎn) → 占用10,000個(gè)整數(shù)空間10,000個(gè)頂點(diǎn) → 占用100,000,000個(gè)整數(shù)空間約400MB純數(shù)據(jù)還不算指針、結(jié)構(gòu)體開(kāi)銷但現(xiàn)實(shí)中絕大多數(shù)圖是稀疏圖——邊數(shù)e遠(yuǎn)小于n2。比如一個(gè)含1000個(gè)城市的交通網(wǎng)若平均每個(gè)城市只連3條高速總邊數(shù)才3000而鄰接矩陣卻要塞滿1,000,000個(gè)格子其中99.7%是“沒(méi)路”的占位符INF或0。這就像為一個(gè)只有3戶人家的村子強(qiáng)行修建覆蓋1000平方公里的全光纜網(wǎng)絡(luò)——錢花了維護(hù)難了擴(kuò)容還卡在物理路由上。注意代碼中DispMat()函數(shù)打印時(shí)用---代替INF正是為了讓人眼直觀識(shí)別“無(wú)效邊”。這個(gè)細(xì)節(jié)暴露了鄰接矩陣的底層焦慮它必須用特殊標(biāo)記填滿所有空格否則無(wú)法維持“方格紙”的完整性。3. 鄰接表給每個(gè)頂點(diǎn)發(fā)一本專屬通訊錄只記真有聯(lián)系的人3.1 它長(zhǎng)什么樣——數(shù)組鏈表的混合雙打如果說(shuō)鄰接矩陣是“全局統(tǒng)一分配的網(wǎng)格本”鄰接表就是“每人一本活頁(yè)通訊錄”。它的結(jié)構(gòu)分兩層頂層是頂點(diǎn)數(shù)組vertices[n]大小等于頂點(diǎn)數(shù)n每個(gè)元素是一個(gè)VNode結(jié)構(gòu)體存頂點(diǎn)自身信息如名稱、ID和一個(gè)關(guān)鍵指針firstarc底層是邊鏈表每個(gè)VNode的firstarc指向一條單向鏈表鏈表節(jié)點(diǎn)ArcNode里只存兩樣?xùn)|西adjvex這條邊指向的鄰居頂點(diǎn)編號(hào)、info邊權(quán)如距離/費(fèi)用以及nextarc指向下一條邊。// 鄰接表核心結(jié)構(gòu)體精簡(jiǎn)版 typedef struct ArcNode { // 邊節(jié)點(diǎn)記錄“我連誰(shuí)”和“代價(jià)多少” int adjvex; // 鄰接點(diǎn)下標(biāo)比如指向頂點(diǎn)3 int info; // 邊的信息權(quán)重、類型等 struct ArcNode *nextarc; // 指向下一個(gè)鄰接點(diǎn) } ArcNode; typedef struct VNode { // 頂點(diǎn)節(jié)點(diǎn)記錄“我是誰(shuí)”和“我的通訊錄在哪” VertexType data; // 頂點(diǎn)數(shù)據(jù)如城市名北京 ArcNode *firstarc; // 指向第一條邊的指針通訊錄首頁(yè) } VNode; typedef struct { // 整張圖頂點(diǎn)數(shù)組 元信息 AdjList vertices; // 頂點(diǎn)數(shù)組n本通訊錄 int vexnum, arcnum; // 頂點(diǎn)數(shù)、邊數(shù) } ALGraph;這個(gè)設(shè)計(jì)的精妙在于空間隨實(shí)際邊數(shù)線性增長(zhǎng)O(ne)。1000個(gè)城市、3000條高速頂點(diǎn)數(shù)組占1000個(gè)槽位邊節(jié)點(diǎn)鏈表共3000個(gè)節(jié)點(diǎn)總空間≈4000個(gè)結(jié)構(gòu)體比鄰接矩陣省99%以上。3.2 它最擅長(zhǎng)什么——遍歷鄰居和增刪邊的靈活身段鄰接表的優(yōu)勢(shì)源于它“按需分配、動(dòng)態(tài)鏈接”的基因遍歷某頂點(diǎn)的所有鄰接點(diǎn)O(degree(v))問(wèn)“北京能直達(dá)哪些城市”——順著vertices[0].firstarc的鏈表一路往下讀讀到nextarc NULL為止。時(shí)間只和北京連出的邊數(shù)度數(shù)有關(guān)與全圖規(guī)模無(wú)關(guān)。插入/刪除一條邊O(1)均攤給北京新增一條到雄安的高速只需malloc一個(gè)新ArcNode填好adjvex雄安編號(hào)、info距離然后把它插到vertices[北京編號(hào)].firstarc鏈表頭部頭插法。刪除同理找到目標(biāo)節(jié)點(diǎn)前驅(qū)修改指針即可。節(jié)省內(nèi)存對(duì)稀疏圖近乎完美沒(méi)有冗余格子每字節(jié)都存有效信息。調(diào)試時(shí)打印DispAdj()看到的是一行行清晰的“0: 3 5”0號(hào)點(diǎn)連向3、5號(hào)點(diǎn)而不是滿屏的0 0 0 7 0 0。// 示例向頂點(diǎn)i添加一條指向j的邊鄰接表核心操作 void AddEdge(ALGraph *G, int i, int j, int weight) { ArcNode *p (ArcNode*)malloc(sizeof(ArcNode)); p-adjvex j; p-info weight; p-nextarc G-vertices[i].firstarc; // 頭插法新節(jié)點(diǎn)成為首節(jié)點(diǎn) G-vertices[i].firstarc p; }這段代碼里p-nextarc G-vertices[i].firstarc和G-vertices[i].firstarc p的順序不能顛倒否則會(huì)丟失原鏈表。這是鄰接表操作的經(jīng)典“斷鏈-重連”手法也是初學(xué)者最容易翻車的血淚經(jīng)驗(yàn)點(diǎn)。3.3 它的軟肋在哪——查邊存在性成了“大海撈針”鄰接表的靈活性是以犧牲隨機(jī)訪問(wèn)為代價(jià)的。最痛的短板就是查任意兩點(diǎn)間是否有邊平均要O(degree(i))時(shí)間。問(wèn)“北京和上海之間有直達(dá)高鐵嗎”——得翻開(kāi)北京的通訊錄vertices[0].firstarc從第一頁(yè)開(kāi)始逐條比對(duì)adjvex直到找到adjvex上海編號(hào)或翻到末頁(yè)nextarc NULL。如果北京連了200個(gè)城市就得比對(duì)最多200次如果圖是星型結(jié)構(gòu)一個(gè)中心點(diǎn)連所有其他點(diǎn)查中心點(diǎn)到任一葉節(jié)點(diǎn)是O(1)但查兩個(gè)葉節(jié)點(diǎn)之間答案永遠(yuǎn)是“沒(méi)有”可你得把中心點(diǎn)的200頁(yè)通訊錄全翻完才能確認(rèn)。這就是為什么鄰接表不適合做“全局關(guān)系快查”。它像一個(gè)高效的快遞分揀站知道某個(gè)包裹該發(fā)往哪遍歷鄰居快但若問(wèn)“A倉(cāng)和B倉(cāng)之間能否直送”得先查A倉(cāng)的發(fā)貨單、再查B倉(cāng)的收貨單效率遠(yuǎn)不如一張全局航線圖鄰接矩陣上直接看交叉點(diǎn)。4. 鄰接矩陣 vs 鄰接表五種常見(jiàn)誤區(qū)專治“我以為它們差不多”4.1 誤區(qū)一鄰接表一定比鄰接矩陣“高級(jí)”或“現(xiàn)代”為什么混教程常強(qiáng)調(diào)鄰接表“節(jié)省空間”學(xué)生誤以為“新好”寫作業(yè)時(shí)盲目選鄰接表。怎么區(qū)分高級(jí)與否取決于場(chǎng)景。在稠密圖如棋盤上所有格子互連的圖e ≈ n2中鄰接矩陣的O(1)查邊能力碾壓鄰接表的O(n)遍歷且矩陣支持矩陣運(yùn)算如求路徑數(shù)A2的i,j元素表示長(zhǎng)度為2的路徑數(shù)鄰接表無(wú)法直接實(shí)現(xiàn)。選型不是比新舊而是比“你的圖更常被怎么問(wèn)問(wèn)題”。4.2 誤區(qū)二鄰接矩陣只能存有向圖鄰接表才能存無(wú)向圖為什么混看到鄰接矩陣代碼里arcs[i][j]和arcs[j][i]值不同有向就認(rèn)為它“不支持”無(wú)向。怎么區(qū)分無(wú)向圖在鄰接矩陣中體現(xiàn)為對(duì)稱矩陣——只要arcs[i][j] arcs[j][i]如都填1或都填權(quán)重它就是合法的無(wú)向圖存儲(chǔ)。鄰接表存無(wú)向圖則需雙向建邊i的鏈表加jj的鏈表加i。兩者都能存只是無(wú)向圖下鄰接矩陣天然對(duì)稱鄰接表需手動(dòng)保證雙向性。4.3 誤區(qū)三鄰接表的“鏈表”必須用指針不能用數(shù)組模擬為什么混教材代碼用malloc和struct ArcNode*學(xué)生以為“鏈表動(dòng)態(tài)內(nèi)存必須指針”。怎么區(qū)分完全可以用靜態(tài)鏈表數(shù)組游標(biāo)實(shí)現(xiàn)鄰接表例如定義ArcNode edgePool[MAX_ARC_NUM]和int head[MAX_VERTEX_NUM]存每個(gè)頂點(diǎn)鏈表頭節(jié)點(diǎn)下標(biāo)用edgePool[i].next代替指針。這樣避免頻繁malloc/free適合嵌入式或?qū)崟r(shí)系統(tǒng)。指針只是最直觀的實(shí)現(xiàn)方式不是本質(zhì)約束。4.4 誤區(qū)四轉(zhuǎn)換程序MatToList / ListToMat只是“格式搬運(yùn)”沒(méi)有業(yè)務(wù)價(jià)值為什么混實(shí)驗(yàn)要求“寫兩個(gè)轉(zhuǎn)換函數(shù)”學(xué)生當(dāng)成機(jī)械編碼任務(wù)忽略其工程意義。怎么區(qū)分真實(shí)系統(tǒng)中數(shù)據(jù)源常是異構(gòu)的——GIS系統(tǒng)導(dǎo)出的可能是鄰接矩陣CSV而算法庫(kù)要求鄰接表輸入。轉(zhuǎn)換函數(shù)就是數(shù)據(jù)管道的適配器。更關(guān)鍵的是MatToList中的for(jn-1;j0;j--)是逆序遍歷代碼注釋為“頭插法”這決定了鏈表中邊的順序影響DFS/BFS遍歷起點(diǎn)選擇。轉(zhuǎn)換不是復(fù)制是重構(gòu)關(guān)系表達(dá)。4.5 誤區(qū)五鄰接矩陣的INF32767可以隨便改成其他大數(shù)不影響邏輯為什么混看到#define INF 32767覺(jué)得“反正很大就行”改成999999或0x3f3f3f3f。怎么區(qū)分INF是“無(wú)窮大”的語(yǔ)義占位符用于初始化和比較。若后續(xù)算法涉及min(dist[i], dist[k]weight)INF必須滿足INF weight INF數(shù)學(xué)上無(wú)窮大有限數(shù)無(wú)窮大。32767是16位有符號(hào)整數(shù)最大值32767 1會(huì)溢出成負(fù)數(shù)破壞語(yǔ)義正確做法是用足夠大的數(shù)如INT_MAX/2或?qū)ｉT的布爾標(biāo)志位。代碼中if(g-arcs[i][j]INF)的判斷一旦INF溢出邏輯就崩了。5. 什么時(shí)候用鄰接矩陣什么時(shí)候用鄰接表——一張決策表和三個(gè)真實(shí)場(chǎng)景5.1 核心決策表看圖的“密度”和你的“高頻操作”判斷維度優(yōu)先選鄰接矩陣優(yōu)先選鄰接表圖的邊數(shù) e 與頂點(diǎn)數(shù) n 關(guān)系e 接近 n2稠密圖如社交網(wǎng)絡(luò)全連接子圖、小規(guī)模全連通圖e 遠(yuǎn)小于 n2稀疏圖如互聯(lián)網(wǎng)網(wǎng)頁(yè)鏈接、大規(guī)模交通網(wǎng)、電路布線最常做的操作頻繁查詢?nèi)我鈨牲c(diǎn)間是否有邊/邊權(quán)如Floyd最短路徑、連通性批量檢測(cè)頻繁遍歷某點(diǎn)所有鄰居如BFS/DFS搜索、PageRank迭代、推薦系統(tǒng)協(xié)同過(guò)濾內(nèi)存是否敏感內(nèi)存充足或圖規(guī)模小n1000內(nèi)存受限或圖規(guī)模大n10000且 e/n 10平均度數(shù)低是否需要矩陣運(yùn)算需要計(jì)算 A2、A3路徑數(shù)、特征值圖譜理論不涉及線性代數(shù)運(yùn)算純圖遍歷邏輯這張表不是教條而是幫你把模糊感覺(jué)“好像該用鄰接表”轉(zhuǎn)化成可驗(yàn)證的條件。比如面試官問(wèn)“10億用戶的關(guān)系圖怎么存”——先算密度微信好友平均300人e ≈ 10? × 300 3×1011n2 101?e/n2 3×10??是極致稀疏圖再看操作推薦系統(tǒng)要查“用戶A的好友的好友”本質(zhì)是兩層鄰居遍歷。結(jié)論鄰接表甚至要升級(jí)為鄰接多重表或圖數(shù)據(jù)庫(kù)。5.2 場(chǎng)景一校園網(wǎng)拓?fù)浔O(jiān)控——鄰接矩陣的“閃電響應(yīng)”時(shí)刻某高校有200臺(tái)核心交換機(jī)n200任意兩臺(tái)間都有光纖直連e ≈ 200240000稠密圖。運(yùn)維系統(tǒng)需每秒檢測(cè)“交換機(jī)A和B是否鏈路中斷”。若用鄰接表每次查詢都要遍歷A的200條鏈路找B的編號(hào)平均100次比較200臺(tái)×200查詢40000次/秒CPU狂轉(zhuǎn)。若用鄰接矩陣arcs[A][B] 0 ? 斷 : 通一次內(nèi)存讀取200×20040000次查詢?cè)诩{秒級(jí)完成。這里鄰接矩陣的O(1)查邊是保障SLA服務(wù)等級(jí)協(xié)議的生命線。實(shí)驗(yàn)代碼中DispMat()打印的整齊方陣正是運(yùn)維大屏上實(shí)時(shí)閃爍的鏈路狀態(tài)圖。5.3 場(chǎng)景二短視頻推薦引擎——鄰接表的“關(guān)系挖掘”主場(chǎng)某平臺(tái)有5億用戶n5×10?平均每人關(guān)注200人e ≈ 1011稀疏圖。推薦算法需執(zhí)行對(duì)用戶A找出其關(guān)注者B再找出B關(guān)注的C計(jì)算A-C的相似度。鄰接矩陣內(nèi)存需求 (5×10?)2 × 4字節(jié) ≈ 101? 字節(jié)10億TB宇宙中沒(méi)有服務(wù)器能裝下。鄰接表A的鏈表200個(gè)節(jié)點(diǎn)B的鏈表200個(gè)節(jié)點(diǎn)兩次鏈表遍歷總操作數(shù)≈200×20040000毫秒級(jí)完成。鄰接表在此不是“夠用”而是“唯一可行”。實(shí)驗(yàn)中MatToList()的頭插法看似微小實(shí)則決定了“最近關(guān)注的用戶排在鏈表前面”讓推薦優(yōu)先考慮時(shí)效性高的關(guān)系——這是業(yè)務(wù)邏輯對(duì)數(shù)據(jù)結(jié)構(gòu)的反向塑造。5.4 場(chǎng)景三編譯器符號(hào)表管理——混合策略的生存智慧某C語(yǔ)言編譯器需管理函數(shù)調(diào)用關(guān)系。項(xiàng)目有10000個(gè)函數(shù)n10?但平均每個(gè)函數(shù)只調(diào)用5個(gè)其他函數(shù)e5×10?稀疏圖。然而編譯器最常做的操作是快速判斷func_A是否直接調(diào)用func_B查邊同時(shí)要列出func_A調(diào)用的所有函數(shù)遍歷鄰居。純鄰接矩陣空間10?整數(shù)400MB查邊O(1)但遍歷需掃10?列純鄰接表空間≈1.5×10?節(jié)點(diǎn)遍歷O(5)但查邊平均O(2.5)。最優(yōu)解是“鄰接矩陣鄰接表”混合用鄰接表存調(diào)用關(guān)系主結(jié)構(gòu)再用一個(gè)10?×10?的布爾矩陣僅1bit/格總空間12.5MB緩存查邊結(jié)果?？臻g增加不多卻把高頻查邊從O(5)降到O(1)。這印證了實(shí)驗(yàn)資源的價(jià)值MatToList和ListToMat不是孤立函數(shù)而是讓你理解結(jié)構(gòu)可轉(zhuǎn)換、能力可組合——真正的工程高手從不迷信單一結(jié)構(gòu)。從那以后我每次設(shè)計(jì)圖結(jié)構(gòu)都強(qiáng)制走一遍這個(gè)流程先手算圖的e/n2密度比再列出未來(lái)三個(gè)月最可能被調(diào)用的3個(gè)API查邊遍歷改權(quán)最后對(duì)照決策表圈出候選方案。哪怕最終選了鄰接表也會(huì)在備注里寫清“因查邊操作將由緩存層承擔(dān)故此處鄰接表不構(gòu)成性能瓶頸”。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取