建图与有哪些信誉好的足球投注网站(代码补充)讲义.ppt

图的基础与有哪些信誉好的足球投注网站 主讲队：Dragon 本课件很多地方引用了学长的课件 建图 1.用结构建图 这种方法多用于以下几种情况: 每个节点有着确定数量的路径 每个点有一定的信息量（权值等） struct point{ 常用于二叉树等一系列题目 int left; int right; int value; int father; }p[205]; 2.用邻接矩阵建图 用a[i][j]表示从点i到点j的路程长度（权值等） 好处：可以很容易的表示出每两个节点之间的路径，也可以记录权值。 缺点：遍历的时候很费时间，空间占用量非常大。 int a[205][205]; 3.用vector建图 vector不但和数组一样可以对元素进行随机访问，还能在尾部插入元素。完全可以替代数组。 vector具有内存自动管理的功能，对于元素的插入和删除，可以动态调整所占内存空间。 vector需要头文件包含申明includevector。 vector同数组一样，也是从下标0开始计数的。 vector容器有两个重要的方法，begin（）和end（）。begin（）返回的是首元素位置的迭代器；end（）返回的是最后一个元素的下一元素位置的迭代器。 Vector的基本操作 #includevector（头文件） using namespace std;（c++） vector（vector中存的变量类型） v（vector的名称）; 增加一个元素：v.push_back(x);将x增加到v中。 清空：v.clear(); v.begin()和v.end()会分别返回开始和结束的地址，v.size()会返回里面元素的个数。 Vector支持下标访问方式且从0开始计数，例如：v={1,4,5,7}，则v[0]=1,v[3]=7。 遍历vector中的元素： for（i=0;iv.size();i++）（注意这个位置不能加等号，否则会越界） if(v[i]==……)…… 还可以使用迭代器来遍历vector中的元素，vectorint:: iterator it,定义it为迭代器。 for(it=v.begin();it!=v.end();it++) if(*it==……)…… Vector存图代码 for(i=1;i=n;i++){//输入n条边 scanf(“%d %d”,a,b);//输入每条边的起点和终点 v[a].push_back(b);//将b存入v[a]中 } 经过n次此操作，v[i]里面的元素即表示点i可以连接的点 4.用邻接表建图 First[205],next[205]; First[i]表示存图时，点i的最后一条边的序号。 Next[i]表示与边i相同起点的其它边的序号。 将first和next都初始化为-1。 例如：b[1]=4-5,b[2]=1-2,b[3]=1-3，b[4]=4-1,b[5]=1-4;b[]表示存边的结构数组。 读取b[1],first[4]=1; 读取b[2],first[1]=2; 读取b[3],next[3]=2;first[1]=3; 读取b[4],next[4]=1;first[4]=4; 读取b[5],next[5]=3;first[1]=5; first next 1 5 -1 2 -1 -1 3 -1 2 4 4 1 5 -1 3 存图 scanf(“%d%d”,b[i].start,b[i].end); next[i]=first[b[i].start]; first[b[i].start]=i; 遍历 k=first[i]; While(k!=-1){ ……(相关操作); k=next[k]; } 有哪些信誉好的足球投注网站 分为广度优先有哪些信誉好的足球投注网站（BFS）和深度优先有哪些信誉好的足球投注网站（DFS）。 广度优先有哪些信誉好的足球投注网站利于求最短路，它是一种先生成的节点先扩展的策略。 深度优先有哪些信誉好的足球投注网站需求空间少，能进则进，进不了则换，换不了则退，回溯的一种策略。 队列 广度优先有哪些信誉好的足球投注网站需要用到一个结构：队列。 队列是一种“先入先出”的存储结构。 有以下几种操作： #includequeue using namespace std; queueint d; d.push(x)(插入元素x)； d.pop()(删除队首元素); d.front()(读取队首元素)； d.empty()(判断队列是否为空，是，返回true，否，返回false)； {E} 对E进行有哪些信誉好的足球投注网站，将子节点F,H,I加入队列中 {F,H,I} 对F进行有哪些信誉好的足球投注网站，将J,G加入队列中 {H,I,J,G} {I,J,G,K} {J,G,K} {G,K} {K} 14 (0,0) (0,1) (0,2) (1,0