深度优先搜索
#include "stdafx.h"
#include"iostream"
using namespace std;
const int MaxV=20;
struct Vertex
{
char name;
bool visited;
};
struct graph
{
int n;
int c[MaxV][MaxV];
Vertex V[MaxV];
};
void DFSk(graph &g, int k)
{ g.V[k].visited=1;
cout<<g.V[k].name<<" ";
for (int i=0;i<g.n;i++)
if (g.c[k][i]==1 && g.V[i].visited==0) DFSk(g,i);
}
void DFS (graph &g) //考虑g的连通性
{ for (int i=0;i<g.n;i++)
{
if (g.V[i].visited==0)
DFSk(g,i);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
graph tu;
cout<<"请输入图的顶点数";
cin>>tu.n;
for(int i=0;i<tu.n;i++)
{
cout<<"请输入第"<<i+1<<"个顶点";
cin>>tu.V[i].name;
}
cout<<"请输入图的邻接矩阵"<<endl;
for (int i=0;i<tu.n;i++)
{
for (int j=0;j<tu.n;j++)
{cout<<"c["<<i<<"]["<<j<<"]=";
cin>>tu.c[i][j];
}
tu.V[i].visited=0;
}
DFS(tu);
return 0;
}