无向图的邻接矩阵创建代码以及深度遍历广度遍历

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <queue>
  4 
  5 using namespace std;
  6 
  7 typedef char VertexType;
  8 typedef int EdgeType;
  9 const int MAXVEX = 100;
 10 const int INFINITY = 65535;
 11 
 12 class MGraph
 13 {
 14 public:
 15     VertexType vex[MAXVEX];//顶点表
 16     EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵,可看做边表
 17     int numVertexes,numEdges;//图中当前的顶点数和边数
 18 };
 19 
 20 
 21 //创建无向网图
 22 void CreateMGraph(MGraph &G)
 23 {
 24     int i,j,k,w;
 25     cout<<"输入顶点数和边数"<<endl;
 26     cin>>G.numVertexes>>G.numEdges;
 27     for(i = 0;i!=G.numVertexes;i++)
 28         cin>>G.vex[i];
 29     for(i = 0;i!=G.numVertexes;i++)
 30         for(j = 0;j<G.numVertexes;j++)
 31             G.arc[i][j]=INFINITY;
 32     for(k = 0;k!=G.numEdges;k++)
 33     {
 34         cout<<"输入边(vi,vj)上的下标i和j,以及权w"<<endl;
 35         cin>>i>>j>>w;
 36         G.arc[i][j]=w;
 37         G.arc[j][i]=G.arc[i][j];
 38     }
 39 }
 40 
 41 bool visited[MAXVEX];
 42 //邻接矩阵的深度优先递归算法
 43 void DFS(MGraph G,int i )
 44 {
 45     visited[i]=true;
 46     cout<<G.vex[i];
 47     for(int j = 0;j!=G.numVertexes;j++)
 48     {
 49         if(G.arc[i][j] ==1 && !visited[j])
 50             DFS(G,j);
 51     }
 52 }
 53 //邻接矩阵的深度遍历操作
 54 
 55 void DFSTraverse(MGraph G)
 56 {
 57     int i ;
 58     for(i = 0;i!=G.numVertexes;i++)
 59     {
 60         visited[i] = false;//初始化所有的顶点都是没有被访问过的.
 61     }
 62     for(i = 0;i!=G.numVertexes;++i)
 63     {
 64         if(!visited[i])  //这里是对没有访问的顶点进行深度遍历调用,如果图是连通图.for循环只执行一遍.
 65             DFS(G,i);
 66     }
 67 }
 68 
 69 
 70 //广度优先遍历
 71 void BFSTraverse(MGraph G)
 72 {
 73     int i,j;
 74     queue<int> Q;
 75     for(i = 0;i<G.numVertexes;++i)
 76         visited[i] = false;
 77     for(i = 0;i!=G.numVertexes;++i)
 78     {
 79         if(!visited[i])
 80         {
 81             visited[i]= true;
 82             cout<<G.vex[i]<<endl;
 83             Q.push(i);
 84             while(!Q.empty())
 85             {
 86                 i = Q.front();
 87                 Q.pop();
 88                 for(j=0;j!=G.numVertexes;j++)
 89                 {
 90                     if(G.arc[i][j] == 1&& !visited[j])
 91                     {
 92                         visited[j]=true;
 93                         cout<<G.vex[j]<<endl;
 94                         Q.push(j);
 95                     }
 96                 }
 97             }
 98         }
 99     }
100 }
101 int _tmain(int argc, _TCHAR* argv[])
102 {
103 
104     return 0 ;
105 }