// 图的深度优先搜索(采用邻接表存储).cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define MAX 100
using namespace std;
struct edgeNode
{
int no; //边端的序号
char info; //边端的名称
struct edgeNode * next; //下一个
};
struct vexNode
{
char info; //节点名称
struct edgeNode *link; //与之相连的端点
};
//存储节点信息
vexNode adjlist[MAX];
//访问标志
bool visited[MAX];
//建立邻接表存储
void createGraph(vexNode *adjlist)
{
int n,e;
cout<<"请输入节点数:";
cin>>n;
cout<<"请输入边数:";
cin>>e;
int i;
for(i=1;i<=n;i++)
{
cout<<"请输入节点"<<i<<"的名称:";
cin>>adjlist[i].info;
adjlist[i].link = NULL;
}
edgeNode *p1,*p2;
int v1,v2;
for(i=1;i<=e;i++)
{
cout<<"请输入边"<<i<<"的二端的节点序号:";
cin>>v1>>v2;
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p2 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = v1;
p1->info = adjlist[v1].info;
p1->next = adjlist[v2].link;
adjlist[v2].link = p1;
p2->no = v2;
p2->info = adjlist[v2].info;
p2->next = adjlist[v1].link;
adjlist[v1].link = p2;
}
}
//深度优先搜索无向无权图
void DFS(vexNode *adjlist,bool *visited,int v1)
{
visited[v1] = true;
cout<<"节点"<<v1<<",名称"<<adjlist[v1].info<<endl;
edgeNode *p;
p = adjlist[v1].link;
while(p!=NULL)
{
if(!visited[p->no])
DFS(adjlist,visited,p->no);
p=p->next;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数:";
cin>>cases;
while(cases--)
{
//访问标志清空
int i;
for(i=1;i<MAX;i++)
visited[i] = false;
//创建邻接表
createGraph(adjlist);
//深度优先搜索
int v1;
cout<<"请输入从哪个序号的点开始搜索:";
cin>>v1;
cout<<"深度优先搜索次序为:"<<endl;
DFS(adjlist,visited,v1);
}
system("pause");
return 0;
}
------------------------------------------------------程序测试-------------------------------------------------
请输入案例的个数:1
请输入节点数:8
请输入边数:10
请输入节点1的名称:r
请输入节点2的名称:s
请输入节点3的名称:t
请输入节点4的名称:u
请输入节点5的名称:v
请输入节点6的名称:w
请输入节点7的名称:x
请输入节点8的名称:y
请输入边1的二端的节点序号:1 2
请输入边2的二端的节点序号:1 3
请输入边3的二端的节点序号:2 4
请输入边4的二端的节点序号:3 5
请输入边5的二端的节点序号:3 6
请输入边6的二端的节点序号:5 6
请输入边7的二端的节点序号:5 8
请输入边8的二端的节点序号:6 7
请输入边9的二端的节点序号:6 8
请输入边10的二端的节点序号:7 8
请输入从哪个序号的点开始搜索:2
深度优先搜索次序为:
节点2,名称s
节点4,名称u
节点1,名称r
节点3,名称t
节点6,名称w
节点8,名称y
节点7,名称x
节点5,名称v
请按任意键继续. . .
分享到:
相关推荐
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 注: 1.代码共182行。 2.代码经过多次编译运行,无错误。
无向图的邻接矩阵存储及输出无向图的邻接矩阵存储及输出
设计一个有向图和一个无向图,使用邻接矩阵和邻接表存储结构,完成在这两种存储结构下有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 三、实验要求: 1. 根据实验内容编程,画出你所设计的图,...
图的存储可采用邻接矩阵或邻接表; 打印出每一个顶点信息和邻接矩阵或邻接表 注意问题: 有向图,无向图,有向网,无向网任选一种。 2、深度优先遍历以及广度优先遍历 问题描述:从键盘输入数据建立图并打印深度...
以邻接表为存储结构,实现创建图、销毁图、查找顶点、获取顶点值、顶点赋值、获得第一邻接点、获得下一邻接点、插入顶点、删除顶点、插入弧、删除弧、深度优先搜索遍历、广深度优先搜索遍历等操作 注: 1.系统设计 2...
" " " "3、设计一个程序exp8-3.cpp,采用邻接表存储图,并输出图8.1(a)中从指定顶点1出 " "发的所有深度优先遍历序列。 " " " "(2)实验方法: " "1、综合运用课本所学的知识,用不同的算法实现在不同的程序功能。 ...
1.建立无向网的邻接表存储结构:要求:从键盘输入无向网的顶点数和边数;然后以"顶点1,顶点2,权值"的方式输入无向网的各边。 2.输出邻接表:输出形式为:顶点:顶点编号 权值->顶点编号 权值->… 3.求出无向网...
(2)能够在邻接矩阵和邻接表存储结构上对(有向和无向)图进行深度优先(递归和非递归都要求)和广度优先搜索 (3)能够存储和显示相应的搜索结果(深度优先或广度优先生成森林(或生成树)、深度优先或广度优先序列和...
一.实验项目要求 1.熟练掌握图的两种...可以是邻接矩阵或者邻接表存储。 2. 使用深度或广度优先搜索对图中顶点进行遍历输出。 3. 采用普里姆算法或克鲁斯卡尔算法求出使总造价最少的子图,即最小生成树。(选做题)
2、实现连通和非连通的无向图的深度优先和广度优先遍历; 3、要求利用栈实现无向图的深度优先遍历; 4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集; 5、用凹入表打印...
1.4 C++程序的编写和实现 1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++的数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 字符常量 2.2.4 符号常量 2.3 变量 2.3.1 什么是变量 2.3.2 ...
以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。
图遍历的演示 题目:试设计一个程序,演示在连通和非连通的无向图上访问全部结点的操作 班级:*** 姓名:*** 学号:*** 完成日期: 一、需求分析 1、以邻接多重表为存储结构; 2、实现连通和非连通的无向图的深度优先...
1.4 C++程序的编写和实现 1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++的数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 字符常量 2.2.4 符号常量 2.3 变量 2.3.1 什么是变量 2.3.2 ...
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界...
12.5 无向图和有向图的描述 371 12.5.1 邻接矩阵 371 12.5.2 邻接压缩表 373 12.5.3 邻接链表 374 12.6 网络描述 375 12.7 类定义 376 12.7.1 不同的类 376 12.7.2 邻接矩阵类 377 12.7.3 扩充Chain类 380 12.7.4 类...
12.5 无向图和有向图的描述 371 12.5.1 邻接矩阵 371 12.5.2 邻接压缩表 373 12.5.3 邻接链表 374 12.6 网络描述 375 12.7 类定义 376 12.7.1 不同的类 376 12.7.2 邻接矩阵类 377 12.7.3 扩充Chain类 380 12.7.4 类...
12.5 无向图和有向图的描述 371 12.5.1 邻接矩阵 371 12.5.2 邻接压缩表 373 12.5.3 邻接链表 374 12.6 网络描述 375 12.7 类定义 376 12.7.1 不同的类 376 12.7.2 邻接矩阵类 377 12.7.3 扩充Chain类 380 12.7.4 类...
1.用邻接矩阵或者邻接表定义图的应用 2.实现图的基本操作: 构造,销毁 广度,深度优先搜索 <3> 图的打印 3.图的应用: <1> 最小生成树 <2> 有向无环图的拓扑排序 <3> 有向无环图的关键路径 注意:图的应用中是...