數(shù)據(jù)結構學習小記3（圖2之圖的存儲結構）
由于圖的結構比較復雜，任意兩個頂點都可能存在聯(lián)系，因此圖沒有順序存儲結構，但可以借助二維數(shù)組即鄰接矩陣表示法來表示元素之間的關系，自然也有用鏈式存儲表示圖，圖的鏈式存儲有多種，有鄰接表，十字鏈表和鄰接多重表，應根據(jù)實際需要的不同選擇不同的存儲結構。
鄰接矩陣?
//圖的鄰接矩陣存儲表示
#define MaxInt 32767? ? ?//表示極大值，即∞ （基本整型變量數(shù)據(jù)范圍是-32768～32767）
#define MVNum 100????????//最大頂點數(shù)
typedef char VerTexType;? //假設頂點的數(shù)據(jù)類型為字符型
typedef int ArcType;? ? ? ?//假設邊的權值類型為整型
typedef struct?
{
VetTexType vexs[MvNum];//頂點表
ArcType arcs[MvNum][MvNum];//鄰接矩陣
int vexnum,arcnum;? ?//圖的當前點數(shù)和邊數(shù)
}AMGraph;
采用鄰接矩陣表示法創(chuàng)建無向網(wǎng)（帶權的圖）
Status CreateUDN(AMGraph &G)
{
cin>>G.vexnum>>G.arcnum;//輸入總頂點數(shù)和總邊數(shù)
for(i=0;i<G.vexnum;++i)
????cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)
????for(j=0;j<G.vexnum;++j)
? ??????G.arcs[i][j]=MaxInt;//給每一條邊賦予最大權值，若要建立無向圖，則將權值均初始化為0
for(k=0;k<G.arcnum;++k)//構造鄰接矩陣
{
cin>>v1>>v2>>w;//輸入一條邊依附的頂點以及權值
i=LocateVex(G,v1);j=LocateVex(G,v2);//LocateVex函數(shù)為獲取v1,v2頂點數(shù)組下標的函數(shù)
G.arcs[i][j]=w;//邊<v1,v2>的權值置為w，若要建立無向圖，將權值改為常量1即可
G.arcs[j][i]=G.arcs[i][j];//將邊<v1,v2>的對稱邊的權值置為w
}
return OK;
}?
【算法分析】
（1）時間復雜度：O(n的平方）
（2）空間復雜度高。如果是有向圖，n個頂點需要n平方個單元存儲邊，如果是無向圖，因其鄰接矩陣是對稱的，所以對規(guī)模較大的鄰接矩陣可以采用僅存儲下三角或上三角的元素，需要n(n-1)/2個單元即可。無論以那種方式，這種表示法的空間復雜度都為O(n的平方），這對于稀疏圖而言浪費空間。
//圖的鄰接表表示
#define MVNum 100????//最大頂點數(shù)
typedef struct ArcNode????//邊結點
{
int adjvex;//該邊所指向的頂點的位置
struct ArcNode *nextarc;//指向下一條邊的指針
OtherInfo info;//和邊相關的其他信息,將邊的權值存儲在其中，即可創(chuàng)建網(wǎng)
}ArcNode;
typedef struct VNode? //頂點信息
{
VerTexType data;
ArcNode *firstarc;? //指向第一條依附該頂點的邊的指針
}VNode,AdjList[MVNum];? //AdjList表示鄰接表類型
typedef struct
{
AdjList vertice;
int vexnum,arcnum; //圖的當前頂點數(shù)和邊數(shù)
}ALGraph;
采用鄰接表表示法創(chuàng)建無向圖
Status CreateUDG(ALGraph &G)
{
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;++i)
{
cin>>G.vertices[i].data;? //輸入頂點值
G.vertices[i].firstarc=NULL;//初始化表頭結點的指針域為NULL
}
for(k=0;k<G.arcnum;++k)//輸入各邊建立鄰接表
{
cin>>v1>>v2;
i=LocateVex(G,v1);j=LocateVex(G,v2);
p1=new ArcNode;//生成一個新的邊結點*p1
p1->adjvex=j;//鄰接點序號為j
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1;
//將新結點插入頂點vi的邊表頭部（類似于鏈表的插入，先連后繼再連前驅）
p2=new ArcNode;
p2->adjvex=i;
//鄰接點序號為i，若是建立有向圖則只需要建立前面一個序號為j的表結點即可，后面不用建立序號為i的邊表結點
p2->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p2;
}
return OK;
}
【算法分析】
算法的時間復雜度為：O(n+e)
空間復雜度：O(n+e),適合稀疏圖
對于無向圖，其鄰接表表示有n個頂點表結點，2e個邊表結點；對于有向圖，則它的鄰接表與逆鄰接表表示有n個頂點表結點，e個邊表結點。
優(yōu)缺點對比：
鄰接矩陣表示的優(yōu)點：
（1）便于判斷兩個頂點是否有邊
（2）便于計算各個頂點的度
缺點：
（1）不利于增刪結點
（2）不便于統(tǒng)計邊的數(shù)目
鄰接表表示的缺點：
（1）不便于判斷兩個頂點是否有邊
（2）不便于計算各個頂點的度
優(yōu)點：
（1）利于增刪結點
（2）便于統(tǒng)計邊的數(shù)目
