无向图的广度优先遍历和深度优先遍历_C++,C语言_ThinkSAAS
无向图的广度优先遍历和深度优先遍历
无向图的广度优先遍历和深度优先遍历
public class MGraph {
private char[]// 顶点
private int[][]// 存储边的二维数组
private int arcN// 边的数目
private boolean[]// 访问标志数组
// 确定顶点在图中的位置
public int locataVex(char vex) {
for (int i = 0; i & vexs. i++) {
if (vex == vexs[i]) {
return -1;
// 构造无向图
public MGraph(int vexNo) throws IOException {
// 初始化访问数组
visited = new boolean[vexNo];
for (int i = 0; i & vexNo; i++) {
visited[i] =
// 顶点初始化
vexs = new char[vexNo];
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
for (int i = 0; i & vexNo; i++) {
String value = reader.readLine();
char c = value.charAt(0);
// 初始化边的二维数组 默认都不相连 用0来表示
edge = new int[vexNo][vexNo];
for (int i = 0; i & vexNo; i++) {
for (int j = 0; j & vexNo; j++) {
edge[i][j] = 0;
// 输入边的数目
arcNum = Integer.parseInt(reader.readLine());
// 输入边的信息
for (int i = 0; i & arcN i++) {
System.out.println("请输入一条边所依附的两个顶点");
String value1 = reader.readLine();
char v1 = value1.charAt(0);
String value2 = reader.readLine();
char v2 = value2.charAt(0);
int m = locataVex(v1);
int n = locataVex(v2);
edge[m][n] = 1;
edge[n][m] = 1;
// v是图中的某个结点 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
public int FirstAdjVex(char v) {
// 先确定v在顶点数组中的位置
i = locataVex(v);
// 返回第一个邻接定点的序号
for (int j = 0; j & vexs. j++) {
if (edge[i][j] == 1) {
// 如果没有邻接结点 则返回-1
return -1;
// int NextAdjVex(MGraph G,VertexType v,VertexType w)初始条件:
// 图G存在,v是G中某个顶点,w是v的邻接顶点 */
// 返回v的(相对于w的)下一个邻接顶点的序号 如果w是v的最后一个结点 则返回-1
public int NextAdjVex(char v, char w) {
// 先确定v在顶点数组中的位置
i = locataVex(v);
// 返回第一个邻接定点的序号
int j = locataVex(w);
for (j = j + 1; j & vexs. j++) {
if (edge[i][j] == 1) {
// 如果没有邻接结点 则返回-1
return -1;
// 深度优先遍历图 从第v个顶点开始
public void DFsTraverse(int v) {
// 对v尚未访问的邻接顶点进行DFS
for (int i = 0; i & vexs. i++) {
if (visited[i] == false) {
public void DFS(int v) {
// 访问v结点
visited[v] =
System.out.println(vexs[v]);
for (int i = FirstAdjVex(vexs[v]); i &= 0; i = NextAdjVex(vexs[v],
vexs[i])) {
if (visited[i] == false) {
// 广度优先遍历图
public void BFSTraverse() {
// 初始化队列
Queue queue = new LinkedList();
for (int i = 0; i & vexs. i++) {
if (visited[i] == false) {
queue.add(i);
while (!queue.isEmpty()) {
int v = (Integer) queue.remove();
if (visited[v] == false) {
visited[v] =
System.out.println(vexs[v]);
for (int j = FirstAdjVex(vexs[v]); j &= 0; j = NextAdjVex(
vexs[v], vexs[j])) {
if (visited[j] == false) {
queue.add(j);
public char[] getVexs() {
public void setVexs(char[] vexs) {
this.vexs =
public int[][] getEdge() {
public void setEdge(int[][] edge) {
this.edge =
public int getArcNum() {
return arcN
public void setArcNum(int arcNum) {
this.arcNum = arcN
public boolean[] getVisited() {
public void setVisited(boolean[] visited) {
this.visited =
//当用邻接矩阵来表示图的时候，其中图的深度优先遍历的算法时间复杂度是0(n*n)，而BFS 算法的时间复杂度为 O(n+e) ，此处 e 为无向图中边的数目或有向图中弧的数目
PHP开发框架
开发工具/编程工具
服务器环境
ThinkSAAS商业授权：
ThinkSAAS为用户提供有偿个性定制开发服务
ThinkSAAS将为商业授权用户提供二次开发指导和技术支持
让ThinkSAAS更好，把建议拿来。
开发客服微信经检测你所在的网络可能存在爬虫，因资源限制，我们只能拒绝你的请求。
如果你是推酷的用户，可以以继续访问使用。
如有疑问，可将IP信息发送到
请求解封。数据结构，为什么？详解！下面（
）方法可以判断出一个有向图是否有环。A．深度优先遍历
B．拓扑排序
C．求最短路径
D．求关键路径
萌小殇7376
AB－－－－－－－－－－－－－－－－－－－－－－－判断有否环，就是要知道
if( v0 == vm)
即判断 某一个点和查找过程中的另一个点，是否是同一个点我的想法是这样的，希望和大家交流下..1.［深度优先遍历］的概念：假定每一个点都没被访问过。从起点开始，找邻接的点。对每个点，只要存在有向的路径，查找就可以继续，顺藤摸瓜（同时把经过的点给标记成“已访问”）。一旦遇到“已访问”就表示，有环路。2.［拓扑］，一般判断环路都靠它任一有向无环图，必定有拓扑排序（有可能多个）所以如果拓扑排序成功，则无环路；排序失败，则有环路3.［求最短路径］的算法很多，Dijkstra算法,SPFA算法,Floyd-Warshall算法,Johnson算法,Bellman-Ford算法..我想这里指的是Dijkstra算法吧，Dijkstra解决的问题是：指定起始点，计算它到图中各点的最小路径。条件是图中无负权。Dijkstra的想法是“最短路径的前缀一定是最短路径”，于是有环的路径肯定被剔除，但是被剔除的不一定都有环啊，所以没法直接判断这整个图有没有环。4.［求关键路径］求关键路径的前提是无环...一般求关键路径之前会先用［拓扑］验证一下是否有环5.［广度优先搜索］广度优先搜索，好比树的层次遍历。在有向图中，广度优先搜索不能判断环路 —— 无法通过判断“已访问”而断定回路。
为您推荐：
扫描下载二维码> 问题详情
图2-36是带权的有向图G的邻接表。以结点V1出发深度遍历图G所得的结点序列为（1)；广度遍历图G所得的
悬赏：0&答案豆
提问人：匿名网友
发布时间：
图2-36是带权的有向图G的邻接表。以结点V1出发深度遍历图G所得的结点序列为（1)；广度遍历图G所得的结点序列为（2)；G的一种拓扑序列是（3)；从结点V1到V8结点的最短路径是（4)；从结点V1到V8结点的关键路径是（5)。A．V1，V2，V3，V4，V5，V6，V7，V8B．V1，V2，V3，V8，V4，V5，V6，V7C．V1，V2，V3，V8，V4，V5，V7，V6D．V1，V2，V3，V8，V5，V7，V4，V6请帮忙给出正确答案和分析，谢谢！
权威推荐： & &
论文写作技巧
您可能感兴趣的试题
1(22)A．V1，V2，V3，V4，V5，V6，V7，V8B．V1，V2，V4，V6，V5，V3，V7，V8C．V1，V2，V4，V6，V3，V5，V7，V8D．V1，V2，V4，V6，V7，V3，V5，V82(23)A．V1，V2，V3，V4，V5，V6，V7，V8B．V1，V2，V4，V6，V5，V3，V7，V8C．V1，V2，V4，V6，V3，V5，V7，V8D．V1，V2，V4，V6，V7，V3，V5，V8
设有一有向图为G=(V，E)。其中，V={V1，V2，V3，V4，V5}，E={
我有更好的答案
相关考试课程
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……}