目錄

• 一、圖的定義和基本術(shù)語(yǔ)(Graph)
• • （一）圖的定義
  • （二）圖的基本術(shù)語(yǔ)
• 一、圖的存儲(chǔ)結(jié)構(gòu)
• • （一）鄰接矩陣（Adjacency Matrix)
  • • 1、無(wú)向圖的鄰接矩陣
    • 2、有向圖的鄰接矩陣
    • 3、網(wǎng)（即有權(quán)圖）的鄰接矩陣
    • 4、鄰接矩陣的存儲(chǔ)表示
    • 5、采用鄰接矩陣表示法創(chuàng)建無(wú)向網(wǎng)
  • （二）鄰接表（鏈?zhǔn)?#xff09;表示法(Adjacency List）
  • • 1、無(wú)向圖的鄰接表表示
    • 2、有向圖的鄰接表表示
    • 3、圖的鄰接表的存儲(chǔ)定義
    • 4、采用鄰接表表示法創(chuàng)建無(wú)向圖
    • 5、鄰接矩陣與鄰接表的比較
  • （三）十字鏈表(Orthogonal List)
  • • 1、弧結(jié)點(diǎn)的結(jié)構(gòu)
    • 2、頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)
    • 3、圖的結(jié)構(gòu)定義
    • 4、實(shí)例
    • 5、有向圖G的十字鏈表
  • （四）鄰接多重表(Adjacent MultiList)
  • • 1、邊結(jié)點(diǎn)的結(jié)構(gòu)
    • 2、頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)
    • 3、圖的結(jié)構(gòu)定義
    • 4、實(shí)例
    • 4、練習(xí)：畫(huà)出無(wú)向圖G的鄰接多重表

一、圖的定義和基本術(shù)語(yǔ)(Graph)

（一）圖的定義

圖（Graph)是由一個(gè)頂點(diǎn)集V和一個(gè)邊集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。
G=(V,E)
V:頂點(diǎn)（數(shù)據(jù)元素）的又窮非空集合
E:邊的又窮集合
無(wú)向圖：每條邊都是沒(méi)有方向的
有向圖：每條邊都是有方向的，邊也稱(chēng)作弧

（二）圖的基本術(shù)語(yǔ)

設(shè)n表示圖中頂點(diǎn)的數(shù)目，e表示邊的數(shù)目
完全圖：任意兩個(gè)點(diǎn)都有一條邊相連

稀疏圖：如果邊或者弧的個(gè)數(shù)滿(mǎn)足e<n*log2n,則稱(chēng)作稀疏圖，否則稱(chēng)作稠密圖

對(duì)無(wú)向圖來(lái)說(shuō)：
鄰接點(diǎn)：若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊a,則稱(chēng)頂點(diǎn)v和w互為鄰接點(diǎn)。邊a與頂點(diǎn)v和w相關(guān)聯(lián)。
度：與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目，記為T(mén)D(v)

對(duì)有向圖來(lái)說(shuō)：
1、<x,y>為有向邊（弧），x為有向邊的起點(diǎn)（弧尾），y為有向邊的終點(diǎn)（弧頭）
2、頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù)，記作ID(v)
3、頂點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù)，記作OD(v)

路徑：連續(xù)的邊構(gòu)成的頂點(diǎn)序列
路徑長(zhǎng)度：路徑上邊或者弧的數(shù)目
簡(jiǎn)單路徑：除路徑起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同的路徑
簡(jiǎn)單回路（簡(jiǎn)單環(huán)）：除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的路徑。

一、圖的存儲(chǔ)結(jié)構(gòu)

圖的存儲(chǔ)表示特點(diǎn)：
1、圖沒(méi)有順序存儲(chǔ)結(jié)構(gòu)，但可以借助二維數(shù)組來(lái)表示圖的元素之間的關(guān)系
2、以頂點(diǎn)為核心，建立鄰接點(diǎn)和弧的關(guān)系；

（一）鄰接矩陣（Adjacency Matrix)

