**邻接矩阵对于无向图的理解

对于图的构造我们有三种方法，第一种邻接矩阵，第二种邻接表，第三种十字链表。在这里我们深度解析邻接矩阵与邻接表的构造方法！

首先我们阐述第一种方法: 邻接矩阵（邻接矩阵用于相对来说比较稠密的无向图）

例如此无向图:

相对应的邻接矩阵表示如下:

  1 #include<iostream>
  3 #include<string>
  5 #define maxSize 10
  7 using namespace  std;
  9 //在此声明 不用template 模板
 11 class Graph{
 13 public:
 15 Graph(string str[],int vertex,int arc1);
 17 ~Graph(){
 19 //由于没有动态申请内存 无法对改内存进行释放(在此处做声明)
 21 cout<<"析构函数调用成功!";
 23 };
 25 void DFS(int v); //深度优先遍历
 27 void FdgDFS(int v); //非递归的深度优先遍历
 29 void BFS(int v); //广度优先遍历 
 31 private:
 33 int verNum;
 35 int arcNum;
 37 string verName[maxSize];
 39 //对于邻接矩阵构造无向图肯定少不了邻接矩阵 即二维数组
 41 int arc[maxSize][maxSize];
 43 //遍历时，对于没有访问过的顶点，需要建立flag 标识
 45 int visited[maxSize]={0};
 47 };
 49 Graph::Graph(string str[],int vertex,int arc1){
 51  verNum=vertex;
 53 //顶点的赋值
 55 for(int i=0;i<verNum;i++){
 57 verName[i]=str[i];
 59 }
 61 for(int i=0;i<verNum;i++)  //初始化邻接矩阵
 63   for(int j=0;j<verNum;j++)
 65     arc[i][j]=arc[j][i]=0;
 67 //对边进行构造 输入依附于边的邻接点的下标
 69 arcNum=arc1;
 71 for(int k=0;k<arcNum;k++){
 73   int i=0;
 75   int j=0;
 77   cout<<"请输入依附于边的邻接点下标 "<<endl;
 79   cin>>i>>j;
 81   //无向图的邻接矩阵是对称的 
 83   arc[i][j]=arc[j][i]=1; 
 85  }
 87 }
 89 //递归的深度遍历
 91 void Graph::DFS(int v){
 93  cout<<verName[v];
 95  visited[v]=1;
 97  for(int j=0;j<verNum;j++){
 99  if(arc[v][j]==1 && visited[j]==0)
101   DFS(j);
103   }
105 }
107 //非递归的深度优先遍历
109 void Graph::FdgDFS(int v){
111  int Stack[maxSize];
113  int top=-1;
115  cout<<verName[v];
117  visited[v]=1;
119  Stack[++top]=v;
121  while(top!=-1){
123  v=Stack[top];
125  for(int j=0;j<verNum;j++){
127   if(arc[v][j]==1 && visited[j]==0){
129   cout<<verName[j];
131   visited[j]=1;
133  Stack[++top]=j;
135  break;
137  } 
139  if(j==verNum-1)
141  top--;
143   } 
145  }
147 }
149 //广度优先遍历
151 void Graph::BFS(int v){
153  //定义队列进行遍历
155  int Queue[maxSize];
157  int front=-1;
159  int rear=-1;
161  cout<<verName[v];
163  visited[v]=1;
165  Queue[++rear]=v;
167  while(front!=rear){
169  //出队
171  v=Queue[++front];
173  for(int j=0;j<verNum;j++)
175  if(arc[v][j]==1 && visited[j]==0){
177  cout<<verName[j];
179  visited[j]=1;
181  //入队
183  Queue[++rear]=j;
185     }
187   }
189 }
193 int main(){ 
195  string mystr[4]={"v0","v1","v2","v3"};
197  Graph myGraph(mystr,4,4);
199  //深度优先遍历
201  myGraph.DFS(2);
203  //非递归深度优先遍历
205  myGraph.FdgDFS(2);
207  //广度优先遍历
209  myGraph.BFS(2);
211  return 0;
213 }