无向图深度搜索算法

⑴ 基于深度优先搜索算法，写出求无向图连通分量的算法

你可以到网上找一下相关的源码
这个重头写 太恐怖了
没个两三天出不来。

⑵ 你好，请问用邻接表存储无向图，进行深度优先搜索的时间复杂度为什么

设有n个点，e条边
邻接矩阵：矩阵包含n^2个元素，在算法中，共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O(n^2)
邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为
O（n+e）
顺便，对于广度优先算法的时间复杂度，也是这样

⑶ 深度优先搜索的详细解释

事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.
举例说明之：下图是一个无向图，如果我们从A点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B也可以是C,D），则我们可能得到如下的一个访问过程：A->B->E（没有路了！回溯到A)->C->F->H->G->D（没有路，最终回溯到A,A也没有未访问的相邻节点，本次搜索结束）.简要说明深度优先搜索的特点：每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序（具体做法是创建一个list，然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表)，则我们可以得到所谓的"拓扑排序",即topological sort.

⑷ 根据用户的输入建立一个以邻接矩阵存储的无向图，然后转换为邻接表存储，最后进行深度优先搜索生成森林。

编写程序建立该图的邻接矩阵存储。
(2)编写程序建立该图的邻接表存储。(3)基于上图所建的存储结构，编写实现深度优先搜索算法和广度优先搜索算法

⑸ 无向有权的图的深度、广度优先遍历怎么做的啊，他的遍历序列怎么求呢

总结深度优先与广度优先的区别
1、区别

1） 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

2） 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：

先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

3）深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。

广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。

⑹ 无向图的度数与边的关系

当图为无向图是边数为e时，那么度数为2e，当图为有向2图时，那么度数也为2e，所以说边数e和度数之间的关系为2e。

基本图：把有向图D的每条边除去定向就得到一个相应的无向图G，称G为D的基本图。称D为G的定向图

图G的顶点数和边数e的关系：若G是无向图，则0≤e≤n(n-1)/2。若G为无向图，则0≤e≤n(n-1)。

(6)无向图深度搜索算法扩展阅读：

有向图和无向图求解最短路径区别：

1、无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号。

2、有向最短路问题使用双标号法。双标号法是对每一点赋予两个标号：路径和路权。

完全图具有最多的边数。任意一对顶点间均有边相连。

图的遍历算法：

1、广度优先搜索法

图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1，vi2，…，vi t，并均标记已访问过。

然后再按照vi1，vi2，……，vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

2、深度优先搜索法

深度优先搜索法是树的先根遍历的推广，基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。

如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。

⑺ 7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是（）

序列为：1354267。

深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。

广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有节点都被访问完为止。

(7)无向图深度搜索算法扩展阅读：

深度优先遍历的相关要求规定：

1、深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

2、每次深度优先搜索的结果必然是图的一个连通分量。深度优先搜索可以从多点发起，如果将每个节点在深度优先搜索过程中的"结束时间"排序，则可以得到所谓的"拓扑排序"，即topological sort。

3、深度优先搜索用一个数组存放产生的所有状态。把初始状态放入数组中，设为当前状态；扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态。

⑻ 若无向图G=(V,E)中含有7个顶点，要保证G在任何情况下都是连通的，则需要的边数最少是（）条

至少有n条边，正好可以组成一个环。

无向连通图指的是图中的每个顶点都有边与其相连，且图中没有断处，即对无向连通图进行遍历时，仅需要从图中的一个顶点出发。

进行深度优先或广度优先搜索，便可以访问到图中所有的顶点。无向连通图构成的条件是：边数＝顶点数－1。

连通分量的提出是以＂整个无向图不是连通图＂为前提的，因为如果无向图是连通图，则其无法分解出多个最大连通子图，因为图中所有的顶点之间都是连通的。

(8)无向图深度搜索算法扩展阅读：

无向图到连通图的tarjan算法：

如果两个顶点可以相互连接，则这两个顶点是强连接的。如果有向图G的每个顶点都是强连通的，则G是一个强连通图。有向图的强连通子图是强连通分量。

在下面的图中，子图｛1，2，3，4｝是一个强连接组件，因为顶点1、2、3和4是不明确的。｛5｝和｛6｝也是两个强连接的分量。

利用Tarjan算法求有向图的强连通分量。寻找有向图强连通分量的Tarjan算法是以其发明者RobertTarjan的名字命名的。RobertTarjan也发明了寻找双连通分量的Tarjan算法。

Tarjan算法是基于图深度优先搜索算法的。每个强连接组件都是搜索树中的一个子树。在搜索过程中，将当前搜索树中未处理的节点添加到堆栈中，并且可以追溯到堆栈顶部的节点，以确定它们是否是强连接组件。

定义DFN（u）为u查找的节点的序列号（时间戳），Low（u）为u或u的子树可以跟踪的最早栈中节点的序号。

