精华内容
下载资源
问答
  • 又例,2行3列的二维数组 {a1, a2, a3, a4, a5, a6} a1 a2 a3 a4 a5 a6 行次序关系:row = {,a2>,,a3>,,a5>,,a6>} 列次序关系:col = {,a4>,,a5>,,a6>} 再例,一维数组 {a1, a2, a3, a4, a5, a6}中存在 次序关系...
  • 一般oj题中可能就是点与点,也有可能具体生活中物体图分为有向图和无向图,图存储使用邻接矩阵(即二维数组)或者邻接表。图基本操作就是图遍历,深度优先搜索算法(dfs)和广度优先搜索算法(bfs)图...

    一、前提须知

    1. 图是一种数据结构,一般作为一种模型用来定义对象之间的关系或联系。对象:顶点(V)表示;对象之间的关系或者关联:通过图的边(E)来表示。一般oj题中可能就是点与点,也有可能是具体生活中的物体
    2. 图分为有向图和无向图,图的存储使用邻接矩阵(即二维数组)或者邻接表。
    3. 图的最基本操作就是图的遍历,深度优先搜索算法(dfs)和广度优先搜索算法(bfs)是图遍历操作的2种方法。这2钟方法对于无向图和有向图皆适用。

    二、深度优先搜索算法(dfs)

    1.基本思想:

    简单说就是搜到底,重新搜。从v0为起点进行搜索,如果被访问过,则做一个标记,直到与v0想连通的点都被访问一遍,如果这时,仍然有点没被访问,可以从中选一个顶点,进行再一次的搜索,重复上述过程。

    2.代码思想:

    定义一个二维数组存放点与点之间的关系,可以直接到达即为1,否则为0;

    定义一个一维数组用于记录某个点是否已经访问过。初始化全为0,代表都未访问过。

    使用递归方法,得出结果。

    3.例子:


                  ( 网图)

    1. 以任何一个点为起点,如 顶点 1 。
    2. 从顶点1开始搜索,为 1->2->3 ,到顶点3后终止。回溯到顶点 2 .
    3.  2->5 到达顶点5 后终止。回溯 到 顶点2,终止于顶点2,回溯到 顶点 1,终止于顶点 1.
    4.  从顶点 4 开始访问,并终止于顶点 4 。

    实现上述图的递归dfs代码:

    #include <iostream>
    using namespace std;
    const int maxn=100;
    
    int arr[maxn][maxn];
    int vis[maxn + 1] = { 0 };
    int n;
    void dfs(int start)
    {
    	vis[start]=1;
    	for(int i=1;i<=n;i++)
    	{
    		if(!vis[i]&&arr[start-1][i-1]==1)
    			dfs(i);
    		
    	}
    	cout<<start<<" ";
    }
    void dfs_traverse(int begin)
    {
    	dfs(begin);
    	for(int i=1;i<=n;i++)//例子中的点是从1开始的,所以是1到n(dfs中同理); 
    	{
    		if(vis[i]==1)
    			continue;
    		dfs(i);
    	}
    }
    int main()
    {
    	int i,j,begin;
    	//读入总的顶点数
    	cin>>n; 
    	//读入邻接矩阵
    	for(i=0;i<n;i++) 
    		for(j=0;j<n;j++)
    			cin>>arr[i][j];
    	//输入深度搜索的起始顶点		
    	cin>>begin;
    	dfs_traverse(begin);
        return 0;
    }

    测试数据:

    0 1 1 0 0
    0 0 1 0 1
    0 0 1 0 0
    1 1 0 0 1

    0 0 1 0 0

    结果:



    三、广度优先搜索算法(bfs)

    1.基本思想:

    选择一个顶点为起始顶点,先搜索与该点连接的所有的邻点,依次搜索所有邻点的邻点。


    2.代码思想:

    双端队列不为空则循环

    将未访问的邻接点压入双端链表后面,然后从前面取出并访问

    结合上述2点,使用STL中的queue实现起来可以方便一点


    3.例子:


    从顶点1开始进行广度优先搜索:
    1. 初始状态,从顶点1开始,队列={1}
    2. 访问1的邻接顶点,1出队变黑,2,3入队,队列={2,3,}
    3. 访问2的邻接结点,2出队,4入队,队列={3,4}
    4. 访问3的邻接结点,3出队,队列={4}
    5. 访问4的邻接结点,4出队,队列={ 空}
      结点5对于1来说不可达。

    实现上述的bfs代码:

    #include <iostream>
    #include<queue>
    using namespace std;
    
    const int maxn=100;
    int arr[maxn][maxn];
    int vis[maxn + 1] = { 0 };
    int n;
    
    void bfs(int start)
    {
    	queue<int>q;
    	q.push(start);
    	vis[start]=1;
    	while(!q.empty())
    	{
    		int front=q.front();
    		cout<<front<<" ";
    		q.pop();
    		for(int i=1;i<=n;i++)
    		{
    			if(!vis[i]&&arr[front-1][i-1])
    			{
    				vis[i]=1;
    				q.push(i);
    			}
    		}	
    	}
    }
    void bfs_traverse(int begin)
    {
    	bfs(begin);
    	for(int i=1;i<=n;i++)//例子中的点是从1开始的,所以是1到n(bfs中同理); 
    	{
    		if(vis[i]==1)
    			continue;
    		bfs(i);
    	}
    }
    int main()
    {
    	int i,j,begin;
    	//读入总的顶点数
    	cin>>n; 
    	//读入邻接矩阵
    	for(i=0;i<n;i++) 
    		for(j=0;j<n;j++)
    			cin>>arr[i][j];
    	//输入深度搜索的起始顶点		
    	cin>>begin;
    	bfs_traverse(begin);
        return 0;
    }

    测试数据:

    0 1 1 0 0
    0 0 1 1 0
    0 1 1 1 0
    1 0 0 0 0 

    0 0 1 1 0

    测试结果:


    展开全文
  • 例如,在一维数组[21,46,24,99,57,77,86]中,查找数据元素99,首先从第1个元素21开始进行比较,比较结果与要查找数据不相等,接着与第2个元素46进行比较,以此类推,当进行到与第4个元素比较时,它们相等,...
  • 关系模型 B. 层次模型 C. 网状模型 D. 数据模型 (30) 关系数据库管理系统能实现专门关系运算包括(B) A. 排序、索引、统计 B. 选择、投影、连接 C. 关联、更新、排序 D. 显示、打印、制表 (31) 算法一般都可以用哪...
  • 4.2.3 二维数组的声明和调用 70 4.2.4 多维数组 71 4.3 动态数组 72 4.3.1 动态数组的声明 72 4.3.2 声明动态数组的注意事项 74 4.4 数组的基本操作 74 4.4.1 输入与输出数组 74 4.4.2 如何定位数组...
  • 数组和指针的基本关系 6.1 我在一个源文件中定义了chara[6],在另一个源文件中声明了externchar*a。为什么不行? 6.2 可是我听说chara[]和char*a等价的。这样的吗? 6.3 那么,在C语言中“指针和数组等价”...
  • java初学者必看

    热门讨论 2012-02-24 16:07:34
    6.2.3 二维数组的空间模型 6.2.4 二维数组的使用 6.3 数组操作 6.3.1 排序数组 6.3.2 查找 6.3.3 复制数组 6.3.4 填充数据 6.3.5 比较数组 6.4 实例:杨辉三角 6.5 本章习题 第7章 对象与类 7.1 面向对象...
  • 数组和指针的基本关系 63 6.1 我在一个源文件中定义了char a[6],在另一个源文件中声明了extern char *a。为什么不行? 63 6.2 可是我听说char a[]和char *a等价的。这样的吗? 63 6.3 那么,在C语言中...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    《你必须知道495个C语言问题》结构清晰,讲解透彻,各高校相关专业C语言课程很好教学参考书,也各层次C程序员优秀实践指南。 -----------------------------------------------------------------------...
  • 最后,读者将学习如何创建二维数组以及如何使用嵌套循环来处理它们。 第6章:分支语句和逻辑操作符 如果程序可以根据实际情况调整执行,我们就说程序能够智能地行动。在本章,读者将了解到如何使用if 、if else...
  • 最后,读者将学习如何创建二维数组以及如何使用嵌套循环来处理它们。 第6章:分支语句和逻辑操作符 如果程序可以根据实际情况调整执行,我们就说程序能够智能地行动。在本章,读者将了解到如何使用if 、if else...
  • 最后,读者将学习如何创建二维数组以及如何使用嵌套循环来处理它们。 第6章:分支语句和逻辑操作符 如果程序可以根据实际情况调整执行,我们就说程序能够智能地行动。在本章,读者将了解到如何使用if 、if else...
  • 6.2 数据模型的演变和数据库技术的当前发展趋势 109 6.3 Informix Universal Server 110 6.3.1 可扩展数据类型 111 6.3.2 支持用户定义例程 112 6.3.3 支持继承 113 6.3.4 支持索引扩展 115 ...
  • 18.8 三维数据的二维图 18.9 其它函数 18.10 动画 18.11 小结 第19章 颜色 19.1 颜色映象理解 19.2 颜色映象使用 19.3 颜色映象显示 19.4 颜色映象建立和修改 19.5 图形中使用一个以上颜色映象 19.6 用颜色描述...
  • C++ Primer Plus 中文版 第4版 清晰版

    千次下载 热门讨论 2009-12-06 14:45:21
    5.6 嵌套循环和二维数组 133 5.6.1 初始化二维数组 134 5.7 总结 136 5.8 复习题 136 5.9 编程练习 137 第6章 分支语句和逻辑操作符 139 6.1 if语句 140 6.1.1 if else语句 141 6.1.2 格式化if ...
  • 10.2.3 二维离散傅立叶变换( 2DDFT ) 10.2.4 快速傅立叶变换( FFT ) 10.2.5 傅立叶变换研究与应用 10.3 离散余弦变换 10.3.1 DCT 变换矩阵 10.3.2 dct2 函数和 dctmtx 函数 10.4 Walsh- Hadamard ...

空空如也

空空如也

1 2 3 4 5
收藏数 89
精华内容 35
关键字:

关系模型的基本结构是二维数组