以邻接矩阵的存储方式，进行广度优先搜索遍历，以邻接表的存储方式，进行深度优先遍历

 一、以邻接矩阵的存储方式，进行广度优先搜索遍历，

图以邻接矩阵存储的存储结构

1.  
   //邻接矩阵的存储结构
2.  
   const int maxvnum= 10//{图的最大顶点数，它要大于等于具体图的顶点数n}
3.  
   const int maxenum =10;//图的最大变数，它要大于等于具体图的变数e；
4.  
   typedef int weightType;//定义边的权值类型
5.  
   const weightType maxvalue=999999999;//特定权值，要大于等于所有权值之和
6.  
    
7.  
   typedef int adjmatrix [maxvnum][maxvnum];//定义adjmatrix为存储邻接矩阵的数组类型

邻接矩阵的初始化

1.  
   void InitMatrix(adjmatrix GA,int k)//邻边矩阵初始化
2.  
   { //假定k等于0为无权图，k =0，为有权图
3.  
   int j,i;
4.  
   for(i=0;i<maxvnum;i )
5.  
   {
6.  
   for( j=0;j<maxvnum;j )
7.  
   {
8.  
   if(i==j) GA[i][j]=0;
9.  
   else if(k) GA[i][j] =maxvalue;
10.  
    else GA[i][j]=0;
11.  
    }
12.  
    }
13.  
    }

根据一个图的边集生成邻接矩阵的算法

1.  
   void CreatMatrix(adjmatrix GA,int n,char*s,int k1,int k2)
2.  
   {
3.  
   //k1为0，则为无向图，否则为有向图；k2为0则为无权图，否则为有权图；
4.  
   //s字符串用来保存一个图的边集，n为图的顶点数
5.  
   istrstream sin(s);
6.  
   char c1,c2,c3;
7.  
   int i,j;
8.  
   weightType w;//保存权值
9.  
   sin>>c1;//将字符串‘{’吃掉；
10.  
    if(k1==0&&k2==0) //建立无向无权图
11.  
    do{
12.  
    sin>>c1>>i>>c2>>j>>c3;//从sin流读入和处理一条边（即字符串s）
13.  
    GA[i][j]=GA[j][i]=1;
14.  
    sin>>c1;
15.  
    if(c1=='}')break;
16.  
    }while(1);
17.  
    if(k1!=0&&k2==0) //建立有向无权图
18.  
    do{
19.  
    sin>>c1>>i>>c2>>j>>c3;
20.  
    GA[i][j]=1;
21.  
    sin>>c1;
22.  
    if(c1=='}')break;
23.  
    }while(1);
24.  
    if(k1==0&&k2!=0)//建立无向有权图
25.  
    do{
26.  
    sin>>c1>>i>>c2>>j>>c3>>w;//w为权值
27.  
    GA[i][j]=GA[j][i]=w;
28.  
    sin>>c1;
29.  
    if(c1=='}')break;
30.  
    }while(1);
31.  
    if(k1!=0&&k2!=0)//有向有权图
32.  
    do{
33.  
    sin>>c1>>i>>c2>>j>>c3>>w;
34.  
    GA[i][j]=w;
35.  
    sin>>c1;
36.  
    if(c1=='}')break;
37.  
    }while(1);
38.  
     
39.  
     
40.  
    }

根据图的邻接矩阵输出图的二元组表示（顶点集和边集）

1.  
   void PrintMatrix(adjmatrix GA,int n,int k1,int k2)
2.  
   {//
3.  
   int i,j;
4.  
   cout<<"V={"; //输出顶点集开始
5.  
   for(i=0;i<n-1;i ) cout<<i<<',';
6.  
   cout<<n-1<<"}"<<endl; //输出顶点集结束
7.  
   cout<<"E={"; //输出边集开始
8.  
   if(k2==0){ //对无权图的处理情况
9.  
   for(i=0;i<n;i )
10.  
    for(j=0;j<n;j )
11.  
    if(GA[i][j]==1)
12.  
    if(k1==0){ //对无向无权图处理
13.  
    if(i<j) cout<<"("<<i<<","<<j<<')'<<',';
14.  
    }
15.  
    else
16.  
    cout<<'<'<<i<<','<<j<<'>'<<',';
17.  
    }
18.  
    else{ //对有权图的处理情况
19.  
    for(i=0;i<n;j )
20.  
    for(j=0;j<n;j )
21.  
    if(GA[i][j]!=0&&GA[i][j]!=maxvalue)
22.  
    if(k1==0){ //对无向有权图
23.  
    if(i<j)
24.  
    cout<<'('<<','<<j<<'>'<<GA[i][j]<<',';
25.  
    }
26.  
    else
27.  
    cout<<'<'<<i<<','<<j<<'>'<<GA[i][j]<<',';
28.  
    }
29.  
    cout<<'}'<<endl;
30.  
    }

