熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之鄰接表表示法

2013-11-15 15:36:44  來源: 數據結構 

鄰接表的表示方法

  鄰接表(Adjacency List)是圖的一種鏈式存儲結構在鄰接表中對圖中每個頂點建立一個單鏈表第i個單鏈表中的結點表示依附於頂點vi的邊(對有向圖是以頂點vi為尾的弧)
  鄰接表由兩部分構成表頭結頭表結點組成的單鏈表


  鄰接表的表示意義為對於圖G=(VE)若(ij)∈E則第i個表頭結點的單鏈表上有一個adjvex為j的表結頭


  無向圖的鄰接表稱為邊表有向圖的鄰接表稱為出邊表鄰接表的表頭向量稱為頂點表
  逆鄰接表在有向圖中對每個頂點vi建立一個鏈接以vi為頭的弧表
  逆鄰接表在形式上由兩部分構成表頭結點表結點組成的單鏈表表頭結點與鄰接表完全一樣但表結點組成的單鏈表是不同的
  逆鄰接表的表示意義為對於圖G=(VE)若<ij>∈E則第j個表頭結點的單鏈表上有一個adjvex為i的表結頭 

 
  一個圖的鄰接矩陣表示是唯一的而鄰接表表示則不是唯一的
  稀疏圖(Sparse graph)有很少條邊或弧(如e<nlogn)的圖
  稠密圖(Dense graph)邊很多的圖
  相比之下從存儲空間角度看鄰接表更適合於表示稀疏圖而鄰接矩陣適合於表示稠密圖
 
鄰接表的C語言描述

  鄰接表形式說明



From:http://tw.wingwit.com/Article/program/sjjg/201311/23684.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.