用DEVC++写一个程序,依次从有向图中的每个顶点深度优先搜索遍历操作;邻接表作为存储结构。算法思想: (1) 定义图的链式存储结构; (2) 创建有向图,采用邻接表表示(调用CreateUDG函数实现),具体实现如下: 输入图的顶点数和边数; 依次输入顶点的信息存入顶点表中,每个表头结点的指针域初始化为NULL; 构造邻接表;(需调用LocateVex函数获取顶点在顶点表中的下标) (3) 依次从每个顶点进行深度优先搜索,并输出访问序列(调用DFSTraverse函数实现;另需调用相关函数实现获取第一个和下一个邻接点的操作)。 注意: 顶点数据仅为1个数字或1个字符; 顶点表数组下标从0开始; 在每个顶点的边表中插入结点时,确保此顶点的各邻接点域的值从大到小排序。 输入说明: 第一行输入图的顶点数n和边数m; 第二行依次输入n个顶点的数据; 接下来m行的每行输入一条边的信息。 输出说明: 输出n行,每行输出从第i(0≤i<n)个顶点深度优先搜索的访问序列,序列中的连通分量用{}括起来,无空格间隔,{}为英文半角的符号。
时间: 2023-07-16 07:15:12 浏览: 92
很高兴为您提供代码实现,以下是DEVC++实现的代码:
```c++
#include <iostream>
using namespace std;
#define MAX_VERTEX_NUM 20
typedef char VertexType;
typedef struct ArcNode{
int adjvex; //邻接点在顶点表中的位置
struct ArcNode *nextarc; //指向下一个邻接点的指针
}ArcNode;
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一个邻接点的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;
int LocateVex(ALGraph G, VertexType x){
for(int i=0; i<G.vexnum; i++){
if(G.vertices[i].data == x){
return i;
}
}
return -1;
}
void CreateALGraph(ALGraph &G){
cout << "请输入顶点数和边数:" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "请输入" << G.vexnum << "个顶点的信息:" << endl;
for(int i=0; i<G.vexnum; i++){
cin >> G.vertices[i].data;
G.vertices[i].firstarc = NULL;
}
for(int k=0; k<G.arcnum; k++){
VertexType v1, v2;
cout << "请输入一条边依附的两个顶点:" << endl;
cin >> v1 >> v2;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
if(i==-1 || j==-1){
cout << "输入顶点信息有误,请重新输入!" << endl;
k--;
}else{
ArcNode *p = new ArcNode;
p->adjvex = j;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
}
}
int visited[MAX_VERTEX_NUM]; //全局数组,记录顶点的访问情况
void DFS(ALGraph G, int v){
visited[v] = 1;
cout << G.vertices[v].data;
ArcNode *p = G.vertices[v].firstarc;
while(p != NULL){
int w = p->adjvex;
if(visited[w] == 0){
DFS(G, w);
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph G){
cout << "深度优先搜索遍历序列:" << endl;
for(int i=0; i<G.vexnum; i++){
visited[i] = 0;
}
for(int i=0; i<G.vexnum; i++){
if(visited[i] == 0){
cout << "{";
DFS(G, i);
cout << "}" << endl;
}
}
}
int main(){
ALGraph G;
CreateALGraph(G);
DFSTraverse(G);
return 0;
}
```
其中,CreateALGraph函数实现了有向图的邻接表存储结构的构造;LocateVex函数用于获取顶点在顶点表中的下标;DFS函数实现了深度优先搜索遍历操作;DFSTraverse函数依次从每个顶点进行深度优先搜索,并输出访问序列,其中使用visited数组记录顶点的访问情况。最后,在主函数中调用CreateALGraph函数和DFSTraverse函数完成程序的执行。
阅读全文