1、考慮到圖是由兩個(gè)頂點(diǎn)和邊或弧兩部分組成，合在一起比較困難，可以分為兩個(gè)結(jié)構(gòu)來(lái)存儲(chǔ)
2、頂點(diǎn)因?yàn)椴粎^(qū)分大小，主次，所以可以用一個(gè)一維數(shù)組來(lái)存儲(chǔ)，記錄各個(gè)頂點(diǎn)的信息
3、邊或弧是頂點(diǎn)和頂點(diǎn)的關(guān)系，用鄰接矩陣來(lái)存儲(chǔ)，表示各個(gè)頂點(diǎn)之間的鄰接關(guān)系。

1、無(wú)向圖的鄰接矩陣

2、有向圖的鄰接矩陣

3、網(wǎng)（即有權(quán)圖）的鄰接矩陣

4、鄰接矩陣的存儲(chǔ)表示

/*圖的鄰接矩陣存儲(chǔ)表示法*/ //用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣 #define MaxInt 32767 //表示極大值，即無(wú)窮 #define MVNum 100 //最大頂點(diǎn)數(shù) typedef char VerTexType; //假設(shè)頂點(diǎn)的數(shù)據(jù)類(lèi)型為字符型 typedef int ArcType; //假設(shè)邊的權(quán)值類(lèi)型為整型 typedef struct {VerTexType vexs[MVNum]; //頂點(diǎn)表ArcType arcs[MVNum][MVNum]; //鄰接矩陣int vexnum, arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) }AMGraph;

5、采用鄰接矩陣表示法創(chuàng)建無(wú)向網(wǎng)

【算法步驟】
1、輸入總頂點(diǎn)數(shù)和邊數(shù)
2、依次輸入點(diǎn)的信息存入到頂點(diǎn)表中
3、初始化鄰接矩陣，使每個(gè)權(quán)值初始化為極大值
4、構(gòu)造鄰接矩陣

注意：
1、無(wú)向圖需要為arcs[i][j]和arcs[j][i]賦值
2、有向圖僅需為arcs[i][j]賦值

算法描述：

/*采用鄰接矩陣表示法創(chuàng)建無(wú)向網(wǎng)*/ Status CreateUDN(AMGraph& G) {cin >> G.vexnum >> G.arcnum;//輸入總頂點(diǎn)數(shù)和總邊數(shù)for (int i = 0;i < G.vexnum;++i)cin >> G.vexs[i];//依次輸入頂點(diǎn)的信息for (int i = 0;i < G.vexnum;++i)//初始化鄰接矩陣，邊的權(quán)值均置為極大值for (int j = 0;j < G.vexnum;++j)G.arcs[i][j] = MaxInt;for (int k = 0;k < G.arcnum;++k){cin >> v1 >> v2 >> w;//輸入一條邊依附的頂點(diǎn)和權(quán)值i = LocateVex(G, v1);j = LocateVex(G, v2);//確定兩個(gè)頂點(diǎn)v1和v2在G中的位置G.arcs[i][j] = w;//邊<v1,v2>的權(quán)值置為wG.arcs[j][i] = G.arcs[i][j];//置邊<v1,v2>的對(duì)稱(chēng)點(diǎn)<v2,v1>的權(quán)值也為w}return OK; } /*在圖中查找頂點(diǎn)的位置LocateVex()函數(shù)*/ int LocateVex(AMGraph G, VertexType u) {//若在圖中找到這個(gè)元素，則返回它的下標(biāo)i,否則返回-1int i;for (i = 0;i < G.vexnum;++i)if (u == G.vexs[i])return i;return -1; }

（二）鄰接表（鏈?zhǔn)?#xff09;表示法(Adjacency List）

是圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，基本思想就是只存儲(chǔ)圖中存在的邊的信息，對(duì)不相鄰的頂點(diǎn)則不保留信息
對(duì)圖中每個(gè)頂點(diǎn)vi建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，把與vi相鄰接的頂點(diǎn)放在這個(gè)鏈表中，一個(gè)單鏈表對(duì)應(yīng)鄰接矩陣中的一行，稱(chēng)為邊鏈表。

1、無(wú)向圖的鄰接表表示

2、有向圖的鄰接表表示

