1、编写图的基本操作算法(可如下所示函数,也可自定义,能实现即可):0算法62采用邻接表表示法创建无向图vald CreateUDG(ALGraph&G)②算法6.6深度优先搜索遍历void DFSCALGraphG, intv) 2、编写一个主函数,调用上述算法,实现采用邻接表表示图的深度优先搜索遍历。
时间: 2024-03-05 10:54:42 浏览: 56
好的,我会根据您的要求进行回答。针对您的问题,我提供以下代码:
```
#include<iostream>
#include<cstring>
using namespace std;
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
#define INFINITY 65535
typedef char VertexType;
typedef int InfoType;
typedef int Status;
typedef struct ArcNode{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数和弧数
}ALGraph;
//建立无向图的邻接表存储结构
Status CreateUDG(ALGraph &G){
int i,j,k;
char v1,v2;
ArcNode *p;
cout<<"请输入顶点数和弧数:";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入顶点信息:";
for(i=0;i<G.vexnum;i++){
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
for(k=0;k<G.arcnum;k++){
cout<<"请输入弧(vi,vj)的顶点序号:";
cin>>v1>>v2;
for(i=0;i<G.vexnum;i++){
if(G.vertices[i].data==v1) break;
}
for(j=0;j<G.vexnum;j++){
if(G.vertices[j].data==v2) break;
}
p=new ArcNode;
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
p=new ArcNode;
p->adjvex=i;
p->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p;
}
return OK;
}
//深度优先搜索遍历
void DFS(ALGraph G,int v,int visited[]){
visited[v]=1;
cout<<G.vertices[v].data<<" ";
for(ArcNode *p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc){
if(!visited[p->adjvex]){
DFS(G,p->adjvex,visited);
}
}
}
int main(){
ALGraph G;
CreateUDG(G);
int visited[MAX_VERTEX_NUM];
memset(visited,0,sizeof(visited));
cout<<"深度优先搜索遍历序列为:";
for(int i=0;i<G.vexnum;i++){
if(!visited[i]){
DFS(G,i,visited);
}
}
return 0;
}
```
其中,CreateUDG函数用于建立邻接表存储的无向图,DFS函数用于实现深度优先搜索遍历,main函数用于测试。
阅读全文