實驗內容：

實現教材算法6.2利用鄰接矩陣構造無向圖的算法，提供從鄰接矩陣獲得鄰接表的功能，在此基礎上進行深度優先遍歷和廣度優先遍歷。

實驗步驟：

（1）按照實驗要求編寫代碼，構造無向圖。
?創建所示無向圖
屏幕輸出鄰接矩陣
0 1 0 0 0 1
1 0 1 1 0 0
0 1 0 1 1 0
0 1 1 0 1 0
0 0 1 1 0 1
1 0 0 0 1 0

深度優先遍歷

屏幕輸出： 1 2 3 4 5 6

廣度優先遍歷

屏幕輸出：1 2 6 3 4 5
（2）輸入驗收用例，驗證其輸出結果。

#include <iostream>
#ifndef DATA_STRUCTURE_STATUS_H
#include <stdio.h>
//狀態碼
#define TRUE              1
#define FALSE            0
#define OK                  1
#define ERROR           0
#endif
#ifndef OVERFLOW
#define OVERFLOW    -2
#endif // OVERFLOW
#ifndef NULL
#define NULL((void*) 0)
#endif // NULL
typedef int Status;
#define MaxInt 32767  //表示極大值
#define MVNum 100     //表示最大頂點數
using namespace std;//圖的鄰接矩陣存儲表示：
typedef int VerTexType;//頂點字符類型
typedef int ArcType;    //邊的權值
typedef struct
{VerTexType vexs[MVNum];//頂點表ArcType arcs[MVNum][MVNum];//鄰接矩陣int vexnum,arcnum;//圖的當前點數和邊數
}AMGraph;typedef string OtherInfo;//圖的鄰接表存儲表示：
typedef struct ArcNode//邊結構
{int adjvex;struct ArcNode *nextarc;OtherInfo info;//其他信息
}ArcNode;typedef struct VNode//頂點結構
{VerTexType data;//存儲頂點信息ArcNode *firstarc;
}VNode,AdjList[MVNum];typedef struct
{AdjList vertics;//鄰接表int vexnum,arcnum;//頂點數和弧數int kind;
}ALGraph;bool visited[MVNum];int LocateVex(AMGraph G,VerTexType u)
{//定位每個頂點的位置int i;for(i=0;i<G.vexnum;i++){if(u==G.vexs[i])return i;}return -1;
}//構建無向網：
Status CreateUDN(AMGraph &G)
{cout<<"請輸入圖的頂點數目，邊數目:";cin>>G.vexnum>>G.arcnum;//輸入當前的頂點數目和邊的數目for(int i=0;i<G.vexnum;i++){cout<<"請輸入第"<<i<<"個頂點：";cin>>G.vexs[i];//初始化點的信息}for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){G.arcs[i][j]=MaxInt;//初始化鄰接矩陣}}int i,j;int v1,v2,w;for(int k=0;k<G.arcnum;k++){cout<<"邊:";cin>>v1>>v2>>w;i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j];}return OK;
}//鄰接矩陣轉換成鄰接表
void change(AMGraph G,ALGraph &p)
{int i,j;ArcNode *q;for(i=0;i<G.vexnum;i++){p.vertics[i].firstarc=NULL;}for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(G.arcs[i][j]){q=new ArcNode;q->adjvex=j;q->nextarc=p.vertics[j].firstarc;p.vertics[j].firstarc=q;}}}
}//深度優先遍歷：
void DFS_AM(AMGraph G,int v)
{cout<<v+1;visited[v]=true;for(int w=0;w<G.vexnum;w++)//依次檢查鄰接矩陣所在的行{if(G.arcs[v][w]!=0&&(!visited[w]))DFS_AM(G,w);//w是v的鄰接點，如果w未訪問，則遞歸調用DFS}
}//廣度優先遍歷：
void BFS(AMGraph G,int v)
{for(int i=0;i<G.vexnum;i++){visited[i]=false;}int Q[MaxInt];cout<<G.vexs[v];visited[v]=true;int w,u;int front=-1,rear=-1;Q[++rear]=v;while(front!=rear){u=Q[++front];for(w=0;w<G.vexnum;w++){if((!visited[w])&&(G.arcs[u][w]==1)){cout<<G.vexs[w];visited[w]=true;Q[++rear]=w;}}}
}int main()
{cout<<"無向網圖"<<endl;cout<<"1.構建網圖"<<endl;cout<<"2.輸出鄰接矩陣"<<endl;cout<<"3.深度優先遍歷"<<endl;cout<<"4.廣度優先遍歷"<<endl;int n,a;AMGraph G;ALGraph P;while(1){cout<<"請輸入你的選擇："<<endl;cin>>n;if(n==1){CreateUDN(G);cout<<"操作完成！"<<endl;}else if(n==2){cout<<"鄰接矩陣為：";for(int i=0;i<G.vexnum;i++){cout<<endl;for(int j=0;j<G.vexnum;j++){if(G.arcs[i][j]==MaxInt){cout<<"0 ";}else{cout<<G.arcs[i][j]<<" ";}}}cout<<"\n操作完成"<<endl;}else if(n==3){cout<<"深度優先遍歷為：";DFS_AM(G,0);cout<<"\n操作完成！"<<endl;}else if(n==4){cout<<"廣度優先遍歷為：";BFS(G,0);cout<<"\n操作完成"<<endl;}else if(n==5){cout<<"本次操作結束"<<endl;break;}}return 0;
}