3、圖的鄰接表的存儲(chǔ)定義

分三部分：
1、圖的結(jié)構(gòu)定義
2、頂點(diǎn)的頭結(jié)點(diǎn)結(jié)構(gòu)
3、弧（邊）的結(jié)點(diǎn)結(jié)構(gòu)

/*圖的鄰接表的存儲(chǔ)定義*/ //弧的結(jié)點(diǎn)結(jié)構(gòu) #define MVNum 100 //最大的頂點(diǎn)數(shù) typedef struct ArcNode {int adjvex; //該邊所指的頂點(diǎn)的位置struct ArcNode* nextarc; //指向下一條邊的指針OtherInfo info; //和邊相關(guān)的信息 }ArcNode; //頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu) typedef struct VNode {VertexType data;//頂點(diǎn)信息ArcNode* firstarc;//指向第一條依附該頂點(diǎn)的邊 }VNode,AdjList[MVNum];//AdjList表示鄰接表類(lèi)型 //AdjList v相當(dāng)于VNode v[MVNum]//圖的結(jié)構(gòu)定義（鄰接表） typedef struct {AdjList vertices;//vertices是vertex的復(fù)數(shù)int vexnum, arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) }ALGraph;/*說(shuō)明*/ ALGraph G;//定義了鄰接表表示的圖G G.vexnum = 5;G.arcnum = 6;//圖G包含了5個(gè)頂點(diǎn)和6條邊 G.vertices[1].data = 'v2';//圖G中第2個(gè)頂點(diǎn)是v2 p = G.vertices[1].firstarc;//指針p指向頂點(diǎn)v2的第一個(gè)邊結(jié)點(diǎn) p->adjvex = 4;//p指針?biāo)高吔Y(jié)點(diǎn)是到下標(biāo)為4的結(jié)點(diǎn)的邊

4、采用鄰接表表示法創(chuàng)建無(wú)向圖

【算法步驟】
1、輸入總頂點(diǎn)數(shù)和總邊數(shù)
2、建立頂點(diǎn)表

1、依次輸入點(diǎn)的信息存入頂點(diǎn)表中
2、使每個(gè)表頭結(jié)點(diǎn)的指針域初始化為NULL

3、創(chuàng)建鄰接表

1、依次輸入每條邊依附的兩個(gè)頂點(diǎn)
2、確定這兩個(gè)頂點(diǎn)的序號(hào)i和j
3、將此邊結(jié)點(diǎn)分別插入vi和vj對(duì)應(yīng)的兩個(gè)邊鏈表的頭部

/*采用鄰接表表示法創(chuàng)建無(wú)向圖*/ Status CreateUDG(ALGraph& G) {//采用鄰接表表示法，創(chuàng)建無(wú)向圖Gcin >> G.vexnum >> G.arcnum;//輸入頂點(diǎn)數(shù)和弧數(shù)for (int i = 0;i < G.vexnum;++i){cin >> G.vertices[i].data;//輸入頂點(diǎn)值G.vertices[i].firstarc = NULL;//初始化表頭結(jié)點(diǎn)的指針域?yàn)镹ULL}for (int k = 0;k < G.arcnum;++k)//輸入各邊，構(gòu)造鄰接表，頭插法{cin >> v1 >> v2;//輸入一條邊依附的兩個(gè)頂點(diǎn)i = LocateVex(G, v1);j = LocateVex(G.v2);p1 = new ArcNode;//生成一個(gè)新的邊結(jié)點(diǎn)*p1p1->adjvex = j;//鄰結(jié)點(diǎn)序號(hào)為jp1->nextarc = G.vertices[i].firstarc;//firstarc為空，所以nextarc也指向空，即最后的一個(gè)結(jié)點(diǎn)G.vertices[i].firstarc = p1;//將新結(jié)點(diǎn)*p1插入到頂點(diǎn)vi的邊表頭部p2 = new ArcNode;//生成一個(gè)新的邊結(jié)點(diǎn)*p2p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;//插入弧結(jié)點(diǎn)到單鏈表G.vertices[j].firstarc = p2;//將新結(jié)點(diǎn)*p2插入到頂點(diǎn)vi的邊表頭部}//頭插法return OK; }

5、鄰接矩陣與鄰接表的比較

練習(xí)：畫(huà)出有向圖G的鄰接矩陣、鄰接表、逆鄰接表

（三）十字鏈表(Orthogonal List)

十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，可以看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表

1、弧結(jié)點(diǎn)的結(jié)構(gòu)

Tailvex:指示弧尾結(jié)點(diǎn)在圖中的位置
headtex:指示弧頭頂點(diǎn)在圖中的位置
hlink:是指向弧頭相同的下一條弧的指針
tlink：是指向弧尾相同的下一條弧的指針
Info:指向該弧的相關(guān)信息

/*弧結(jié)點(diǎn)的結(jié)構(gòu)*/ typedef struct ArcBox {int tailvex, headvex;//該弧的尾和頭頂點(diǎn)的位置struct ArcBox* hlink, * tlink;//分別為弧頭相同和弧尾相同的弧的指針域InfoType* info;//該弧相關(guān)信息的指針 }ArcBox;

2、頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)

每個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)，它相當(dāng)于出邊表和入邊表的表頭結(jié)點(diǎn)。數(shù)據(jù)成員data存放與該頂點(diǎn)的相關(guān)信息。鏈域firstin指示以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)。鏈域firstout指示以該結(jié)點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)。

