Question

图的遍历

根据从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索（实验类型：验证型）
1）问题描述：在主程序中提供下列菜单：
1…图的建立
2…深度优先遍历图
3…广度优先遍历图
0…结束
2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程：
CreateGraph(): 按从键盘的数据建立图
DFSGrahp()：深度优先遍历图
BFSGrahp()：广度优先遍历图

Answer 1

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

//Graph.h
/*typedef double AdjMatrix[MaxN][MaxN]; //赋权图
typedef struct //邻接矩阵表示的图的数据类型
{ int Vnum; //图中顶点数
AdjMatrix Arcs;
}Graph_M; */
typedef struct AcrNode //邻接表的表结点
{ int adjvex; //邻接表的顶点序号
double weight; //边(弧)上的权值
struct AcrNode * nextarc; //下一个邻接顶点
}EdgeNode;
typedef struct VNode //邻接表的头结点
{
char data; //顶点表示的数据, 以一个字符表示
EdgeNode * firstarc; //指向第一条依附于该顶点的弧的指针
}AdjList;
typedef struct //邻接链表表示的图的数据类型
{ int Vnum;
AdjList *Vertices;
}Graph_A;

Graph_A * CreatGraph_A();
void SaveGraph_A(Graph_A * graph);
void Dfs(Graph_A G, int i);
void Search(Graph_A * G, int start, int end, int &p, double len);
void Display();
extern int MaxN;
extern int * L;
extern int * T;
extern double len_T, len_L;

int main()
{
Graph_A * graph;
int choice;
char str[20];
while(1)
{
do{
cout << endl << endl;
cout << "/*/*/*/*/*/*/*/*/*/*/*/*" << endl;
cout << "1.创建新图" << endl;
cout << "2.退出" << endl;
cout << "/*/*/*/*/*/*/*/*/*/*/*/*" << endl;
cout << "按数字键选择对应操作: ";
cin >> str;
choice = atoi(str);
cout << endl;
switch(choice)
{
case 1:
graph = CreatGraph_A();
case 2:
return 0;
default:
choice = 0;
cout << "输入错误" << endl;
}
}while(!choice);

cout << endl << endl;
cout << "开始寻找最短路径(输入0,0退出)......" << endl << endl;
while(1)
{
int start, end;
for(start=1;start<=MaxN;start++)
for(end=1;end<=MaxN;end++)
Search(graph, start, end, p, 0.0);
Display();
}//while
}//while
return 0;
}

int MaxN = 100;

/*
* 函数功能: 建立邻接链表表示的图
* 输入参数: NULL
* 输出参数: Graph_A 邻接链表表示的图*/
Graph_A * CreatGraph_A()
{ //顶点数
cout << "输入顶点数: ";
cin >> MaxN;
Graph_A * graph = (Graph_A *)malloc(sizeof(Graph_A));
EdgeNode temp;
EdgeNode * tp;
graph->Vertices = (AdjList *)malloc(MaxN * sizeof(AdjList));
graph->Vnum = MaxN;
for(int i=0; i<MaxN; i++)
{ graph->Vertices[i].data = i+1;
graph->Vertices[i].firstarc = NULL;
cout << "输入与第" << i+1 << "个结点相连的结点信息(结点编号为0表示结束):" << endl;
while(1)
{ cout << "输入结点编号: ";
cin >> temp.adjvex;
if(!temp.adjvex)
{
break;
}
cout << "输入路径长度: ";
cin >> temp.weight;
/*double t;
cout << "选择倍率: ";
cin >> t;
temp.weight *= t;*/
tp = (EdgeNode *)malloc(sizeof(EdgeNode));
*tp = temp;
tp->nextarc = graph->Vertices[i].firstarc;
graph->Vertices[i].firstarc = tp;
}
}
return graph;
}

void SaveGraph_A(Graph_A * graph)
{
FILE * fp;
EdgeNode * tp;
char g_name[50];
cout << "输入保存图的文件名: ";
cin >> g_name;
if(!(fp = fopen(g_name, "w")))
{
return;
}
fwrite(&(graph->Vnum), sizeof(int), 1, fp);
fputc('\n', fp);
for(int i=0; i<MaxN; i++)
{
fwrite(&(graph->Vertices[i].data), sizeof(char), 1, fp);
fputc('\n', fp);

tp = graph->Vertices[i].firstarc;
while(tp)
{
fwrite(tp, sizeof(EdgeNode), 1, fp);
//fwrite(&(tp->adjvex), sizeof(int), 1, fp);
//fwrite(&(tp->weight), sizeof(double), 1, fp);
fputc('c', fp);
tp = tp->nextarc;
}
tp = (EdgeNode *)malloc(sizeof(EdgeNode));
tp->adjvex = 0;
tp->nextarc = NULL;
tp->weight = 0;
fwrite(tp, sizeof(EdgeNode), 1, fp);
fputc('\n', fp);
}
fclose(fp);
}

int * visited = (int *)malloc(MaxN * sizeof(int));
/*
* 函数功能: 深度优先遍历邻接链表表示的图
* 输入参数: Graph_A G 邻接链表表示的图
int i 出发结点
* 输出参数: void
*/
void Dfs(Graph_A G, int i)
{
EdgeNode * t;
int j;
printf("%d", i+1); //访问序号为i的顶点
visited[i] = 1; //序号为i的结点已经访问过
t = G.Vertices[i].firstarc;
//取顶点i的第一个邻接的顶点

while(t) //检查所有与顶点i相邻接的顶点
{
j = t->adjvex; //顶点j为顶点i的一个邻接顶点
if(!visited[j]) //若j从未被访问过
{
Dfs(G, j); //从顶点j出发进行深度优先遍历
}
t = t->nextarc; //取顶点i的下一个邻接顶点
}
}

/*
* 函数功能: 寻找两点间最短路径
* 输入参数: Graph_A G 邻接链表表示的图
int start 出发结点
int end 目的结点
int p 当前位置
double len 进入函数前len_T增加的量
* 输出参数: void
*/
int * L = (int *)malloc((MaxN+1) * sizeof(int));
int * T = (int *)malloc((MaxN+1) * sizeof(int));
double len_T, len_L;
void Search(Graph_A * G, int start, int end, int &p, double len)
{
if(start == end || len_T >= len_L)
{
if(len_T < len_L)
{
len_L = len_T;
for(int i=0; i<p; i++)
{
L[i] = T[i];
}
L[p] = 0;
}
len_T -= len;
p--;
return;
}

EdgeNode * tp = (EdgeNode *)malloc(sizeof(EdgeNode));
tp = G->Vertices[start-1].firstarc;

while(tp)
{
int b = 1;
for(int i=0; i<p; i++)
{
if(T[i] == tp->adjvex)
{
b = 0;
break;
}
}
if(b)
{
len_T += tp->weight;
T[p++] = tp->adjvex;
Search(G, tp->adjvex, end, p, tp->weight);
}
tp = tp->nextarc;
}

p--;
len_T -= len;
return;
}

void Display()
{
cout << "路径: ";
for(int i=0; L[i]; i++)
{
cout << L[i] << " ";
}
cout << endl << "长度: " << len_L << endl << endl;
}