l7_3.cpp

《数据结构（C++描述）》-李根强-源代码

//用邻接矩阵实现无向图的深度优先搜索遍历
#include<iostream.h>
const  int  n=8;                    // 图中顶点数  
const  int  e=10;
typedef int elemtype;                    // 图中边数
struct    graph
{  
elemtype       v[n+1];                  // 存放顶点信息v1,v2,….vn，不使用v[0]存储空间
int    arcs[n+1][n+1];             // 邻接矩阵
};

graph  g;
int visited[n+1];
void  creatadj( )
{ int i,j,k ;
  cout<<"请输入顶点信息"<<endl;
  for  (k=1; k<=n; k++)
  cin>>g.v[k];                            //输入顶点信息   
for (i=1; i<=n;  i++ )
  for (j=1; j<=n; j++)
   g.arcs[i][j]=0;
for (k=1; k<=e; k++)
{    cout<<"请输入一条边";
	cin>>i>>j;                             //输入一条边(i,j)           
    cout<<endl;
	g.arcs[i][j]=1;
    g.arcs[j][i]=1;
}
}
void dfs (int i)                             // 从顶点i 出发遍历
{  
 int j;                                                           
           cout<<g.v[i]<<"  ";                        //输出访问顶点
           visited[i]=1;        //全局数组访问标记置1表示已经访问
            for(j=1; j<=n; j++)
				if ((g.arcs[i][j]==1)&&(!visited[j]))
                    dfs(j);
        }

void main( )
{  int i,j;
    for(i=1;i<=n;i++)
		visited[i]=0;
	creatadj( );
	for(i=1;i<=n;i++)
	{for(j=1;j<=n;j++)
			cout<<g.arcs[i][j]<<"  ";
	cout<<endl;
	}
	cout<<"请输入开始访问的顶点";
	cin>>i;
	cout<<endl;
	cout<<"从"<<i<<"出发的深度优先搜索遍历序列为"<<endl;
	dfs(i);
    cout<<endl;
}