6-5 jmu-ds-图邻接表操作
分数 10
作者 林丽
单位 集美大学
请你以邻接表存储结构实现无向图的深度遍历、无向图广度遍历。
你要实现的3个函数接口定义：
void CreateAdj(AdjGraph *&G,int n,int e); //创建图邻接表
void DFS(AdjGraph *G,int v);//v节点开始深度遍历
void BFS(AdjGraph *G,int v); //v节点开始广度遍历
G表示邻接表存储的图结构，v表示从v节点开始深度遍历。
裁判测试程序样例：
#define MAXV 20
#include
#include
#include
#include
using namespace std;
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
int info; //该边的相关信息，如权重
} ArcNode; //边表节点类型
typedef int Vertex;
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef VNode AdjList[MAXV];
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} AdjGraph;
int visited[MAXV];
int flag=0;
void CreateAdj(AdjGraph *&G,int n,int e); //创建图邻接表
void DFS(AdjGraph *G,int v);//v节点开始深度遍历
void BFS(AdjGraph *G,int v); //v节点开始广度遍历
int main()
{
AdjGraph G;
int n,e,i,v;
cin>>n>>e;
CreateAdj(G,n,e);
cin>>v;
for(i=1;i<=G->n;i++) visited[i]=0;
cout<<"dfs:";
DFS(G,v);
cout<
for(i=1;i<=G->n;i++) visited[i]=0;
cout<<"bfs:";
BFS(G,v) ;
return 0;
}
/
输入格式:
输入在第一行给出2个整数n（0 < n <=20）、e（0 < e <=380），分别是无向图的顶点数、边数.
随后e行，每行给出一条边的两个端点的编号。(顶点编号：1--n)
输入在最后一行，输出深度遍历和广度遍历的起始顶点。（顶点编号：1--n）
输出格式:
深度遍历和广度遍历结果。要求顶点序列间空格隔开，尾部不带空格。
输入样例:
6 10
1 2
1 3
1 4
2 3
2 5
3 4
3 5
3 6
4 6
5 6
2
Figure_1.png
输出样例:
dfs:2 5 6 4 3 1
bfs:2 5 3 1 6 4
你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答
本次提问扣除的有问必答次数，已经为您补发到账户，我们后续会持续优化，扩大我们的服务范围，为您带来更好地服务。