int LocateVex(ALGraph G, char ch)
{
for(int i = 0 ; i< G.vexnum; ++i)
{
if(G.vertices[i].data == ch)
{
return i;
}
}
return -1;
}
char findNode(ALGraph G, int index)
{
return G.vertices[index].data;
}
//建图
void CreateGraph(ALGraph &G)
{
cout << "请输入图的顶点数和边数:"<<endl;
cin >> G.vexnum >> G.arcnum;
cout << "请输入顶点:"<<endl;
char ch;
for(int i = 0; i<G.vexnum; ++ i)
{
cin >>ch;
G.vertices[i].data = ch;
G.vertices[i].firstarc = NULL;
}
cout << "请输入图的各边及边的权重:"<<endl;
char start, end;
int weight;
for(int i = 0; i < G.arcnum; ++i)
{
cin >> start >>end>> weight;
int startPostion = LocateVex(G, start);
int EndPostion = LocateVex(G,end);
ArcNode *s = new ArcNode;
s->adjvex = EndPostion;
s->nextarc = G.vertices[startPostion].firstarc;
G.vertices[startPostion].firstarc = s;
}
}
//遍历该图
void printGraph(ALGraph G)
{
for(int i = 0; i < G.vexnum; ++i)
{
ArcNode *s = G.vertices[i].firstarc;
while(s != NULL)
{
cout << G.vertices[i].data << " "<< findNode(G,s->adjvex)<<endl;
s = s->nextarc;
}
}
}
//深度优先遍历图
bool visited[MAX_VERTEX_NUM] = {false};
void DFS(ALGraph G, int v)
{
visited[v] = true;
cout << findNode(G,v)<<"->";
ArcNode *w = G.vertices[v].firstarc;
while(w != NULL)
{
int wIndex = w->adjvex;
if(!visited[wIndex])
{
DFS(G,wIndex);
}
w = w->nextarc;
}
}
//广度优先遍历图
void BFS(ALGraph G)
{
int u, w;
bool flag[MAX_VERTEX_NUM]={false};
ArcNode *s;
char e;
SqQueue Q;
InitQueue(Q);
for(int v = 0; v < G.vexnum; ++v)
{
if(!flag[v])
{
flag[v] = true;
cout << findNode(G,v) <<"->";
EnQueue(Q,findNode(G,v));
while(!QueueEmpty(Q))
{
e = DeQueue(Q);
u = LocateVex(G,e);
s = new ArcNode;
s = G.vertices[u].firstarc;
while(s != NULL)
{
w = s->adjvex;
if(flag[w] == false)
{
flag[w] = true;
cout << findNode(G, w)<<"->";
EnQueue(Q,findNode(G,w));
}
s=s->nextarc;
}
}
}
}
}
int main()
{
ALGraph graph;
CreateGraph(graph);
char ch;
cout <<"遍历该图的:"<<endl;
printGraph(graph);
//深度优先遍历啊该图
cout<< "请输入起始点:" << endl;
cin >> ch;
int pos = LocateVex(graph, ch);
DFS(graph,pos);
cout <<endl;
//广度优先遍历图
cout << "广度优先遍历此图的结果是:"<<endl;
BFS(graph);
return 0;
}