/*頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)*/ typedef struct VexNode {VertexType data;ArcBox* firstin, * firstout;//分別指向該頂點(diǎn)第一條入弧和出弧 }VexNode; //ArcBox為弧結(jié)點(diǎn)變量

3、圖的結(jié)構(gòu)定義

/*圖的結(jié)構(gòu)定義*/ typedef struct {VexNode xlist[MAX_VERTEX_NUM];//表頭向量int vexnum, arcnum;//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) }OLGraph;

4、實(shí)例

5、有向圖G的十字鏈表

（四）鄰接多重表(Adjacent MultiList)

鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，由于用鄰接表存儲(chǔ)無(wú)向圖時(shí)，雖然容易求出頂點(diǎn)和邊的各種信息，但在鄰接表中每一條邊有兩個(gè)結(jié)點(diǎn)，分別在第i和j個(gè)鏈表中，給圖的某些操作帶來(lái)不便，在鄰接多重表中，每一條邊只有一個(gè)邊結(jié)點(diǎn)，為有關(guān)的處理提供了方便。

1、邊結(jié)點(diǎn)的結(jié)構(gòu)

mark：為標(biāo)志域，可用以標(biāo)記該條邊是否被搜索過(guò)
ivex和jvex為該邊依附的兩個(gè)頂點(diǎn)在圖中的位置
ilink:指向下一條依附于頂點(diǎn)的ivex的邊
jlink:指向下一條依附于頂點(diǎn)jvex的邊
info:為指向和邊相關(guān)的各種信息個(gè)指針域

/*邊結(jié)點(diǎn)結(jié)構(gòu)*/ typedef struct EBox {VisitIf mark;//訪(fǎng)問(wèn)標(biāo)志域int ivex, jvex;//該邊依附的兩個(gè)頂點(diǎn)在表頭數(shù)組中的位置struct Ebox* ilink, * jlink;//分別指向依附于ivex和jvex的下一條邊InfoType* info; }EBox;

2、頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)

/*頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)*/ typedef struct VexBox {VertexType data;//存與頂點(diǎn)相關(guān)的信息EBox* firstedge;//指向第一條依附于該頂點(diǎn)的邊 }VexBox;

3、圖的結(jié)構(gòu)定義

/*圖的結(jié)構(gòu)定義*/ typedef struct {VexBox adjmulist[MAX_VERTEX_NUM];//表頭向量int vexnum, edgenum;//無(wú)向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) }OLGraph; //VexNode為頂點(diǎn)結(jié)點(diǎn)變量

4、實(shí)例

4、練習(xí)：畫(huà)出無(wú)向圖G的鄰接多重表

總結(jié)

以上是生活随笔為你收集整理的【数据结构——图和图的存储结构】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。