经常要用到,放到这里备用!!
//邻接矩阵实现图的广搜和深搜
import java.util.*;
public class Graph {
private int[][] G;//邻接矩阵
private int k;//顶点数目
private boolean[] visited;//判断顶点是否被访问过
public Graph(int k,int[][] G){
this.k=k;
this.G=G;
visited = new boolean[k];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k;
k = sc.nextInt(); //顶点数(顶点为0,1,2,...k-1)
int m=sc.nextInt();//边数
//构建邻接矩阵
int[][] G = new int[k][k];
for (int i = 0; i <m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
G[u][v] = 1;
G[v][u] = 1;//无向图的对称
}
Graph g=new Graph(k,G);
g.bfs(0);
// g.dfs(0);
System.out.println();
}
//广搜
private void bfs(int v) {
//队列用来保存被访问节点的分支节点
Queue<Integer> que = new LinkedList<Integer>();
que.offer(v);
while (!que.isEmpty()) {
v = que.poll();
System.out.print(v+" ");
visited[v] = true;
//将被访问节点的分支节点加入到队列中
for (int i = 0; i < k; i++) {
if (G[v][i] == 1 && !visited[i]) {
que.add(i);
visited[i] = true;
}
}
}
}
//深搜
private void dfs(int v) {
visited[v] = true;
System.out.print(v+" ");
for (int i = 0; i <k; i++) {
//递归调用搜索没有被访问过的当前节点的下一个节点(邻接点)
if (G[v][i] == 1 && !visited[i])
dfs(i);
}
}
}
C:\java>java Graph
6
10
0 1
0 2
0 3
1 2
1 4
2 4
2 5
2 3
3 5
4 5
0 1 2 3 4 5
源码:
- 大小: 5.3 KB
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1745985
NULL 博文链接:https://128kj.iteye.com/blog/1663164
这是我的课程设计,题为《图的遍历》,包括利用邻接矩阵、邻接链表建图,利用深度优先和广度优先遍历图,以及利用prim和克鲁斯卡尔算法生成最小生成树。里面注解详细!
邻接矩阵实现图
NULL 博文链接:https://128kj.iteye.com/blog/1663043
代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图...
图的邻接矩阵存储表示和实现图的邻接矩阵存储表示和实现图的邻接矩阵存储表示和实现,图的邻接矩阵存储表示和实现,图的邻接矩阵存储表示和实现,图的邻接矩阵存储表示和实现,图的邻接矩阵存储表示和实现,图的邻接...
图的邻接矩阵和邻接表实现, 深度搜索, 广度搜索, Dijstra最短路径
图的邻接矩阵实现,用邻接矩阵实现了图,基本操作,主要算法
代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图...
利用networkx,numpy,matplotlib,将邻接矩阵输出为图形。 1,自身确定一个邻接矩阵,然后通过循环的方式添加变,然后输出图像 import networkx as nx import matplotlib.pyplot as plt import numpy as np G = nx...
数据结构类模板无向图邻接矩阵和深度及广度优先搜索遍历
图的邻接矩阵存储和邻接表存储 代码完整 有注释,有需要的可以下载看看,基本是图的邻接矩阵存储和邻接表存储 代码完整
图的邻接矩阵实现,用邻接矩阵实现了图,基本操作,主要算法
数据结构 图的遍历(邻接矩阵) c语言 源代码
图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵图的邻接矩阵
matlab 实现邻接矩阵画图
//以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 int info; //顶点其余的信息 }VertexType; typedef struct { int edges[MAXV][MAXV]; //邻接矩阵 int n,e; //顶点数,弧数 VertexType vexs[MAXV...
领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...