概要描述一个算法，判断一个用邻接矩阵表示的连通图是否具有欧拉回路该算法效率类型如何？离散数学连通度怎么算

本文目录

• 概要描述一个算法，判断一个用邻接矩阵表示的连通图是否具有欧拉回路该算法效率类型如何
• 离散数学连通度怎么算
• 一个连通图采用邻接表作为储存结构，设计一个算法～实现从顶点v出发的深度优先遍历的非递归过程
• 请问如何求（有向/无向）图的强连通分量，还有，基础一点，怎么求有几个连通图啊
• 试以邻接矩阵为存储结构，写出连通图的深度优先搜索算法
• 用C语言编写求有向图有多少连通图的算法（数据结构题目）
• 怎么用c语言和数据结构来编写一个判断有向图是否为强连通图的算法

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

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

离散数学连通度怎么算

一个具有N个点的图G中，在去掉任意k-1个顶点后（1《=k《=N），所得的子图仍然连通，去掉K个顶点后不连通。

G中不含割点的极大连通子图称为图G的块。若H是图G的块，则H自身不含割点且满足：若向H中再添加边，但不添加结点，那么H就不是G的子图了；若向H中再增加结点或边将H扩大为更大的连通图，那么H就会含有割点。

扩展资料：

如果图G的顶点集的一个真子集T满足G-T不连通或是平凡图，如果图G的边集的一个真子集S满足G-S不连通或是平凡图。

一个图G有强连通的定向图的必要条件是G为2边连通的。否则G中有割边，这与G有强连通的定向图矛盾。

一个连通图采用邻接表作为储存结构，设计一个算法～实现从顶点v出发的深度优先遍历的非递归过程

递归转非递归的常用方法是自己用栈来模拟，比较容易得到的方法是：

#include 《iostream》
#include 《vector》
#include 《stack》
#include 《cstring》
using namespace std;
const int maxn = 1000000;
vector《int》 G;
int e;
bool visit;
void dfs(int u)
{
    visit = true;
    cout 《《 u 《《 endl;
    for(int i = 0; i 《 (int)G.size(); ++i) {
        if(!visit);
    }
}
int n, s; // 结点数, 起点编号
int main()
{
    cin 》》 n;
    for(int i = 1; i 《= n; ++i) {
        int sz;
        cin 》》 sz;
        for(int j = 0; j 《 sz; ++j) {
            int v;
            cin 》》 v;
            G.push_back(v);
        }
    }
    cin 》》 s;
    dfs(s);
    cout 《《 endl;
    memset(visit, 0, sizeof(visit));
    stack《int》 stk;
    stk.push(s);
    while(!stk.empty()) {
        int u = stk.top(); stk.pop();
        if(!visit) {
            cout 《《 u 《《 endl;
            visit = true;
        }
        for(; e) {
            int v = G;
            if(visit) continue;
            stk.push(u); stk.push(v);
            break;
        }
    }
    return 0;
}

以上程序进行了一次递归遍历和依次非递归遍历，输入格式是：

10
1 8
1 4
1 9
2 2 5
2 4 8
3 10 7 8
1 6
3 1 5 6
2 3 10
2 6 9
8

第一行表示结点数，第的结点的邻接表（邻接点数量 结点编号...）

最后一行表示dfs的起点编号。

请问如何求（有向/无向）图的强连通分量，还有，基础一点，怎么求有几个连通图啊

