邻接矩阵表示图的深度优先搜索遍历
程序员文章站
2022-05-19 19:53:23
...
这次用了点c++,用c的话需要考虑吞字符,一开始没想到,写完了也就没改。
运行结果:
#include <iostream>
using namespace std;
#define MaxInt 32767
#define MVNum 100
#define OK 1;
bool visited[MVNum];
typedef int Status;
typedef char VerTexType;
typedef int ArcType;
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])
break;
}
return i;
}
Status CreateUDN(AMGraph &G)
{
int i,j,k,w;
char v1,v2;
printf("请输入顶点数 总边数:");
scanf("%d,%d",&G.vexnum,&G.arcnum);
printf("请输入顶点信息:");
for(i=0;i<G.vexnum;++i)
{
cout<<"第"<<i+1<<"个顶点:";
cin>>G.vexs[i];
}
for(i = 0;i < G.vexnum ; i++)
for(j = 0;j < G.vexnum ; j++)
G.arcs [i][j] = MaxInt;
printf("请输入一条边依附的顶点及其权值(例:a,b,1 a,c,2):");
for(k = 0;k < G.arcnum ; k++)
{
cout<<"第"<<k+1<<"条边依附的顶点及权值:";
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];
}
return OK;
}
void DFS_AM(AMGraph G,int v)
{
int w;
cout<<G.vexs[v];
visited[v] = true;
for(w = 0; w < G.vexnum;w++ )
if((G.arcs [v][w]!=0)&&(!visited[w]))
DFS_AM(G,w);
}
int main()
{
int v,i,j;
AMGraph G;
CreateUDN(G);
cout << "创建的无向网如下" << endl;
for(i = 0 ; i < G.vexnum ; ++i)
{
for(j = 0; j < G.vexnum; ++j)
{
if(G.arcs[i][j] != MaxInt)
cout << G.arcs[i][j] << "\t";
else
cout << "∞" << "\t";
}
cout<<endl<<endl;
}
for(int i=0;i<G.vexnum;i++)
visited[i]=false;
cout<<"从哪个顶点开始DFS?"<<endl;
cin>>v;
DFS_AM(G,v);
cout <<endl;
return 0;
}