??圖的存儲與遍歷
一．實驗?zāi)康?/b>
掌握圖的存儲結(jié)構(gòu)以及圖的深度優(yōu)先搜索遍歷、最小生成樹算法。
二．實驗要求與內(nèi)容
自構(gòu)造一無向圖，采用鄰接矩陣或者鄰接表存儲，完成圖的深度優(yōu)先搜索遍歷以及廣度優(yōu)先搜索遍歷算法的實現(xiàn)。
算法參見課本P214-225
三．實驗步驟
1．?dāng)?shù)據(jù)結(jié)構(gòu)
圖的儲存與遍歷的鄰接矩陣方式，在圖的深度優(yōu)先搜索中采用的是棧的方式進行結(jié)點的儲存，在圖的廣度優(yōu)先搜索中用的是隊列方式進行儲存。隊列和棧用的都是stl中所定義好的，需要頭文件#include<queue>和#include<stack>
在最小生成樹中采用合并集的思想，定義一個結(jié)構(gòu)體來儲存邊的開始點，結(jié)束點，以及權(quán)值大小。
2．算法設(shè)計
在深度優(yōu)先搜索中用棧的方式進行儲存以訪問過的結(jié)點，找到一個結(jié)點A后進行訪問標(biāo)記并壓入棧，訪問與它相連的另一個結(jié)點B標(biāo)記并壓入棧，再訪問結(jié)點B相連的任一結(jié)點標(biāo)記并壓入棧，重復(fù)，，直至沒有結(jié)點N沒有可供訪問的結(jié)點。則從棧中彈出頭結(jié)點，尋找結(jié)點N-1的另外可供訪問的結(jié)點，如果沒有則再彈出頭結(jié)點直至棧為空。
在廣度優(yōu)先搜索中用隊列的方式進行儲存訪問過的結(jié)點，找到一個結(jié)點A后進行訪問標(biāo)記并進入隊列，訪問與它相連的所有結(jié)點標(biāo)記并進入隊列，當(dāng)與它相連的所有結(jié)點都進入隊列后頭結(jié)點出隊，訪問隊列頭結(jié)點的所有可供訪問的結(jié)點并進入隊列，，重復(fù)，直至隊列為空
在這兩種訪問方式中設(shè)置一個visited用來標(biāo)記該結(jié)點是否被訪問過，如果未被訪問過visited[i]=0否則visited[i]=1;
合并集求最小生成樹，將每一個結(jié)點都看作成一棵樹，將權(quán)值進行排序，求最小權(quán)值的start和end是否在一棵樹中，如果不在一棵樹中則將兩個結(jié)點并為一棵樹，重復(fù)找最小權(quán)值和合并樹這兩個步驟直至所有結(jié)點都在一棵樹上為止。
詳細過程解析看代碼注釋
3．程序
void DFS1(int v)//深度優(yōu)先搜索
{
? ? cout<<b[v]<<" ";//訪問第v個結(jié)點
? ? visited[v]=1;//設(shè)置該結(jié)點已經(jīng)被訪問過；
? ? s.push(v);
? ? int count=1;
? ? while(!(s.empty()&& count==n))
? ? {
? ? ? ? if(s.empty() && count!=n)//需要判斷棧空但是結(jié)點并沒有遍歷完的情況
? ? ? ? {
? ? ? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(visited[i]==0)//如果該鄰接結(jié)點都還沒有被訪問過
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? cout<<b[i]<<" ";
? ? ? ? ? ? ? ? ? ? visited[i]=1;
? ? ? ? ? ? ? ? ? ? s.push(i);
? ? ? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int w=node1(s.top());//求該結(jié)點的鄰接結(jié)點
? ? ? ? while(w!=-1)//如果該結(jié)點存在鄰接結(jié)點
? ? ? ? {
? ? ? ? ? ? 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]<<" ";//訪問第v個結(jié)點
? ? visited[v]=1;//設(shè)置該結(jié)點已經(jīng)被訪問過；
? ? q.push(v);
? ? int count=1;
? ? while(!(q.empty()&&count==n))
? ? {
? ? if(q.empty() && count!=n)//需要判斷隊列空但是結(jié)點并沒有遍歷完的情況
? ? {
? ? ? ? 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é)點的鄰接結(jié)點
? ? while(w!=-1)//如果該結(jié)點存在鄰接結(jié)點
? ? {
? ? if(!visited[w])//如果該鄰接結(jié)點都還沒有被訪問過
? ? {
? ? ? ? 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 用來記錄最短路中應(yīng)該加入哪個點
{
? ? int fx=find(x);
? ? int fy=find(y);
? ? if(fx!=fy)
? ? {
? ? ? ? pre[fx]=fy;
? ? ? ? sum=edge[n].power+sum;
? ? }
}
4．程序調(diào)試
測試數(shù)據(jù)、程序運行結(jié)果截圖
四．結(jié)果與體會
在使用棧和隊列的時候可以用stl中的棧的隊列，，無需自己定義函數(shù)，但需要加頭文件#include<queue>和#include<stack>
在求最小權(quán)值的時候可以用查并集的方法。
在廣度優(yōu)先搜索和深度優(yōu)先搜索的時候要特別考慮如果棧或者隊列為空時但是結(jié)點卻沒有遍歷完。即輸入的圖并不是一棵樹，可能是森林的情況下。
五．源程序
另附
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
#define M 100
int a[M][M];//鄰接矩陣
int b[M];//頂點數(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;//無向圖的頂點數(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é)點的所有相連結(jié)點都被訪問過
}
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 用來記錄最短路中應(yīng)該加入哪個點
{
? ? 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]<<" ";//訪問第v個結(jié)點
? ? visited[v]=1;//設(shè)置該結(jié)點已經(jīng)被訪問過；
? ? s.push(v);
? ? int count=1;
? ? while(!(s.empty()&& count==n))
? ? {
? ? ? ? if(s.empty() && count!=n)//需要判斷棧空但是結(jié)點并沒有遍歷完的情況
? ? ? ? {
? ? ? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(visited[i]==0)//如果該鄰接結(jié)點都還沒有被訪問過
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? cout<<b[i]<<" ";
? ? ? ? ? ? ? ? ? ? visited[i]=1;
? ? ? ? ? ? ? ? ? ? s.push(i);
? ? ? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int w=node1(s.top());//求該結(jié)點的鄰接結(jié)點
? ? ? ? while(w!=-1)//如果該結(jié)點存在鄰接結(jié)點
? ? ? ? {
? ? ? ? ? ? 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]<<" ";//訪問第v個結(jié)點
? ? visited[v]=1;//設(shè)置該結(jié)點已經(jīng)被訪問過；
? ? q.push(v);
? ? int count=1;
? ? while(!(q.empty()&&count==n))
? ? {
? ? if(q.empty() && count!=n)//需要判斷隊列空但是結(jié)點并沒有遍歷完的情況
? ? {
? ? ? ? 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é)點的鄰接結(jié)點
? ? while(w!=-1)//如果該結(jié)點存在鄰接結(jié)點
? ? {
? ? if(!visited[w])//如果該鄰接結(jié)點都還沒有被訪問過
? ? {
? ? ? ? cout<<b[w]<<" ";
? ? ? ? q.push(w);
? ? ? ? visited[w]=1;
? ? ? ? count++;
? ? }
? ? ? ? w=node1(s);
? ? }
}
}
int main()
{
? ? //構(gòu)造無向圖，鄰接矩形
? ? cout<<"請輸入無向圖的頂點數(shù)和邊數(shù)";
? ? cin>>n>>m;
? ? for(int i=1;i<=n;i++)//初始化鄰接矩陣
? ? ? ? for(int j=1;j<=n;j++)
? ? ? ? ? ? a[i][j]=0;
? ? cout<<"請輸入頂點的順序";
? ? for(int i=1;i<=n;i++)
? ? {
? ? ? ? cin>>b[i];
? ? }
? ? cout<<"依次輸入每一條邊兩個頂點的序列號和權(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é)點順序為："<<endl;
? ? DFS(1);
? ? for(int i=1;i<=n;i++)
? ? ? ? visited[i]=0;
? ? //圖的深度優(yōu)先搜索
? ? cout<<endl;
? ? cout<<"深度優(yōu)先遍歷的結(jié)點順序為："<<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;
}