求强连通分量的算法有tarjan和kosaraju 两种算法
相较之下 tarjan写起来比较简单 Kosaraju比较麻烦
但是想起来 Kosaraju比较简单
其他求强连通分量的算法 要是还有的话 估计就是需要更高深的数据结构的算法了
建议还是学下tarjan 因为他可以帮你做很多事 比如 求桥 求割点 缩环 而且写起来也很简单
连通图的求法可以直接DFS 每次DFS到一个点 就把它记录成已到达 然后继续向下搜索 每次DFS就可以求出一个连通图
附上tarjan的代码
var
next,head,point:array of longint;
time,tot,i,j,n,m,x,y,t:longint;
v:array of byte;
f,z,q:array of longint;
low,rea:array of longint;
function min(x,y:longint):longint;
begin
if x《y then exit(x) else exit(y);
end;
procedure add(x,y:longint);
begin
inc(tot);
next;
head:=tot;
point:=y;
end;
procedure dfs(x:Longint);
var
i,j:longint;
begin
inc(time);
low:=time;
rea:=time;
v:=1;
inc(t);
z:=x;
j:=head;
while j《》0 do
begin
if v);
if v);
j:=next;
end;
if low then
begin
inc(tot);
while z《》x do
begin
inc(q);
f:=tot;
v:=2;
dec(t);
end;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
add(x,y);
end;
tot:=0; time:=0;
for i:=1 to n do
if v=0 then dfs(i);
//writeln(tot);
for i:=1 to n do
if q《》1 then writeln(’T’) else writeln(’F’);
end.

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

