#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<iostream>
using namespace std;
#define VerStrLen 5
#define MaxVnum 30

typedef struct ArcNode{ //表结点
int    weight;
struct ArcNode *nextarc;
}ArcNode;
typedef struct Vnode{ //头结点
char     *data;
ArcNode  *firstarc;
typedef struct {//邻接表
int      vexnum,arcnum;
}ALGraph;

bool visited[MaxVnum];

int Locate(ALGraph G, char *s)
{
int i;

for(i=0; i<G.vexnum; i++){
if(!strcmp(s, G.vertices[i].data))
return i;
}
return -1;
}

{
FILE *fp;
int i,j;

if((fp = fopen("Graph.txt","r"))==NULL) {
printf("Could not open Graph.txt file\n");
exit(0);
}

fscanf(fp, "%d %d\n", &ALG.vexnum, &ALG.arcnum);
for(i=0; i<ALG.vexnum; i++){
ALG.vertices[i].data = (char *)malloc(VerStrLen*sizeof(char));
fscanf(fp, "%s", ALG.vertices[i].data);
ALG.vertices[i].firstarc = NULL;
}
for(int k = 0; k < ALG.arcnum;++k){        		//输入各边，构造邻接表
char v1[VerStrLen] , v2[VerStrLen];
fscanf(fp, "%s %s\n", v1, v2);                		//输入一条边依附的两个顶点
i = Locate(ALG, v1);  j = Locate(ALG, v2);
//确定v1和v2在G中位置，即顶点在G.vertices中的序号

ArcNode *p1=new ArcNode;               	//生成一个新的边结点*p1
p1->nextarc= ALG.vertices[i].firstarc;  ALG.vertices[i].firstarc=p1;
//将新结点*p1插入顶点vi的边表头部

ArcNode *p2=new ArcNode;                //生成另一个对称的新的边结点*p2
p2->nextarc= ALG.vertices[j].firstarc;  ALG.vertices[j].firstarc=p2;
//将新结点*p2插入顶点vj的边表头部
}//for
fclose(fp);
}

void DFS(ALGraph G, int v)
{
ArcNode *p;

visited[v] = true;
printf("%s  ", G.vertices[v].data);
for(p=G.vertices[v].firstarc; p; p=p->nextarc){
}
}

void DFSTraverse(ALGraph G, int i)
{
int v;

for(v=0; v<G.vexnum; ++v)
visited[v] = false;
DFS(G, i);
for(v=0; v<G.vexnum; ++v)
if(visited[v]==false)
DFS(G, v);
}

void BFSTraverse(ALGraph G, int i)
{
int v, u;
int *Q;
int front=0, rear=0;
ArcNode *p;

for(v=0; v<G.vexnum; ++v)
visited[v] = false;
Q = (int *)malloc(G.vexnum*sizeof(int));
if(visited[i]==false){
Q[rear++] = i;
visited[i] = true;
printf("%s  ", G.vertices[i].data);
while(front != rear){
u = Q[front++];
for(p=G.vertices[u].firstarc; p; p=p->nextarc){
}
}
}
}
for(v=0; v<G.vexnum; ++v)
if(visited[v]==false){
Q[rear++] = v;
visited[v] = true;
printf("%s  ", G.vertices[v].data);
while(front != rear){
u = Q[front++];
for(p=G.vertices[u].firstarc; p; p=p->nextarc){
}
}
}
}
free(Q);
}

int main()
{
ALGraph ALG;
int i, j, v,index;
cout << "无向连通图ALG创建完成！" << endl << endl;
char c[VerStrLen];
cout << "请输入遍历连通图的起始点：";
cin >> c;
index = Locate(ALG, c);
while(index == -1){
cout << "该点不存在，请重新输入！" << endl;
cout << "请输入遍历连通图的起始点：";
cin >> c;
index = Locate(ALG, c);
}
//邻接表深度优先搜索
printf("邻接表深度优先搜索序列: ");
DFSTraverse(ALG, index);
printf("\n");

//邻接表广度优先遍历
printf("邻接表广度优先搜索序列: ");
BFSTraverse(ALG, index);
printf("\n");
}