`
pleasetojava
  • 浏览: 727678 次
  • 性别: Icon_minigender_2
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

无向图的深度优先搜索(采用邻接表存储)C++实现

 
阅读更多

// 图的深度优先搜索(采用邻接表存储).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
请按任意键继续. . .

分享到:
评论

相关推荐

    C++无向图深度优先和广度优先遍历(编译可运行).rar

    以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 注: 1.代码共182行。 2.代码经过多次编译运行,无错误。

    假设图中数据元素类型是字符型,请采用邻接矩阵或邻接表实现图的以下基本操作: (1)构造图(包括有向图、有向网、无向图、无向网); (2)根据深度优先遍历图。

    这包括构造有向图、有向网、无向图和无向网,以及进行深度优先遍历。首先,我们来理解图和网之间的区别。 **图和网的区别**: 图是由顶点和连接顶点的边构成的数据结构。网则是图的一种特殊形式,它包含了带权值的...

    无向图的邻接矩阵存储及输出

    ### 无向图的邻接矩阵存储及输出详解 在计算机科学中,图是一种重要的数据结构,用于表示对象之间的关系。图由顶点(或节点)和边组成,其中边可以是有向的或无向的。本文将详细介绍无向图的邻接矩阵存储方式以及...

    图的遍历(包括深度 广度遍历 利用邻接矩阵 利用邻接表)

    而在邻接表表示的图中,DFS通常采用栈的数据结构来辅助实现。DFS的优势在于空间效率,对于稠密图(边数接近顶点数的平方)来说,邻接矩阵的存储效率较低,而邻接表则更节省空间。 接下来,我们讨论广度优先搜索(BFS...

    无向图_C语言_

    总之,这个项目涵盖了无向图的邻接表存储、深度优先搜索以及先序遍历等核心概念,是学习和实践图论及C语言编程的好例子。通过这个项目,开发者可以深入了解图的存储和遍历算法,并提升解决复杂问题的能力。

    深度优先算法--邻接表

    对于无向图,邻接表需要两个边节点来表示一条边,因为每条边连接两个顶点,所以节点数量为2e。而有向图只需一个边节点,因此节点数量为e。建立邻接表的时间复杂度通常为O(n*e),但如果顶点信息可以直接用顶点的下标...

    图的邻接表存储实现及深度优先遍历

    通过这个实验,学生可以深入理解图的邻接表存储和深度优先遍历的概念,并掌握C++实现这两种操作的技术。这对于学习图论和算法分析至关重要,因为这两种操作在解决许多实际问题时都非常有用,例如网络路由、文件系统...

    图的建立和遍历的c++实现(邻接表储存)

    总结起来,本示例程序提供了用C++实现图的邻接表存储、图的建立以及DFS和BFS遍历的方法。通过学习和理解这段代码,你将能够更好地掌握图这种数据结构及其操作,这对于理解和解决许多实际问题,特别是在算法和数据...

    图的邻接矩阵和邻接表存储结构(C++)

    总结,理解和实现图的邻接矩阵和邻接表存储结构是学习数据结构和算法的重要部分。它们在许多领域,如路由算法、社交网络分析和图形渲染等,都有广泛的应用。通过C++实现这两种结构,可以加深对图操作的理解,并为...

    图的邻接表实现.rar

    在实际应用中,使用邻接表实现的图可以有效地进行深度优先搜索(DFS)和广度优先搜索(BFS),并支持多种图算法,如最短路径计算(Dijkstra算法或Floyd-Warshall算法)、拓扑排序等。此外,由于类模板的使用,此实现...

    无向图深度遍历邻接矩阵报告.doc

    "无向图深度遍历邻接矩阵报告.doc" 本报告旨在掌握图的结构特征、邻接矩阵和邻接表存储结构的特点和实现,以及在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。 一、图的结构特征 ...

    用邻接多重表实现图遍历演示

    邻接多重表是一种用于存储无向图的数据结构,它通过在每个顶点处维护一个指向与之相连的所有边的链表来表示图。这种数据结构不仅可以高效地存储图数据,而且可以方便地进行图的遍历操作,如深度优先搜索(DFS)和...

    数据结构:判别k长度简单路径(邻接表)

    总的来说,通过邻接表和限制深度的深度优先搜索策略,我们可以有效地在无向图中查找特定长度的简单路径。理解这些概念和技术对于理解和解决问题至关重要,它们也是计算机科学特别是图论和算法设计中的基础内容。

    C++ 数据结构 邻接矩阵

    设计一个有向图和一个无向图,使用邻接矩阵和邻接表存储结构,完成在这两种存储结构下有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 三、实验要求: 1. 根据实验内容编程,画出你所设计的图,...

    无向图深度优先搜索和宽度优先搜索算法代码c++

    无向图的深度优先搜索(DFS, Depth-First Search)和宽度优先搜索(BFS, Breadth-First Search)是图论中两种重要的遍历算法,它们被广泛应用于解决各种问题,如查找路径、判断连通性、求最短路径等。在C++中实现这...

    C++实现图的邻接表存储和广度优先遍历实例分析

    本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法。分享给大家供大家参考。具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6...

    数据结构基于图的深度优先算法用c++编写

    在这个主题中,我们专注于使用C++实现基于图的深度优先搜索(DFS,Depth-First Search)算法。深度优先搜索是一种用于遍历或搜索树或图的算法,其基本思想是从根节点开始,尽可能深地探索树的分支,直到达到叶子节点...

    图的深度优先生成树C++实现

    在计算机科学中,图是一种数据结构,用于表示对象之间的关系。...通过理解并实践这个C++实现,你可以更好地掌握图的深度优先搜索及其在生成树上的应用,这对理解和解决各种图论问题有着重要的意义。

    C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列。

    通过本文的介绍,读者应该能够理解无向图的深度优先遍历算法,并能根据所提供的示例代码实现自己的无向图深度优先遍历程序。这种遍历方式对于解决图理论中的许多问题非常有用,例如最短路径问题、拓扑排序等。

    图的邻接矩阵和邻接表表示

    在实现过程中,需要考虑图的遍历(深度优先搜索DFS和广度优先搜索BFS)、添加边、删除边以及查找路径等操作。 **4. 功能与运行界面** 描述中提到的实现可能包含了完整的功能,如读取图的输入、输出结果、显示图形...

Global site tag (gtag.js) - Google Analytics