/* 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; //顶点序列(顶点编号从0开始)
EType w; //邻接矩阵
int vn, en; //顶点数,边数
int kind; //图的种类：=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
}Graph;
int visited; //访问标志数组(=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;
//初始化邻接矩阵:
for (i = 0; i 《 n; i++)
for (j = 0; j 《 n; j++)
G.w = INVALID;
//构造邻接矩阵:
p = 0; //VVW数组元素“指针”
n = 0; //边计数器
while (VVW != -1)
{//只要p未到结束位置便继续:
i = VVW; //边的起点序号
j = VVW; //边的终点序号
w = VVW; //边的权
G.w = w; //置邻接矩阵的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是无向图(网),
G.w; //则置(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 == INVALID) //若当前元素是无效元素,
continue; //则继续找。
if (!visited)
{//若当前有效元素未曾访问过,则作为邻接点a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex
/* 访问顶点i */
void visit(Graph &G, int i)
{
printf("%c", G.v);
}//visit
/* 从第i个顶点出发深度优先遍历连通图G */
/* 调用DFS前可能需初始化数组visited */
void DFS(Graph &G, int i)
{int a;
visit(G, i); //访问i顶点
visited = 1; //标注i顶点已访问
a = NextAdjVex(G, i); //找出一个i的邻接点a
while (a != EMPTY)
{//只要a存在便继续:
if (visited == 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 = 0;
DFS(G, i); //从i出发遍历
//若G非连通图，执行一次DFS无法遍历所有顶点，还需用如下for对尚未访问的顶点DFS。
//若G是连通图，执行一次DFS就已遍历所有顶点，此时如下for什么也不做，因所有visited=1。
for (k = 0; k 《 G.vn; k++)
if (!visited) 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 == INVALID)
printf("%3c", ’*’);
else
printf("%3d", G.w);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM

用C语言编写求有向图有多少连通图的算法（数据结构题目）

深度优先搜索。

***隐藏网址***

#include 《iostream》
#include 《cstdio》
using namespace std;
#define maxn 100  //最大顶点个数
int n, m;       //顶点数，边数
struct arcnode  //边结点
{
    int vertex;     //与表头结点相邻的顶点编号
    int weight = 0;     //连接两顶点的边的权值
    arcnode * next; //指向下一相邻接点
    arcnode() {}
    arcnode(int v,int w):vertex(v),weight(w),next(NULL) {}
    arcnode(int v):vertex(v),next(NULL) {}
};
struct vernode      //顶点结点，为每一条邻接表的表头结点
{
    int vex;    //当前定点编号
    arcnode * firarc;   //与该顶点相连的第一个顶点组成的边
}Ver;
void Init()  //建立图的邻接表需要先初始化，建立顶点结点
{
    for(int i = 1; i 《= n; i++)
    {
        Ver.vex = i;
        Ver.firarc = NULL;
    }
}
void Insert(int a, int b, int w)  //尾插法，插入以a为起点，b为终点，权为w的边，效率不如头插，但是可以去重边
{
    arcnode * q = new arcnode(b, w);
    if(Ver.firarc == NULL)
        Ver.firarc = q;
    else
    {
        arcnode * p = Ver.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;
    }
}
void Insert2(int a, int b, int w)   //头插法，效率更高，但不能去重边
{
    arcnode * q = new arcnode(b, w);
    if(Ver.firarc == NULL)
        Ver.firarc = q;
    else
    {
        arcnode * p = Ver.firarc;
        q-》next = p;
        Ver.firarc = q;
    }
}
void Insert(int a, int b)   //尾插法，插入以a为起点，b为终点，无权的边，效率不如头插，但是可以去重边
{
    arcnode * q = new arcnode(b);
    if(Ver.firarc == NULL)
        Ver.firarc = q;
    else
    {
        arcnode * p = Ver.firarc;
        if(p-》vertex == b) return;      //去重边，如果不要去重边，去掉这一句
        while(p-》next != NULL)
        {
            if(p-》next-》vertex == b)    //去重边，如果不要去重边，去掉这一句
                return;
            p = p-》next;
        }
        p-》next = q;
    }
}
void Insert2(int a, int b)   //头插法，效率跟高，但不能去重边
{
    arcnode * q = new arcnode(b);
    if(Ver.firarc == NULL)
        Ver.firarc = q;
    else
    {
        arcnode * p = Ver.firarc;
        q-》next = p;
        Ver.firarc = q;
    }
}
void Show()     //打印图的邻接表（有权值）
{
    for(int i = 1; i 《= n; i++)
    {
        cout 《《 Ver.vex;
    
        arcnode * p = Ver.firarc;
        while(p != NULL)
        {
            cout 《《 "-》(" 《《 p-》vertex 《《 "," 《《 p-》weight 《《 ")";
            p = p-》next;
        }
        cout 《《 "-》NULL" 《《 endl;
    }
}
void Show2()     //打印图的邻接表(无权值）
{
    for(int i = 1; i 《= n; i++)
    {
        cout 《《 Ver.vex;
        arcnode * p = Ver.firarc;
        while(p != NULL)
        {
            cout 《《 "-》" 《《 p-》vertex;
            p = p-》next;
        }
        cout 《《 "-》NULL" 《《 endl;
    }
}
#define INF 999999
bool visited;     //标记顶点是否被考察，初始值为false
int parent记录某结点的父亲结点，生成树，初始化为-1
int d记录结束检查时
void dfs(int s)         //深度优先搜索（邻接表实现），记录时间戳，寻找最短路径
{
    cout 《《 s 《《 " ";
    visited = true;
    time++;
    d = time;
    arcnode * p = Ver.firarc;
    while(p != NULL)
    {
        if(!visited)
        {
            parent = s;
            dfs(p-》vertex);
        }
        p = p-》next;
    }
    time++;
    f = time;
}
void dfs_travel()       //遍历所有顶点，找出所有深度优先生成树，组成森林
{
    for(int i = 1; i 《= n; i++)     //初始化
    {
        parent = -1;
        visited = false;
    }
    time = 0;
    for(int i = 1; i 《= n; i++)     //遍历
        if(!visited)
            dfs(i);
    cout 《《 endl;
}
int main()
{
    int a, b;
    cout 《《 "Enter n and m：";
    cin 》》 n 》》 m;
    Init();
    while(m--)
    {
        cin 》》 a 》》 b;       //输入起点、终点
        Insert2(a, b);        //插入操作
    }
    Show2();    //邻接表
    dfs_travel(); //遍历
    int cnt = 0;     //连通图个数
    for(int i = 1; i 《= n; i++)
        if(parent == -1)
            cnt++;
    printf("%d\n", cnt);
    return 0;
}

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

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