t06.图

1.强连通

image-20240530191051179

强连通指的是在有向图中每两个顶点之间都是可达的,当两个顶点时有两条边为最少

2. 邻接表

image-20240530191217676

图有多少个顶点,就有多少个表头结点.无向图的表结点个数为2e

3. 无向图至少使得连通图

image-20240530191420897

n个节点的无向图,要有n-1条使得图为一个连通图

4. 无向图最小生成树

image-20240530191520523

一个无向图有n个顶点时，最小生成树上的边数为n-1条。这是因为最小生成树是一个包含所有顶点的树，而一棵树具有n个顶点时，它恰好包含n-1条边。

5.有向图表头结点

image-20240530192047749

有向图有n个顶点则有n个表头结点

6. 无向图表头结点

image-20240530192140240

无向图同理

7.深度优先

image-20240530192211610

8.无向图至少确保连通图

image-20240530192949418

首先五个顶点的全连通图需要的边为n*(n-1)/2=10,再来一条边就可以确保六个顶点为连通图

9.无向图邻接矩阵0元素

image-20240530193456213

矩阵是两个顶点有边,就有两个1.固n^2-2e

10.n个顶点,e条弧删除弧时间复杂度

image-20240530193818198

找结点+找边

11.

image-20240530194045999

12.

image-20240530194057358

13.

image-20240530194120362

14.

image-20240530194201449

15.

image-20240530194327276