连通图算法
❶ 什么叫做连通图
连通图：是指在图论中，连通图基于连通的概念。
在一个无向图G中，若从顶点到顶点有路径相连（当然从到也一定有路径），则称和是连通的。如果G是有向图，那么连接和的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。
❷ 连通图的深度优先遍历算法
这个第一个点是随机的。只是看你怎么储存的。如果你把v的邻接顶点用数组保存，那么它在数组的最前边。用指针的话，就指向下一个紧接的位置。
❸ 概要描述一个算法，判断一个用邻接矩阵表示的连通图是否具有欧拉回路。该算法效率类型如何
算法如下：
设邻接矩阵维度为n*n，将邻接矩阵进行标准化转为概率转移矩阵，方法是每一行元素除以行和保证每行和为1（由于连通，每行和一定大于零，所以除法可实现）
首先判断矩阵对角线上是否有>0的元素，如有证明有欧拉回路（自环），否则进行下一步
第二步将矩阵平方，判断矩阵对角线上是否有>0的元素，如有证明有欧拉回路（两个节点的环），否则进行下一步
以此类推，直到计算矩阵的n次方，判断对角线上是否有>0的元素，如有证明有欧拉回路，此时仍没有>0的元素证明该连通图没有欧拉回路
这个方法的依据是，如果将邻接矩阵标准化为概率转移矩阵，那么对矩阵进行k次方，得到的矩阵第(i,j)个元素的意义就是通过k步使得从i走到j的概率，那么对角线(i,i)代表的就是从i经k步回到i的概率，这个概率大于零就代表有一条回路。对于一个共有n个节点的有欧拉回路的连通图，最短的欧拉回路结点个数一定小于等于n，所以如果n次方后还没有出现回路概率就可以判断没有回路了
算法效率类型我不太清楚是怎么算的……不过这个算法方面，标准化矩阵的部分运算复杂度不超过n，之后至多进行n步，每一步的矩阵幂大概可以到O(n)复杂度，判断至多也就是O(n)，所以这个复杂度不超过O(n^2)的吧
❹ 一个连通图的计算
5，最少是n-1，最多是n(n-1)/2。
❺ 如何判断一个图是否是连着的图论，算法
连通图的特点是图中任意两点都是连通的，也就是说只要从任意一点出发能够到达所有的点就能够证明是连通图，否则就是不连通图
因为不知道你准备采用什么，具体算法我就不写语言了，只是解释一下原理：
1 采用数组、链表或数组，先将所有顶点定义在数组POINT中。
2 采用二维数组，将所有边（线段）定义在二维数组LINE中，记录两遍，边的两个顶点分别作为第一项如（v0,v3）(v3,v0)。
3 取出一个顶点v0加入到新数组CONPOINT中，并在顶点数组POINT中删除。
4 while循环，停止条件是CONPOINT中都标记着已读
{
从CONPOINT中取出一个有未读标记的顶点X，并作已读标记。
从二维数组LINE中查找第一项中包含X的边，将选出边的第二个顶点（1个或多个）取出，并加入到新数组CONPOINT中，并作未读标记（如果已有该点则不作插入）
将选出的边从二维数组LINE中删除。
}
比较CONPOINT和POINT数量，如果少了则不是连通图
❻ 连通图用深度优先和广度优先算法所得的生成树是否唯一
理论上遍历所得的生成树或序列是不唯一的，算法本身并没有对同等条件下哪个点优先访问做要求。但实际写代码的时候肯定要按某种顺序遍历，通常是从小到大，这时首个访问的点肯定是第一个点，当前点与多个未访问点相连时也是优先访问编号小的点，这样所得的结果就是唯一的了。
❼ 用c语言编写求有向图有多少连通图的算法（数据结构题目）
深度优先搜索。
http://www.cnblogs.com/dzkang2011/p/bfs_dfs.html
#include<iostream>
#include<cstdio>
usingnamespacestd;
#definemaxn100//最大顶点个数
intn,m;//顶点数，边数
structarcnode//边结点
{
intvertex;//与表头结点相邻的顶点编号
intweight=0;//连接两顶点的边的权值
arcnode*next;//指向下一相邻接点
arcnode(){}
arcnode(intv,intw):vertex(v),weight(w),next(NULL){}
arcnode(intv):vertex(v),next(NULL){}
};
structvernode//顶点结点，为每一条邻接表的表头结点
{
intvex;//当前定点编号
arcnode*firarc;//与该顶点相连的第一个顶点组成的边
}Ver[maxn];
voidInit()//建立图的邻接表需要先初始化，建立顶点结点
{
for(inti=1;i<=n;i++)
{
Ver[i].vex=i;
Ver[i].firarc=NULL;
}
}
voidInsert(inta,intb,intw)//尾插法，插入以a为起点，b为终点，权为w的边，效率不如头插，但是可以去重边
{
arcnode*q=newarcnode(b,w);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
if(p->vertex==b)//如果不要去重边，去掉这一段
{
if(p->weight<w)
p->weight=w;
return;
}
while(p->next!=NULL)
{
if(p->next->vertex==b)//如果不要去重边，去掉这一段
{
if(p->next->weight<w);
p->next->weight=w;
return;
}
p=p->next;
}
p->next=q;
}
}
voidInsert2(inta,intb,intw)//头插法，效率更高，但不能去重边
{
arcnode*q=newarcnode(b,w);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
q->next=p;
Ver[a].firarc=q;
}
}
voidInsert(inta,intb)//尾插法，插入以a为起点，b为终点，无权的边，效率不如头插，但是可以去重边
{
arcnode*q=newarcnode(b);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
if(p->vertex==b)return;//去重边，如果不要去重边，去掉这一句
while(p->next!=NULL)
{
if(p->next->vertex==b)//去重边，如果不要去重边，去掉这一句
return;
p=p->next;
}
p->next=q;
}
}
voidInsert2(inta,intb)//头插法，效率跟高，但不能去重边
{
arcnode*q=newarcnode(b);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
q->next=p;
Ver[a].firarc=q;
}
}
voidShow()//打印图的邻接表（有权值）
{
for(inti=1;i<=n;i++)
{
cout<<Ver[i].vex;
arcnode*p=Ver[i].firarc;
while(p!=NULL)
{
cout<<"->("<<p->vertex<<","<<p->weight<<")";
p=p->next;
}
cout<<"->NULL"<<endl;
}
}
voidShow2()//打印图的邻接表(无权值）
{
for(inti=1;i<=n;i++)
{
cout<<Ver[i].vex;
arcnode*p=Ver[i].firarc;
while(p!=NULL)
{
cout<<"->"<<p->vertex;
p=p->next;
}
cout<<"->NULL"<<endl;
}
}
#defineINF999999
boolvisited[maxn];//标记顶点是否被考察，初始值为false
intparent[maxn];//parent[]记录某结点的父亲结点，生成树，初始化为-1
intd[maxn],time,f[maxn];//时间time初始化为0，d[]记录第一次被发现时，f[]记录结束检查时
voiddfs(ints)//深度优先搜索（邻接表实现），记录时间戳，寻找最短路径
{
cout<<s<<"";
visited[s]=true;
time++;
d[s]=time;
arcnode*p=Ver[s].firarc;
while(p!=NULL)
{
if(!visited[p->vertex])
{
parent[p->vertex]=s;
dfs(p->vertex);
}
p=p->next;
}
time++;
f[s]=time;
}
voiddfs_travel()//遍历所有顶点，找出所有深度优先生成树，组成森林
{
for(inti=1;i<=n;i++)//初始化
{
parent[i]=-1;
visited[i]=false;
}
time=0;
for(inti=1;i<=n;i++)//遍历
if(!visited[i])
dfs(i);
cout<<endl;
}
intmain()
{
inta,b;
cout<<"Enternandm：";
cin>>n>>m;
Init();
while(m--)
{
cin>>a>>b;//输入起点、终点
Insert2(a,b);//插入操作
}
Show2();//邻接表
dfs_travel();//遍历
intcnt=0;//连通图个数
for(inti=1;i<=n;i++)
if(parent[i]==-1)
cnt++;
printf("%d ",cnt);
return0;
}
❽ 求无向连通图中两点最远距离算法，和Dijkstra相反，有想法就行，有代码更好
如果是无环图的话，把所有边取相反数，就变成了求最短路，可以使用floyd
❾ 实现图的邻接表表示及连通图
v v
❿ 怎么用c语言和数据结构来编写一个判断有向图是否为强连通图的算法
强连通图表明任意两点之间可以互相到达。
方案1：判断结点A可以到达的点的方法如下：
首先SA = {A}；
while 1
取SA中任意没有被去过的点x，根据以x为起点的有向线段，判断x可以直接到达的点，然后这些点加入SA；
如此循环，直到SA中的点的个数没有变化了
end
这样得到的集合SA是所有A可以到达的点的一个集合。
判断SA 是否等于S，若不等于S，表明不是强连通。
如此循环，求出所有S中的点的能够到达的点集。如果所有的点集都等于S表明强连通图。
方案2：可以优化1