当DFN（u）＝Low（u）时，以u为根的搜索子树上所有节点是一个强连通分量。

⑼ 无向图中求两定点之间所有路径。图用二维数组存储。最好用c语言、给我解题思路也行。谢谢

/*
深度优先搜索算法。
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 图中最多的点数
#define MAX_NODES_NUM 10

// 图中两点最多的路径数
#define MAX_PATHS_BETWEEN_TWO_NODES_NUM (1<<(MAX_NODES_NUM-2))

// 标记无穷远的路径长度
#define INFINTITY (1<<30)

// 标记可以到达的路径长度
#define REACHABLE 1

#define TRUE 1
#define FALSE 0

struct Path
{
int size;
int nodes[MAX_NODES_NUM];
};
/*
获取地图 map 中 点 start 到 点 end 的所有路径

map : 地图
n : 地图的点数
start : 起点
end : 终点
paths : 保存找到的所有从 start 到 end 路径
paths : 保存找到的所有从 start 到 end 路径数目

*/
void getPaths(int map[][MAX_NODES_NUM],int n ,int start,int end,int isNodeUsed[],struct Path paths[],int * pathsNum)
{
int i,j;
struct Path tempPaths[MAX_PATHS_BETWEEN_TWO_NODES_NUM];
int tempPathsNum ;

// 标记当前起点不可用
isNodeUsed[start] = TRUE;

for(i=0;i<n;i++)
{
// 节点不在路径中，且可以到达
if(isNodeUsed[i] == FALSE && map[start][i]== REACHABLE)
{
// 当前起点能直接到达终点
if(i == end)
{
paths[(*pathsNum)].size = 2;
paths[(*pathsNum)].nodes[0] = end;
paths[(*pathsNum)].nodes[1] = start;
(*pathsNum)++;
}
// 当前起点能不能直接到达终点，尝试当前节点通过其他节点达到终点
else
{
// 递归计算从当前起点到达终点的所有路径
tempPathsNum = 0;
getPaths(map,n,i,end,isNodeUsed,tempPaths,&tempPathsNum);

// 处理找到的，从当前起点到达终点的所有路径
for(j=0;j<tempPathsNum;j++)
{
// 在当前起点到达终点的所有路径中，添加当前起点
tempPaths[j].nodes[tempPaths[j].size] = start;
tempPaths[j].size ++;

// 合并到最终的路径中
paths[(*pathsNum)] = tempPaths[j];
(*pathsNum)++;
}
}
}
}
isNodeUsed[start] = FALSE;
}

int main(int argc, char *argv[])
{
int map[MAX_NODES_NUM][MAX_NODES_NUM];
int isNodeUsed[MAX_NODES_NUM];
struct Path paths[MAX_PATHS_BETWEEN_TWO_NODES_NUM];
int pathsNum;

int i,j;
int start,end;
int a,b;
int n,m;

// 读取点数，路径数
while(scanf("%d%d",&n,&m)!=EOF)
{
// 初始化图
for(i=0;i<n;i++)
{
isNodeUsed[i] = FALSE;
for(j=0;j<n;j++)
{
map[i][j] = INFINTITY;
}
}

// 读入路径
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
// 标记 a b 间有路径，注意是无向图，标记两次
map[a][b] = REACHABLE;
map[b][a] = REACHABLE;
}

// 要连接的两个点
scanf("%d%d",&start,&end);

// 查找点 start 到点 end 的所有路径
pathsNum = 0;
getPaths(map,n,start,end,isNodeUsed,paths,&pathsNum);

// 打印点 start 到点 end 的所有路径
for(i=0;i<pathsNum;i++)
{
for(j=paths[i].size-1;j>=1;j--)
{
printf("%d -> ",paths[i].nodes[j]);
}
printf("%d\n",paths[i].nodes[j]);
}
}

return 0;
}

/*
测试用数据：
1）首先输入点数 n,路径条数 m，

2）接下来输入 m 对点的编号，每对点 a,b 表示点 a 和 点 b 之间有一条路
点的编号从 0 开始到 n-1.

3）最后输入要连接的两个点

输入：
6 14

0 1
0 2
1 0
1 3
2 0
2 4
2 5
3 1
3 5
4 2
4 5
5 2
5 3
5 4

0 5

输出：
0 -> 1 -> 3 -> 5
0 -> 2 -> 4 -> 5
0 -> 2 -> 5
*/

⑽ 无向图中查找环的算法有哪些

比较直观的办法是，从初始结点 S 开始，用深度优先的方法遍历图的结点，如果在这个过程中，你遇到了一个先前就已经发现过的结点（假定它叫 V），说明存在一个环。
如果你想输出这个环，那么就从 V 沿路返回，直到又遇到 V，途中经过的所有结点就组成了这个环。