??圖的存儲(chǔ)與遍歷
一．實(shí)驗(yàn)?zāi)康?/b>
掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)以及圖的深度優(yōu)先搜索遍歷彤敛、最小生成樹(shù)算法掠抬。
二．實(shí)驗(yàn)要求與內(nèi)容
自構(gòu)造一無(wú)向圖，采用鄰接矩陣或者鄰接表存儲(chǔ)瓷耙，完成圖的深度優(yōu)先搜索遍歷以及廣度優(yōu)先搜索遍歷算法的實(shí)現(xiàn)朱躺。
算法參見(jiàn)課本P214-225
三．實(shí)驗(yàn)步驟
1．?dāng)?shù)據(jù)結(jié)構(gòu)
圖的儲(chǔ)存與遍歷的鄰接矩陣方式，在圖的深度優(yōu)先搜索中采用的是棧的方式進(jìn)行結(jié)點(diǎn)的儲(chǔ)存搁痛，在圖的廣度優(yōu)先搜索中用的是隊(duì)列方式進(jìn)行儲(chǔ)存长搀。隊(duì)列和棧用的都是stl中所定義好的，需要頭文件#include<queue>和#include<stack>
在最小生成樹(shù)中采用合并集的思想鸡典，定義一個(gè)結(jié)構(gòu)體來(lái)儲(chǔ)存邊的開(kāi)始點(diǎn)源请，結(jié)束點(diǎn)，以及權(quán)值大小彻况。
2．算法設(shè)計(jì)
在深度優(yōu)先搜索中用棧的方式進(jìn)行儲(chǔ)存以訪問(wèn)過(guò)的結(jié)點(diǎn)谁尸，找到一個(gè)結(jié)點(diǎn)A后進(jìn)行訪問(wèn)標(biāo)記并壓入棧，訪問(wèn)與它相連的另一個(gè)結(jié)點(diǎn)B標(biāo)記并壓入棧纽甘，再訪問(wèn)結(jié)點(diǎn)B相連的任一結(jié)點(diǎn)標(biāo)記并壓入棧良蛮，重復(fù)，悍赢，直至沒(méi)有結(jié)點(diǎn)N沒(méi)有可供訪問(wèn)的結(jié)點(diǎn)决瞳。則從棧中彈出頭結(jié)點(diǎn)，尋找結(jié)點(diǎn)N-1的另外可供訪問(wèn)的結(jié)點(diǎn)左权，如果沒(méi)有則再?gòu)棾鲱^結(jié)點(diǎn)直至棧為空皮胡。
在廣度優(yōu)先搜索中用隊(duì)列的方式進(jìn)行儲(chǔ)存訪問(wèn)過(guò)的結(jié)點(diǎn)，找到一個(gè)結(jié)點(diǎn)A后進(jìn)行訪問(wèn)標(biāo)記并進(jìn)入隊(duì)列赏迟，訪問(wèn)與它相連的所有結(jié)點(diǎn)標(biāo)記并進(jìn)入隊(duì)列屡贺，當(dāng)與它相連的所有結(jié)點(diǎn)都進(jìn)入隊(duì)列后頭結(jié)點(diǎn)出隊(duì)，訪問(wèn)隊(duì)列頭結(jié)點(diǎn)的所有可供訪問(wèn)的結(jié)點(diǎn)并進(jìn)入隊(duì)列锌杀，甩栈，重復(fù)，直至隊(duì)列為空
在這兩種訪問(wèn)方式中設(shè)置一個(gè)visited用來(lái)標(biāo)記該結(jié)點(diǎn)是否被訪問(wèn)過(guò)抛丽，如果未被訪問(wèn)過(guò)visited[i]=0否則visited[i]=1;
合并集求最小生成樹(shù)谤职，將每一個(gè)結(jié)點(diǎn)都看作成一棵樹(shù)，將權(quán)值進(jìn)行排序亿鲜，求最小權(quán)值的start和end是否在一棵樹(shù)中允蜈，如果不在一棵樹(shù)中則將兩個(gè)結(jié)點(diǎn)并為一棵樹(shù)，重復(fù)找最小權(quán)值和合并樹(shù)這兩個(gè)步驟直至所有結(jié)點(diǎn)都在一棵樹(shù)上為止蒿柳。
詳細(xì)過(guò)程解析看代碼注釋
3．程序
void DFS1(int v)//深度優(yōu)先搜索
{
? ? cout<<b[v]<<" ";//訪問(wèn)第v個(gè)結(jié)點(diǎn)
? ? visited[v]=1;//設(shè)置該結(jié)點(diǎn)已經(jīng)被訪問(wèn)過(guò)饶套；
? ? s.push(v);
? ? int count=1;
? ? while(!(s.empty()&& count==n))
? ? {
? ? ? ? if(s.empty() && count!=n)//需要判斷棧空但是結(jié)點(diǎn)并沒(méi)有遍歷完的情況
? ? ? ? {
? ? ? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(visited[i]==0)//如果該鄰接結(jié)點(diǎn)都還沒(méi)有被訪問(wèn)過(guò)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? cout<<b[i]<<" ";
? ? ? ? ? ? ? ? ? ? visited[i]=1;
? ? ? ? ? ? ? ? ? ? s.push(i);
? ? ? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int w=node1(s.top());//求該結(jié)點(diǎn)的鄰接結(jié)點(diǎn)
? ? ? ? while(w!=-1)//如果該結(jié)點(diǎn)存在鄰接結(jié)點(diǎn)
? ? ? ? {
? ? ? ? ? ? if(!visited[w])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cout<<b[w]<<" ";
? ? ? ? ? ? ? ? s.push(w);
? ? ? ? ? ? ? ? visited[w]=1;
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? }
? ? ? ? ? ? w=node1(w);
? ? ? ? }
? ? ? ? s.pop();
? ? }
}
void DFS(int v)//廣度優(yōu)先搜索
{
? ? cout<<b[v]<<" ";//訪問(wèn)第v個(gè)結(jié)點(diǎn)
? ? visited[v]=1;//設(shè)置該結(jié)點(diǎn)已經(jīng)被訪問(wèn)過(guò)垒探；
? ? q.push(v);
? ? int count=1;
? ? while(!(q.empty()&&count==n))
? ? {
? ? if(q.empty() && count!=n)//需要判斷隊(duì)列空但是結(jié)點(diǎn)并沒(méi)有遍歷完的情況
? ? {
? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? {
? ? ? ? ? ? if(visited[i]==0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cout<<b[i]<<" ";
? ? ? ? ? ? ? ? visited[i]=1;
? ? ? ? ? ? ? ? q.push(i);
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? int s=q.front();
? ? q.pop();
? ? int w=node1(s);//求該結(jié)點(diǎn)的鄰接結(jié)點(diǎn)
? ? while(w!=-1)//如果該結(jié)點(diǎn)存在鄰接結(jié)點(diǎn)
? ? {
? ? if(!visited[w])//如果該鄰接結(jié)點(diǎn)都還沒(méi)有被訪問(wèn)過(guò)
? ? {
? ? ? ? cout<<b[w]<<" ";
? ? ? ? q.push(w);
? ? ? ? visited[w]=1;
? ? ? ? count++;
? ? }
? ? ? ? w=node1(s);
? ? }
}
}
int find(int x)
{
? ? if(x!=pre[x])
? ? ? ? pre[x]=find(pre[x]);
? ? return pre[x];
}
void megre(int x,int y,int n)//查并集合并函數(shù)妓蛮，n 用來(lái)記錄最短路中應(yīng)該加入哪個(gè)點(diǎn)
{
? ? int fx=find(x);
? ? int fy=find(y);
? ? if(fx!=fy)
? ? {
? ? ? ? pre[fx]=fy;
? ? ? ? sum=edge[n].power+sum;
? ? }
}
4．程序調(diào)試
測(cè)試數(shù)據(jù)、程序運(yùn)行結(jié)果截圖
四．結(jié)果與體會(huì)
在使用棧和隊(duì)列的時(shí)候可以用stl中的棧的隊(duì)列圾叼，蛤克，無(wú)需自己定義函數(shù)捺癞，但需要加頭文件#include<queue>和#include<stack>
在求最小權(quán)值的時(shí)候可以用查并集的方法。
在廣度優(yōu)先搜索和深度優(yōu)先搜索的時(shí)候要特別考慮如果椆辜罚或者隊(duì)列為空時(shí)但是結(jié)點(diǎn)卻沒(méi)有遍歷完髓介。即輸入的圖并不是一棵樹(shù)，可能是森林的情況下筋现。
五．源程序
另附
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
#define M 100
int a[M][M];//鄰接矩陣
int b[M];//頂點(diǎn)數(shù)據(jù)
int visited[M];
queue<int> q;
stack<int>s;
int pre[M];
int sum=0;
struct node
{
? ? int start,end,power;
}edge[20];
int m,n;//無(wú)向圖的頂點(diǎn)數(shù)和邊數(shù)
int node1(int v)
{
? ? for(int i=1;i<=n;i++)
? ? {
? ? ? ? if(a[v][i]!=0 && visited[i]==0)
? ? ? ? ? ? return i;
? ? }
? ? return -1;//如果該結(jié)點(diǎn)的所有相連結(jié)點(diǎn)都被訪問(wèn)過(guò)
}
int cmp(node a,node b)//按權(quán)值排序
{
? ? return a.power<b.power;
}
int find(int x)
{
? ? if(x!=pre[x])
? ? ? ? pre[x]=find(pre[x]);
? ? return pre[x];
}
void megre(int x,int y,int n)//查并集合并函數(shù)唐础，n 用來(lái)記錄最短路中應(yīng)該加入哪個(gè)點(diǎn)
{
? ? int fx=find(x);
? ? int fy=find(y);
? ? if(fx!=fy)
? ? {
? ? ? ? pre[fx]=fy;
? ? ? ? sum=edge[n].power+sum;
? ? }
}
void DFS1(int v)//深度優(yōu)先搜索
{
? ? cout<<b[v]<<" ";//訪問(wèn)第v個(gè)結(jié)點(diǎn)
? ? visited[v]=1;//設(shè)置該結(jié)點(diǎn)已經(jīng)被訪問(wèn)過(guò)；
? ? s.push(v);
? ? int count=1;
? ? while(!(s.empty()&& count==n))
? ? {
? ? ? ? if(s.empty() && count!=n)//需要判斷椃桑空但是結(jié)點(diǎn)并沒(méi)有遍歷完的情況
? ? ? ? {
? ? ? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(visited[i]==0)//如果該鄰接結(jié)點(diǎn)都還沒(méi)有被訪問(wèn)過(guò)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? cout<<b[i]<<" ";
? ? ? ? ? ? ? ? ? ? visited[i]=1;
? ? ? ? ? ? ? ? ? ? s.push(i);
? ? ? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int w=node1(s.top());//求該結(jié)點(diǎn)的鄰接結(jié)點(diǎn)
? ? ? ? while(w!=-1)//如果該結(jié)點(diǎn)存在鄰接結(jié)點(diǎn)
? ? ? ? {
? ? ? ? ? ? if(!visited[w])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cout<<b[w]<<" ";
? ? ? ? ? ? ? ? s.push(w);
? ? ? ? ? ? ? ? visited[w]=1;
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? }
? ? ? ? ? ? w=node1(w);
? ? ? ? }
? ? ? ? s.pop();
? ? }
}
void DFS(int v)//廣度優(yōu)先搜索
{
? ? cout<<b[v]<<" ";//訪問(wèn)第v個(gè)結(jié)點(diǎn)
? ? visited[v]=1;//設(shè)置該結(jié)點(diǎn)已經(jīng)被訪問(wèn)過(guò)一膨；
? ? q.push(v);
? ? int count=1;
? ? while(!(q.empty()&&count==n))
? ? {
? ? if(q.empty() && count!=n)//需要判斷隊(duì)列空但是結(jié)點(diǎn)并沒(méi)有遍歷完的情況
? ? {
? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? {
? ? ? ? ? ? if(visited[i]==0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cout<<b[i]<<" ";
? ? ? ? ? ? ? ? visited[i]=1;
? ? ? ? ? ? ? ? q.push(i);
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? int s=q.front();
? ? q.pop();
? ? int w=node1(s);//求該結(jié)點(diǎn)的鄰接結(jié)點(diǎn)
? ? while(w!=-1)//如果該結(jié)點(diǎn)存在鄰接結(jié)點(diǎn)
? ? {
? ? if(!visited[w])//如果該鄰接結(jié)點(diǎn)都還沒(méi)有被訪問(wèn)過(guò)
? ? {
? ? ? ? cout<<b[w]<<" ";
? ? ? ? q.push(w);
? ? ? ? visited[w]=1;
? ? ? ? count++;
? ? }
? ? ? ? w=node1(s);
? ? }
}
}
int main()
{
? ? //構(gòu)造無(wú)向圖，鄰接矩形
? ? cout<<"請(qǐng)輸入無(wú)向圖的頂點(diǎn)數(shù)和邊數(shù)";
? ? cin>>n>>m;
? ? for(int i=1;i<=n;i++)//初始化鄰接矩陣
? ? ? ? for(int j=1;j<=n;j++)
? ? ? ? ? ? a[i][j]=0;
? ? cout<<"請(qǐng)輸入頂點(diǎn)的順序";
? ? for(int i=1;i<=n;i++)
? ? {
? ? ? ? cin>>b[i];
? ? }
? ? cout<<"依次輸入每一條邊兩個(gè)頂點(diǎn)的序列號(hào)和權(quán)值"<<endl;
? ? for(int i=1;i<=m;i++)
? ? {
? ? ? ? int x,y,weight;
? ? ? ? scanf("%d %d %d",&x,&y,&weight);
? ? ? ? edge[i].start=x;
? ? ? ? edge[i].end=y;
? ? ? ? edge[i].power=weight;
? ? ? ? a[x][y]=weight;
? ? ? ? a[y][x]=weight;
? ? }
? ? //圖的廣度優(yōu)先搜索
?? cout<<"廣度優(yōu)先遍歷的結(jié)點(diǎn)順序?yàn)椋?<<endl;
? ? DFS(1);
? ? for(int i=1;i<=n;i++)
? ? ? ? visited[i]=0;
? ? //圖的深度優(yōu)先搜索
? ? cout<<endl;
? ? cout<<"深度優(yōu)先遍歷的結(jié)點(diǎn)順序?yàn)椋?<<endl;
? ? DFS1(1);
? ? cout<<endl;
? ? //求最小權(quán)值
? ? for(int i=1;i<=m;i++)
? ? ? ? pre[i]=i;
?? sort(edge+1,edge+m+1,cmp);
? ? for(int i=1;i<=m;i++)
? ? ? ? megre(edge[i].start,edge[i].end,i);
? ? cout<<"最小權(quán)值為：";
? ? cout<<sum<<endl;
?? return 0;
}
