邻接矩阵和图的深度优先遍历

#include<stdio.h>

#include<iostream.h>

#define MaxInt 32767

#define MVNum 100

#define OK 1

typedef char VerTexType;

typedef int ArcType;

typedef int Status;

typedef struct

{

VerTexType vexs[MVNum];

ArcType arcs[MVNum][MVNum];

int vexnum,arcnum;

}AMGraph;

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)//采用邻接矩阵创建无向网

{

int i,j,w,k;

VerTexType v1,v2;

cout<<"输入顶点数及边数"<<endl;

cin>>G.vexnum>>G.arcnum;

cout<<"依次输入点的信息"<<endl;

for(i=0;i<G.vexnum;++i)

cin>>G.vexs[i];

for(i=0;i<G.vexnum;++i)

for(j=0;j<G.vexnum ;++j)

           G.arcs[i][j]=0;

cout<<"输入边依附的顶点及权值"<<endl;

for(k=0;k<G.arcnum ;++k)

{

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];

}

cout<<"输出邻接矩阵"<<endl;

for(i=0;i<G.vexnum;++i)

{

    for(j=0;j<G.vexnum ;++j)

cout<<G.arcs[i][j]<<" ";

    cout<<endl;

}

return OK;

}

bool visited[MVNum];

void DFS_AM(AMGraph G,int v)//采用邻接矩阵图的深度优先搜索遍历

{

int w;

cout<<G.vexs[v]<<endl;

visited[v]=true;

for(w=0;w<G.vexnum;w++)

if((G.arcs[v][w]!=0)&&(!visited[w]))

DFS_AM(G,w);

}

void main()

{

      int v;

AMGraph G;

cout<<"初始化图"<<endl;

CreateUDN(G);

       cout<<"输入遍历开始的位置"<<endl;

cin>>v;

cout<<"遍历的结果是"<<endl;

DFS_AM(G,v)

}