学网站建设要什么,哈尔滨模板建站源码,知名企业的企业文化,上海建设检测网图的基本概念和术语
图的定义#xff1a;图是由顶点的有穷非空集合和顶点之间的边的集合组成的#xff0c;G表示#xff0c;V是图G中顶点的集合#xff0c;E是图G中边的集合
无向图#xff1a;任意两点的边都是无向边组成的图#xff08;无向边#xff1a;#xff08…图的基本概念和术语
图的定义图是由顶点的有穷非空集合和顶点之间的边的集合组成的G表示V是图G中顶点的集合E是图G中边的集合
无向图任意两点的边都是无向边组成的图无向边A,B)表示点A能到点B点B也能到点A
有向图任意两点的弧都是有向边组成的图有向边A,B表示点A能到点B点B不能到点AB为弧头A为弧尾
边较少的图叫稀疏图反之叫稠密图
权网图的边或弧相关的数叫权这种带权的图通常叫做网
顶点的度无向图中顶点的度表示和顶点相关联的的边的数目记TD)有向图中分为入度和出度 入度为顶点为弧头有关联的弧出度为顶点为弧尾有关联的弧
路径长度路径长度是路径上边或弧的数目
回路环第一个顶点和最后一个顶点相同的路径称为回路或环
连通图图中任意两点都是连接的有路径有向图中称为强连通图
无向图中联通n个顶点和n-1条边叫生成树有向图中一顶点入度为0其余顶点入度为1的叫有向树。 图的储存结构
邻接矩阵
图的邻接矩阵采用顺序存储结构用一个一维数组储存顶点的信息一个二维数组储存图中边或弧的的信息 优点便于理解适合稠密图O(1)判断两点是否有边删除边比较方便
缺点遇到边较少的图浪费大量空间图的建立dfsbfs遍历时间复杂度较高为O(N^2)删除点不方便 邻接表
邻接表采用顺序链式存储结构一个一维结构体数组数组大小为结点数量结构体数组的存储元素构成单链表每一个单链表链接与该结点相连的点 优点根据需求分配空间浪费的空间较少适合稀疏图 缺点删除边或点比较麻烦对于有向图不利于求某个点出度的数量 图的遍历
广度优先遍历和深度优先遍历对于邻接矩阵和邻接表的时间复杂度都为平方阶和线性阶 所以对于有关于图的遍历问题一般采用邻接表储存图时间开销更小
图中如果不是联通图存在一次遍历不能遍历全部的点一般用数组标记判断点是否遍历 模板题 洛谷 P5318 查找文献
本题考察图的深度和广度
题目描述
小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个也有可能没有参考文献的链接指向别的博客文章。小 K 求知欲旺盛如果他看了某篇文章那么他一定会去看这篇文章的参考文献如果他之前已经看过这篇参考文献的话就不用再看它了。
假设洛谷博客里面一共有n(n≤10^5) 篇文章编号为 1 到 n以及 m(m≤10^6) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章请帮助小 K 设计一种方法使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图其中文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。 请对这个图分别进行 DFS 和 BFS并输出遍历结果。如果有很多篇文章可以参阅请先看编号较小的那篇(因此你可能需要先排序)。
输入格式
共 m1 行第 1 行为 2 个数n 和 m分别表示一共有 n(n≤10^5) 篇文章编号为 1 到 n以及m(m≤10^6) 条参考文献引用关系。
接下来 m 行每行有两个整数 X,Y 表示文章 X 有参考文献 Y。
输出格式
共 2 行。 第一行为 DFS 遍历结果第二行为 BFS 遍历结果。
输入输出样例
输入 #1
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
输出 #1
1 2 5 6 3 7 8 4
1 2 3 4 5 6 7 8 看题发现本题的n的范围10^5用邻接矩阵不仅空间存不下遍历也浪费时间所以采用邻接表
这题不需要考虑是否为连通图题目的数据若是存在一个点与1号点没有联系则不需要输出这个点
思路
我们知道邻接表遍历结果不唯一的而题目要求请先看编号较小的那篇(因此你可能需要先排序)链表不好进行排序我们可以先对输入的m个x和y进行排序因为对于邻接表一般采用头插法先插入的点在链表的最后按照y的比较进行降序排列这样可以保证每一个单链表都是升序。
AC代码
#includestdio.h
#includestdlib.h
struct nb {int data;struct nb* p;
}a[100010];//邻接表
struct mm {int l, r;
}mr[1000010], b[1000010];//b为归并辅助数组
void guibin(int x, int y)//归并排序不多说
{if (x y) return;long long mid (x y) / 2, i, j;guibin(x, mid);guibin(mid 1, y);int cnt 0;for (i x, j mid 1; i mid j y;){if (mr[i].r mr[j].r)b[cnt] mr[i];elseb[cnt] mr[j];}while (i mid)b[cnt] mr[i];while (j y)b[cnt] mr[j];for (i 1; i cnt; i)mr[x i - 1] b[i];
}
int book[100010], book1[100010] { 0 };//标记数组
void dfs(int x)
{struct nb* gg;book[x] 1;//第一次访问标记为1printf(%d , x);//打印结果gg a[x].p;while (gg){if (book[gg-data] 0)//第一次访问dfs搜索dfs(gg-data);gg gg-p;}
}
void bfs(int x)
{int link[100010];int hard 1, tail 2;link[1] x; book1[x] 1;while (hard tail){printf(%d , link[hard]);struct nb* f a[link[hard]].p;while (f ! NULL){if (book1[f-data] 0){link[tail] f-data;book1[f-data] 1;}f f-p;}hard;}
}
int main()
{int n, m, i, j;struct nb* q, * t, * s;scanf(%d %d, n, m);for (i 1; i m; i)//输入m个x,yscanf(%d %d, mr[i].l, mr[i].r);for (i 1; i n; i)a[i].p NULL;guibin(1, m);//降序排序for (i 1; i m; i)//邻接表的建立{q (struct nb*)malloc(sizeof(struct nb));q-data mr[i].r; q-p a[mr[i].l].p;a[mr[i].l].p q;}dfs(1);//dfs搜索printf(\n);bfs(1);//bfs搜索for (i 1; i n; i)//清空邻接表链表避免内存泄露{s a[i].p;while (s ! NULL){t s;s s-p;free(t);}}return 0;
}
