无向图用矩阵幂算法如何求其连通分支数

pwdlist2022-10-04 11:39:541条回答

已提交，审核后显示！提交回复

darcy_shi 共回答了10个问题 | 采纳率80%: 设连通矩阵A,x->y若连通,则A[x][y]=1（当然也有A[y][x]=1）,否则A[x][y]=0,特别地有A[x][x]=1
此时A[x][y]>0当且仅当x->y有直接连通的边
再考虑A^2=A*A,A^2[x][y]>0当且仅当x->y有长度小于等于2条边的通路
最后,A^n[x][y]>0当且仅当x->y有任意长度的通路（n是节点数目）
所以用快速幂求出A^n,然后将A^n作为邻接矩阵,DFS一遍就可以了; 1年前

2．知有8个结点值为A、B、C、D、E、F、G和H的无向图,其邻接矩阵的存储结构见表.（1）画出此无向图.（2 2．知有8个结点值为A、B、C、D、E、F、G和H的无向图,其邻接矩阵的存储结构见表.（1）画出此无向图.（2 就这些分了- - tmjxf1年前1: 402933916 共回答了11个问题 | 采纳率90.9%

直接插入:46,58 剩下的待排
冒泡:14,18,37,42,48,64,96,96
快速:以第70为基准 68,73,69,23,93,18,11,70
直接选择:2,3,4 剩下的待排
堆排序:用大根堆第一次选出94 第二次为73,23,71,68,72,16,5
归并:用二路归并 5,26,1,77,11,61,15,59,19,48
基数:用最低位 505,008,109,930,63,269,278,83,184,589

1年前查看全部

数据结构类：画出无向图（下附）的邻接矩阵和邻接表示意图,并写出每个顶点的度! 凯蕊1年前1: jssmzylj 共回答了16个问题 | 采纳率87.5%

邻接矩阵
v1 v2 v3 v4 v5 v1 0 1 0 1 0 v2 1 0 0 1 1 v3 0 0 0 1 1 v4 1 1 1 0 0 v5 0 1 1 0 0
邻接表
v1 -> v2 -> v4 v2 -> v1 -> v4 -> v5 v3 -> v4 -> v5
v4 -> v1 -> v2 -> v3 v5 -> v2 -> v3
度
v1 2
v2 3
v3 2
v4 3
v5 2

1年前查看全部

对如下带权无向图,用克鲁斯卡尔(Kruskal)算法或普里姆（prim）算法,生成一棵最小生成树, 对如下带权无向图,用克鲁斯卡尔(Kruskal)算法或普里姆（prim）算法,生成一棵最小生成树, 并用图示来表明树的形成过程 demons13141年前1: princejlx 共回答了9个问题 | 采纳率88.9%

1年前查看全部

设图的邻接矩阵为 0 1 10 0 10 1 0,则该图为（）.A.有向图 B.无向图 C.强连通图 D.完全图 love_felicia1年前0: 共回答了个问题 | 采纳率

查看全部

下面关于图的论述中正确的是a邻接表法只能用于有向图的存储,而相邻矩阵法对于有向图和无向图的存储都适用b任何有向图网络拓扑 下面关于图的论述中正确的是 a邻接表法只能用于有向图的存储,而相邻矩阵法对于有向图和无向图的存储都适用 b任何有向图网络拓扑排序的结果是唯一的 c有回路的图不能进行拓扑排序 d无向连通网络的最小生成树是唯一的 痞子啊赖1年前1: 笑见共回答了16个问题 | 采纳率93.8%

d

1年前查看全部

设G是(n,m)无向图,若 ,证明G中必存在圈. sb026811年前2: 安安0422 共回答了15个问题 | 采纳率100%

LS说的对啊,LZ题目给的不完整,当然我也做不来这些诶.

1年前查看全部

有向图和无向图的邻接矩阵有什么区别 有向图和无向图的邻接矩阵有什么区别 我看见有的题目的答案中的矩阵有0和1,但有的又有0、1和∞.请问什么时候是前者,什么时候是后者呢? baobei03291年前1: 00fy 共回答了16个问题 | 采纳率93.8%

0、1和无穷三者不可能同时出现.无向和有向无权图中用1表示能够直接到达,0表示不能一步到达.带权图中正数代表路径权值,无穷表示一步无法到达.

1年前查看全部