以邻接矩阵的存储方式深度优先搜索遍历

1.  
   void dfsMatrix(adjmatrix GA,int i,int n,bool*visited)
2.  
   {//从初始点i开始出发进行深度优先搜索邻接矩阵GA表示的图
3.  
   cout<<i<<" ";
4.  
   visited[i]=true;//标记i点已经被访问过
5.  
   for(int j=0;j<n;j )//依次搜索i点的每个邻接点
6.  
   if(GA[i][j]!=0 &&GA[i][j]!=maxvalue &&!visited[i])
7.  
   {
8.  
   dfsMatrix(GA,j,n,visited);//若i的某个有效邻接点j未被访问过，则从j进行递归调用
9.  
   }
10.  
    }

以邻接矩阵存储方式进行广度优先搜索遍历

1.  
   void bfsMatrix(adjmatrix GA, int i,int n,bool *visited)
2.  
   {
3.  
   const int Maxsize = 30;
4.  
   int front=0,rear=0;
5.  
   int q[Maxsize]={0};
6.  
   cout<<i<<' ';
7.  
   visited[i]=true;
8.  
   q[ rear]= i;
9.  
   while(front!=rear)
10.  
    {front=(front 1)%Maxsize;
11.  
    int k = q[front];
12.  
    for(int j=0; j<n; j )
13.  
    {
14.  
    if(GA[k][j]!=0 &&GA[k][j]!=maxvalue &&!visited[j])
15.  
    {
16.  
    cout<<j<<' ';
17.  
    visited[j]=true;
18.  
    rear=(rear 1)%Maxsize;
19.  
    q[rear]=j;
20.  
    }
21.  
    }
22.  
    }

二）.以邻接表的存储方式进行的深度优先搜索遍历

1.邻接表的存储结构3.

1.  
   typedef int weightType;//权值类型
2.  
   const int MAX = 10;//最大顶点数，可任意定义
3.  
   struct edgenode
4.  
   {
5.  
   int adjvex;//顶点
6.  
   weightType weight;//权值
7.  
   edgenode *next;
8.  
   };
9.  
   typedef edgenode *adjlist[MAX];

2.邻接表的初始化

1.  
   void InitAdjoin(adjlist GL)
2.  
   {
3.  
   for(int i = 0;i<MAX;i )
4.  
   GL[i]=NULL;
5.  
   }

3.根据一个图的边集生成邻接表

1.  
   void CreateAdjoin(adjlist GL,int n, char*s,int k1,int k2)
2.  
   {
3.  
   istrstream sin(s);
4.  
   char c1,c2,c3;
5.  
   int i,j;
6.  
   weightType w;
7.  
   edgenode *p;
8.  
   sin>>c1;
9.  
   if(k2==0)
10.  
    {
11.  
    do{
12.  
    sin>>c1>>i>>c2>>j>>c3;
13.  
    p=new edgenode;
14.  
    p->adjvex =j;
15.  
    p->weight =1;
16.  
    p->next = GL[i];
17.  
    GL[i]=p;
18.  
    if(k1==0)
19.  
    {
20.  
    p=new edgenode;
21.  
    p->adjvex =i;
22.  
    p->weight =1;
23.  
    p->next = GL[j];
24.  
    GL[j]=p;
25.  
    }
26.  
    sin>>c1;
27.  
    }while(c1==',');
28.  
    }
29.  
    else
30.  
    {
31.  
    do{
32.  
    sin>>c1>>i>>c2>>j>>c2>>w;
33.  
    p=new edgenode;
34.  
    p->adjvex =j;
35.  
    p->weight =w;
36.  
    p->next = GL[i];
37.  
    GL[i]=p;
38.  
    if(k1==0)
39.  
    {p=new edgenode;
40.  
    p->adjvex =i;
41.  
    p->weight =w;
42.  
    p->next = GL[j];
43.  
    GL[j]=p;
44.  
    }
45.  
    sin>>c1;
46.  
    }while(c1==',');
47.  
    }
48.  
     
49.  
    }

4.图以邻接表的存储结构深度优先搜索遍历

1.  
   void dfsAdjoin(adjlist GL,int i,int n,bool*visited)
2.  
   {
3.  
   cout<<i<<' ';
4.  
   visited[i]=true;
5.  
   edgenode*p=GL[i];
6.  
   while(p!=NULL)
7.  
   {
8.  
   int j = p->adjvex;
9.  
   if(!visited[j])
10.  
    dfsAdjoin(GL,j,n,visited);
11.  
    p=p->next;
12.  
    }
13.  
     
14.  
    }

三、结果分析

深度优先遍历： 类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到（注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点）。

广度优先遍历： 类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。

这篇好文章是转载于：学新通技术网