介紹

鄰接矩陣是運(yùn)用較多的一種儲(chǔ)存圖的方法，但如果一張網(wǎng)圖邊數(shù)較少，就會(huì)出現(xiàn)二維矩陣中大部分?jǐn)?shù)據(jù)為0的情況，浪費(fèi)儲(chǔ)存空間

為了避免空間浪費(fèi)，也可以采用數(shù)組與鏈表結(jié)合的方式來(lái)存儲(chǔ)圖

假設(shè)有這樣一張圖

我們可以先用一個(gè)數(shù)組來(lái)存儲(chǔ)頂點(diǎn)；

在每個(gè)頂點(diǎn)后面，可以采用鏈?zhǔn)浇Y(jié)構(gòu)，來(lái)記錄每個(gè)頂點(diǎn)與那些頂點(diǎn)相連，就好比一個(gè)車(chē)頭后面跟著幾節(jié)代表信息的車(chē)廂

如v1這個(gè)頂點(diǎn)，就可以采用如圖的結(jié)構(gòu)記錄連接信息

? ?這種存儲(chǔ)了一個(gè)網(wǎng)圖信息的鏈表集合就稱(chēng)為鄰接鏈表

創(chuàng)建

結(jié)構(gòu)體定義如下

#define MAX 100
//“車(chē)廂”部分
typedef struct edge{int adjvex;//鄰接點(diǎn)域，用于儲(chǔ)存該頂點(diǎn)對(duì)應(yīng)下標(biāo)int info;//儲(chǔ)存權(quán)值struct edge* next;//鏈域，指向下一個(gè)鄰接點(diǎn)
}edge;
//“車(chē)頭”部分
typedef struct vex{char v;//儲(chǔ)存頂點(diǎn)edge* first;//邊表頭指針
}vex,adjlist[MAX];
//儲(chǔ)存鄰接鏈表構(gòu)成的網(wǎng)圖信息
typedef struct{adjlist al;//頂點(diǎn)int numE,numN;//頂點(diǎn)數(shù)，邊數(shù)
}graphAL;

鄰接鏈表的創(chuàng)建

void creat(graphAL* g,int n,int e){//傳入鄰接鏈表，頂點(diǎn)數(shù)與邊數(shù)g->numE=e;g->numN=n;for (int i=0;i<n;i++){cin>>g->al[i].v;//傳入頂點(diǎn)g->al[i].first=NULL;//每一個(gè)頂點(diǎn)的邊表初始化為空}for (int i=0;i<e;i++){//建立邊表int v1,v2;cin>>v1>>v2;//頭插法進(jìn)行插入edge* temp1=(edge*)malloc(sizeof(edge));temp1->adjvex=v2;temp1->next=g->al[v1].first;g->al[v1].first=temp1;//無(wú)向網(wǎng)圖需要兩個(gè)頂點(diǎn)都記錄連接信息edge* temp2=(edge*)malloc(sizeof(edge));temp2->adjvex=v1;temp2->next=g->al[v2].first;g->al[v2].first=temp2;}
}

遍歷

與鄰接矩陣相似，遍歷方式也是主要有BFS與DFS兩種

DFS遍歷法

void dfs(graphAL g,int i){edge* temp3=g.al[i].first;//記錄頭結(jié)點(diǎn)book[i]=false;//標(biāo)記已經(jīng)遍歷過(guò)的節(jié)點(diǎn)while(temp3){if (book[temp3->adjvex]) dfs(g,temp3->adjvex);temp3=temp3->next;//繼續(xù)遍歷}
}

需要用到標(biāo)記數(shù)組

bool book[MAX];
for (int i=0;i<g.numN;i++){book[i]=true;
}
for (int i=0;i<g.numN;i++){if (book[i]) dfs(g,l);
}

BFS遍歷法

void bfs(graphAL g){for (int i=0;i<g.numN;i++){book[i]=true;}deque <int>q;for (int i=0;i<g.numN;i++){if (book[i]){book[i]=false;q.push_back(i);//將頂點(diǎn)入隊(duì)while(!q.empty()){int t=q.front();q.pop_front();//將隊(duì)首出隊(duì)edge* temp4=g.al[t].first;while(temp4){//將與隊(duì)首相連的入隊(duì)if (book[temp4->adjvex]){book[temp4->adjvex]=false;q.push_back(temp4->adjvex);//將此頂點(diǎn)入隊(duì)}temp4=temp4->next;//繼續(xù)遍歷}}}}
}