谁会数据结构?用邻接表创建一个 < 无向图>,中间涉及到“狐头”“狐尾”吗?我个人认为不应该涉及到> 谁会数据结构?用邻接表创建一个 < 无向图>,中间涉及到“狐头”“狐尾”吗?我个人认为不应该涉及到> void CreateGraph(AdjGraph *G) /*采用邻接表存储结构,创建无向图G*/ 、-----------《它注明是创建无向图》 { x05int i,j,k; x05VertexType v1,v2;x05x05 .(中间省略) x05scanf("%s%s",v1,v2); x05x05i=LocateVertex(*G,v1); x05x05j=LocateVertex(*G,v2); x05x05/*j为弧头i为弧尾创建邻接表*/----------中间为什么涉及弧头弧尾? x05x05p=(ArcNode*)malloc(sizeof(ArcNode)); x05x05p->adjvex=j; x05x05p->info=NULL; x05x05p->nextarc=G->vertex[i].firstarc; x05x05G->vertex[i].firstarc=p; x05x05/*i为弧头j为弧尾创建邻接表*/------中间问什么涉及弧头弧尾? kiya00701年前1: 一六电子共回答了16个问题 | 采纳率75%

用邻接表创建一个 < 无向图>,是不会涉及到弧头弧尾的,只有边邻接的两个顶点

1年前查看全部

设T是一个（n,m）无向图,若T无圈且m=n-1,证明T为树 f345361872065d001年前1: 小流星jfy 共回答了12个问题 | 采纳率100%

设该图为G.只需要证明G是连通的.用反证法.
设G是不连通的,G含s个连通分图G1,G2,……Gs,(s>=2）.因每个Gi（i=1,2,……s)是连通的,并且不含圈,故每个Gi是树.设Gi有pi个点,则Gi有pi-1条边,于是
q(G)=q(G1)+q(G2)+……+q(Gs)=(p1-1)+(p2-1)+……+ps-1)=p(G)-s

1年前查看全部

设某带权无向图如下图,画出用Prim算法,从顶点A开始生成最小生成树的每一步结果. rexysy141年前1: 悠悠睡共回答了18个问题 | 采纳率83.3%

和你文字描述好了,你自己画出来
第一步连AE
第二步连EG
GC
GF
AD
BD

1年前查看全部

无向图用邻接矩阵存储,其所有元素之和表示无向图的边数的_____? 无向图用邻接矩阵存储,其所有元素之和表示无向图的边数的_____? 应该是一半还是2倍 zxcwxy1231年前1: 雨涵2002 共回答了9个问题 | 采纳率88.9%

2倍
因为每条边对应矩阵中的两个1

1年前查看全部

数据结构：无向图适合邻接矩阵,有向图适合邻接表 数据结构：无向图适合邻接矩阵,有向图适合邻接表 这句话对吗,并给出理由 yagnjv1年前1: janhua000 共回答了15个问题 | 采纳率93.3%

这句话不对,邻接表和邻接矩阵,即可以存储无向图也可以存储有向图,稠密图适合用邻接矩阵,稀疏图适合用邻接表存储

1年前查看全部

无权无向图,只给出节点个数,怎么用Prim算法求最小生成树 歪歪gg1年前1: carlyle 共回答了17个问题 | 采纳率76.5%

Prim算法的主要运行时间花在过程②的选边中.看起来复杂度是O(VE)=O(V^3)不是么,效率也太低了吧……

为了比较快速地选边,我们用两个数组lowcost、closest动态地维护每一个点到S的最短距离.在某一状态下,lowcost[i]表示所有与i相连且另一端点在S中的边中的权值最小值,closest[i]表示在S中且与i相连的点中与i之间距离最小的点.显然,lowcost[i]=w(i,closest[i]).需要注意的是两个数组记录的都是边而不是路径.若i没有边直接连向S,则lowcost[i]=∞.另外,若i已在S中,则lowcost[i]=0.

设出发点为x.初始时对于任意k∈V,closest[k]=x,lowcost[k]=w（k,x）【w（i,j）表示i、j间的距离.初始化时,若两点间没有边则w（i,j）赋为一个足够大的整数（如maxint）,并且所有点到自身的距离赋为0,即w（i,i）=0】

每一次找出lowcost中不为0的最小值lowcost[i],然后把i加入S（即lowcost[i]:=0）,然后对于图中所有点k,若w(k,i)

1年前查看全部