福田网站建设龙岗网站建设,网站集约化建设 统一出口,重庆今天新闻发布会直播,wordpress ico不显示不出来前言#xff1a; 邻接矩阵是数学和计算机科学中常用的一种表示方式#xff0c;用来表述有向图或无向图#xff0c;一张图由一组顶点#xff08;或结点#xff09;和一组表组成#xff0c;用邻接矩阵就能表示这些顶点间存在的边的关系
1.图的概念 对于图而言#xff0c;…前言 邻接矩阵是数学和计算机科学中常用的一种表示方式用来表述有向图或无向图一张图由一组顶点或结点和一组表组成用邻接矩阵就能表示这些顶点间存在的边的关系
1.图的概念 对于图而言是数据结构中最复杂的结构而是在做题的过程中最大的难点在于BFS和DFS的过程图从两个维度划分可以有有向图、无权图、带权图。
1.有向图和无向图 在无向图中边没有方向表示的是双向关系换句话来说如果两个顶点或结点之间存在边那么这两个顶点就互相连接 例如如果你正在建模一个社交网络你可能会使用无向图因为友谊是双向如果1是2的朋友那么2也是1的朋友如图示 有向图与无向图相反有向图的边有方向表示单向关系在这种图中如果存在从1到2的边那不一定存在从2到1的边如图所示 2.无权图和带权图
在图论中图可以是无权的也可以是带权的这主要取决于边是否具有与其关联的值权重
无权图 在无权图中边没有权重或者说所有边的权重都是相同的你只关心两个节点顶点之间是否存在边而不是关心边的长度或者是成本比如社交网络的人际关心就可以用无权图来表示如果两个人是朋友就有一条边连接它们所有的边都被视为相等 带权图 与无权图相对带权图中的边有各自的权重这个权重可以表示很多的意义如距离、时间、成本等等取决于你要了解的问题比如在导航应用中每个结点可以代表一个结点边的权重就可以代表两个地点之间的距离或者是行驶时间在这种情况下你不仅关心结点之间是否存在边还关心这个边的权重是多少 2.邻接矩阵的概念 注意对于邻接矩阵而言 不需要去考虑是有向的还是无向的统一都可以理解成有向的因为有向图可以兼容无向图对于无向图而言只不过这个矩阵按照主对角线对称因为A到B有变则必然B到A有边
1.无权图的邻接矩阵
在这样一个矩阵里
1.矩阵中的行和列都是对应图中的一个顶点
2.如果顶点A到顶点B有一条边这里是单向的则对应矩阵单元为1
3.如果顶点A到顶点B没有边则对应的矩阵单元就为0
如下图所示 从这个矩阵中我们可以看出A节点能够到达B、D节点B节点能够到达A、C节点C节点能够到达B、D节点D节点能够到达A、C节点所以如图所示 2.带权图的邻接矩阵 在带权图的邻接矩阵中每个矩阵元素表示一个有向边的权值如果不存在从一个结点到另一个节点的边则通常将其表示为特殊的值0、-1均可
A-B 权重为3A-C 权重为7B-A 权重为4B-D 权重为1C-D 权重为2D-A 权重为1
该邻接矩阵为 3.邻接矩阵的代码实现
/*** 图的表示--使用邻接矩阵*/
public class Graph01 {private char[] V;//顶点上的值private Vertex[] vertexs;//顶点数组private int N;//邻接矩阵private int[][] adj;//图的构造函数public Graph01(char[] arr) {//{A,E,F,G,H,P}//拿到数组的长度int length arr.length;this.N length;V new char[length];//arr元素赋值 到Vthis.V Arrays.copyOf(arr, length);//构建图中的结点vertexs new Vertex[length];for (int i 0; i length; i) {vertexs[i] new Vertex(i,this.V[i]);//}this.adj new int[length][length];}//打印邻接矩阵public void show() {System.out.print( );for (int i 0; i this.N; i) {System.out.format(%4c, this.V[i]);}System.out.println();for (int i 0; i this.N; i) {System.out.format(%4c,this.V[i]);for (int j 0; j this.N; j) {System.out.format(%4s, this.adj[i][j] 0?(this.adj[i][j]):-);}System.out.println();}}/*** 创建顶点类*/private class Vertex {char v;//值int index;//索引public Vertex(int index, char c) {this.index index;this.v v;}}public static void main(String[] args) {char arr[] {A, E, F, G, H, P};//构建graph01Graph01 graph01 new Graph01(arr);//进行连接int[][] adjMatrix graph01.adj;adjMatrix[0][1]1;adjMatrix[0][2]1;adjMatrix[0][3]1;adjMatrix[1][0]1;adjMatrix[1][3]1;adjMatrix[1][4]1;adjMatrix[2][0]1;adjMatrix[3][0]1;adjMatrix[3][1]1;adjMatrix[3][4]1;adjMatrix[3][5]1;adjMatrix[4][1]1;adjMatrix[4][3]1;adjMatrix[4][5]1;adjMatrix[5][3]1;adjMatrix[5][4]1;graph01.show();}
*** 图的表示--使用邻接矩阵*/
public class Graph02 {private char[] V;//顶点上的值private Vertex[] vertexs;//顶点数组private int N;//邻接矩阵private ListInteger[] adj;//图的构造函数public Graph02(char[] arr) {//{A,E,F,G,H,P}//拿到数组的长度int length arr.length;this.N length;V new char[length];//arr元素赋值 到Vthis.V Arrays.copyOf(arr, length);//构建图中的结点vertexs new Vertex[length];for (int i 0; i length; i) {vertexs[i] new Vertex(i, this.V[i]);}this.adj new List[length];for (int i 0; i this.N; i) {this.adj[i]new ArrayList();}}//打印邻接矩阵public void show() {System.out.println( );for (int i 0; i this.N; i) {System.out.format(%-4c, this.V[i]);//拿到邻接表相邻结点的集合ListInteger linkedList this.adj[i];for (int j 0; j linkedList.size(); j) {System.out.print(this.V[linkedList.get(j)] ----);}System.out.println();System.out.format(%-4d,vertexs[i].index);for (int j 0; j linkedList.size(); j) {System.out.print(vertexs[linkedList.get(j)].index ----);}System.out.println();}}/*** 创建顶点类*/private class Vertex {char v;//值int index;//索引int weight;//权值public Vertex(int index, char c) {this.index index;this.v v;this.weight weight;}public Vertex(int index) {}}public static void main(String[] args) {char arr[] {A, E, F, G, H, P};//构建graph01Graph02 graph02 new Graph02(arr);//邻接表ListInteger[] adj graph02.adj;adj[0].add(1);adj[0].add(2);adj[0].add(3);adj[1].add(0);adj[1].add(3);adj[1].add(4);adj[2].add(0);adj[3].add(0);adj[3].add(1);adj[3].add(4);adj[3].add(5);adj[4].add(1);adj[4].add(3);adj[4].add(5);adj[5].add(3);adj[5].add(4);graph02.show();}
leetcode题单
省份数量
//进行广度优先搜索public int findCircleNum(int[][] isConnected) {if(isConnectednull||isConnected.length0){return 0;}int privice0;QueueInteger queuenew LinkedList();boolean[] visitednew boolean[isConnected.length];Arrays.fill(visited,false);//对每一个城市进行遍历得到每一个城市与相连的城市表for (int i 0; i isConnected.length; i) {//如果是没有遍历过的城市则进行如下操作if(!visited[i]){queue.offer(i);while(!queue.isEmpty()){int indexqueue.poll();visited[index]true;for (int j 0; j isConnected.length; j) {if(isConnected[index][j]1!visited[j]){queue.offer(j);}}}privice;} }return privice;}
矩阵中的最长递增路径
LCP07.传递信息
