连通图算法

① 实现图的邻接表表示及连通图

v v

② 试以邻接矩阵为存储结构，写出连通图的深度优先搜索算法。

/* MGraph.cc: 图的邻接矩阵存储表示和实现 */
/* 包含图类型Graph定义；创建图；深度优先遍历；广度优先遍历 */
/* 用到引用型参数，在TC下无法通过编译，VC等C++编译器可通过 */

#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX

#define VType char //顶点值类型
#define EType int //边权值类型
#define MAXVNUM 50 //最大顶点个数
#define DIGRAPH 0 //有向图(网)
#define UNDIGRAPH 1 //无向图(网)
#define INVALID INT_MAX //无效权值(最大整数表示无穷大)
#define EMPTY -1 //"空"顶点序号

//定义邻接矩阵表示的图类型Graph:
typedef struct
{
VType v[MAXVNUM]; //顶点序列(顶点编号从0开始)
EType w[MAXVNUM][MAXVNUM]; //邻接矩阵
int vn, en; //顶点数,边数
int kind; //图的种类：=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
}Graph;

int visited[MAXVNUM]; //访问标志数组(=1已访问，=0未访问)。遍历时用到的全局量。

/* 创建图G
参数Vex是存放顶点序列的数组
参数VVW是整数数组，以{Vi,Vj,Wij,...,-1}的形式依次存放各边的起止点序号(Vi,Vj)和权(Wij)，-1是数据结束标志
参数kind=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //顶点数
G.kind = kind; //图的种类
//置顶点序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化邻接矩阵:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//构造邻接矩阵:
p = 0; //VVW数组元素“指针”
n = 0; //边计数器
while (VVW[p] != -1)
{//只要p未到结束位置便继续:
i = VVW[p]; //边的起点序号
j = VVW[p + 1]; //边的终点序号
w = VVW[p + 2]; //边的权
G.w[i][j] = w; //置邻接矩阵的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是无向图(网),
G.w[j][i] = G.w[i][j]; //则置(i,j)的对称位置(j,i)
n++; //边计数器加1
p += 3; //p指向下一组(Vi,Vj,Wij)
}//end while
G.en = n; //边数
}//CreateGraph

/* 返回G中顶点i的一个未曾访问过的邻接点(序号) */
int NextAdjVex(Graph &G, int i)
{
int j, a;

a = EMPTY; //邻接点序号初始为"空"
//在邻接矩阵的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若当前元素是无效元素,
continue; //则继续找。
if (!visited[j])
{//若当前有效元素未曾访问过,则作为邻接点a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex

/* 访问顶点i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit

/* 从第i个顶点出发深度优先遍历连通图G */
/* 调用DFS前可能需初始化数组visited[] */
void DFS(Graph &G, int i)
{int a;

visit(G, i); //访问i顶点
visited[i] = 1; //标注i顶点已访问
a = NextAdjVex(G, i); //找出一个i的邻接点a
while (a != EMPTY)
{//只要a存在便继续:
if (visited[a] == 0) //若a未曾访问,
DFS(G, a); //则从a出发继续进行深度优先遍历。
a = NextAdjVex(G, i); //找出i的下一个邻接点a
}//end while
}//DFS

/* 从第i个顶点出发深度优先遍历图G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各顶点的访问标志为0(未曾访问):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //从i出发遍历
//若G非连通图，执行一次DFS无法遍历所有顶点，还需用如下for对尚未访问的顶点DFS。
//若G是连通图，执行一次DFS就已遍历所有顶点，此时如下for什么也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //对尚未访问的顶点DFS
}//DFSTrav

//显示图的邻接矩阵
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //顶点数
//以表格形式输出数组：
//输出表头：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//输出表体(矩阵元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM

③ 概要描述一个算法，判断一个用邻接矩阵表示的连通图是否具有欧拉回路。该算法效率类型如何

算法如下：
设邻接矩阵维度为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)的吧

④ 求无向连通图中两点最远距离算法，和Dijkstra相反，有想法就行，有代码更好

如果是无环图的话，把所有边取相反数，就变成了求最短路，可以使用floyd

⑤ 连通图的深度优先遍历算法

这个第一个点是随机的。只是看你怎么储存的。如果你把v的邻接顶点用数组保存，那么它在数组的最前边。用指针的话，就指向下一个紧接的位置。

⑥ 一个连通图的计算

5，最少是n-1，最多是n(n-1)/2。

⑦ 用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;
}

⑧ 连通图用深度优先和广度优先算法所得的生成树是否唯一

理论上遍历所得的生成树或序列是不唯一的，算法本身并没有对同等条件下哪个点优先访问做要求。但实际写代码的时候肯定要按某种顺序遍历，通常是从小到大，这时首个访问的点肯定是第一个点，当前点与多个未访问点相连时也是优先访问编号小的点，这样所得的结果就是唯一的了。

⑨ 什么叫做连通图

连通图：是指在图论中，连通图基于连通的概念。

在一个无向图G中，若从顶点到顶点有路径相连（当然从到也一定有路径），则称和是连通的。如果G是有向图，那么连接和的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。

⑩ 怎么用c语言和数据结构来编写一个判断有向图是否为强连通图的算法

强连通图表明任意两点之间可以互相到达。
方案1：判断结点A可以到达的点的方法如下：
首先SA = {A}；
while 1
取SA中任意没有被去过的点x，根据以x为起点的有向线段，判断x可以直接到达的点，然后这些点加入SA；
如此循环，直到SA中的点的个数没有变化了
end
这样得到的集合SA是所有A可以到达的点的一个集合。
判断SA 是否等于S，若不等于S，表明不是强连通。

如此循环，求出所有S中的点的能够到达的点集。如果所有的点集都等于S表明强连通图。

方案2：可以优化1