

#include <iostream>
#include <string.h>
using namespace std;
const int MVNum = 100; //最大顶点数
const int OK = 1;
typedef char VerTexType; //设顶点的数据类型为字符型
typedef int ArcType;
typedef struct {
VerTexType vexs[MVNum]; //顶点表 字符型
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的顶点数和边数
}AMGraph; //Adjacency Matrix Graph 邻接矩阵图
int LocateVex(AMGraph G, VerTexType u)
{
int i;
for (i = 0; i < G.vexnum; i++)
if (u == G.vexs[i])
return i;
return -1;
}
int CreateUDN(AMGraph& G) //采用邻接矩阵表示法,创建无向网G
{
int i, j, k;
cout<<"请输入顶点数和边数:";
cin >> G.vexnum >> G.arcnum; //输入总的顶点数和边数
cout << "请输入各个顶点:";
for (i = 0; i < G.vexnum; i++)
{
cin >> G.vexs[i]; //依次输入各点 字符型
}
for (i = 0; i < G.vexnum; i++) //初始化邻接矩阵为全部0
for (j = 0; j < G.vexnum; i++)
G.arcs[i][j] = 0;
cout << "输入一条边的两个顶点:";
for (k = 0; k < G.arcnum; k++) //输入邻接矩阵
{
VerTexType v1, v2;
cin >> v1 >> v2; //输入两条边的顶点 字符型
i = LocateVex(G, v1);
j = LocateVex(G, v2); //确定v1.v2在G中的位置
G.arcs[i][j] = 1;
}
return OK;
}//CreateUDN
int visited[MVNum] = { 0 };
void DFS(AMGraph G, int v)
{
cout << G.vexs[v];//访问第v个顶点
visited[v] = 1;
for (int i = 0; i < G.vexnum; i++)//依次检查邻接矩阵v所在的行
{
if ((G.arcs[v][i] == 1) && (visited[i] == 0)) //邻接矩阵不为0,而且没有被访问过的
{
DFS(G, i);
}
}
}
int main()
{
AMGraph G;
CreateUDN(G);
DFS(G, 0);
return 0;
}