图(Graph),是一种复杂的非线性表结构。
图中的元素我们就叫做顶点(vertex)
图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边(edge)
跟顶点相连接的边的条数叫做度(degree)
图这种结构有很广泛的应用,比如社交网络,电子地图,多对多的关系就可以用图来表示。
有向图
:边有方向的图,比如A点到B点的直线距离,微信的添加好友是双向的
无向图
:边无方向的图,比如网络拓扑图
带权图
:在带权图中,每条边都有一个权重(weight),我们可以通过这个权重 来表示 一些可度量的值
邻接矩阵的底层是一个二维数组
如果顶点 i 到顶点 j 之间,有一条箭头从顶点 i 指向顶点 j 的边,那我们就将 A[i][j]标记为 1。同理,如 果有一条箭头从顶点 j 指向顶点 i 的边,我们就将 A[j][i]标记为 1
数组中就存储相应的权重
/** * 邻接矩阵实现 */ public class Graph1 { private List vertexList;//存储点的链表 private int[][] edges;//邻接矩阵,用来存储边 private int numOfEdges;//边的数目 public Graph1(int n) { //初始化矩阵,一维数组,和边的数目 edges=new int[n][n]; vertexList=new ArrayList(n); numOfEdges=0; } //得到结点的个数 public int getNumOfVertex() { return vertexList.size(); } //得到边的数目 public int getNumOfEdges() { return numOfEdges; } //返回结点i的数据 public Object getValueByIndex(int i) { return vertexList.get(i); } //返回v1,v2的权值 public int getWeight(int v1,int v2) { return edges[v1][v2]; } //插入结点 public void insertVertex(Object vertex) { vertexList.add(vertex); } //插入边 public void insertEdge(int v1,int v2,int weight) { edges[v1][v2]=weight; numOfEdges++; } public static void main(String args[]) { int n=4,e=4;//分别代表结点个数和边的数目 String labels[]={"V1","V1","V3","V4"};//结点的标识 Graph1 graph=new Graph1(n); for(String label:labels) { graph.insertVertex(label);//插入结点 } //插入四条边 graph.insertEdge(0, 1, 2); graph.insertEdge(0, 2, 5); graph.insertEdge(2, 3, 8); graph.insertEdge(3, 0, 7); System.out.println("结点个数是:"+graph.getNumOfVertex()); System.out.println("边的个数是:"+graph.getNumOfEdges()); } }
用邻接矩阵来表示一个图,虽然简单、直观,但是比较浪费存储空间,
于无向图来说,如果 A[i][j]等于 1,那 A[j][i]也肯定等于 1。实际上,我们只需要存储一个就可以了。 也就是说,无向图的二维数组中,如果我们将其用对角线划分为上下两部分,那我们只需要利用上面或 者下面这样一半的空间就足够了,另外一半白白浪费掉了
还有,如果我们存储的是稀疏图(Sparse Matrix),也就是说,顶点很多,但每个顶点的边并不多, 那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户,对应到图上就是好几亿的顶点。 但是每个用户的好友并不会很多,一般也就三五百个而已。如果我们用邻接矩阵来存储,那绝大部分的 存储空间都被浪费了
每个顶点对应一条链表,链表中存储的是与这个顶点相连接的其他顶点。
图中画的是一个有向图的邻接表存储方式,每个顶点对应的链表里面,存储的是指向的顶点
/** * 顶点 */ public class Vertex { String name; Edge next; //顶点名称 //从该定点出发的边 public Vertex(String name, Edge next){ this.name = name; this.next = next; } } /** *边 */ public class Edge { String name; int weight; Edge next; //被指向的顶点 //弧的权值 //被指向的下一个边 public Edge(String name, int weight, Edge next){ this.name = name; this.weight = weight; this.next = next; } } public class Graph2 { Map<String, Vertex> vertexsMap; Graph2(){ this.vertexsMap = new HashMap<>(); } //存储所有的顶点 加弧 public void insertVertex(String vertexName){ Vertex vertex = new Vertex(vertexName, null); vertexsMap.put(vertexName, vertex); //添加顶点 } public void insertEdge(String begin, String end, int weight){ //添 } Vertex beginVertex = vertexsMap.get(begin); if(beginVertex == null){ beginVertex = new Vertex(begin, null); vertexsMap.put(begin, beginVertex); } Edge edge = new Edge(end, weight, null); if(beginVertex.next == null){ beginVertex.next = edge; }else{ Edge lastEdge = beginVertex.next; while(lastEdge.next != null){ lastEdge = lastEdge.next; } lastEdge.next = edge; }
深度优先搜索,从起点出发,从规定的方向中选择其中一个不断地向前走,直到无法继续为止,然后尝
试另外一种方向,直到最后走到终点。就像走迷宫一样,尽量往深处走。
DFS 解决的是连通性的问题,即,给定两个点,一个是起始点,一个是终点,判断是不是有一条路径能 从起点连接到终点。起点和终点,也可以指的是某种起始状态和最终的状态。问题的要求并不在乎路径 是长还是短,只在乎有还是没有
假设我们有这么一个图,里面有A、B、C、D、E、F、G、H 8 个顶点,点和点之间的联系如下图所示, 对这个图进行深度优先的遍历。
必须依赖栈(Stack),特点是后进先出(LIFO)。
直观地讲,它其实就是一种“地毯式”层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近 的,依次往外搜索。
假设我们有这么一个图,里面有A、B、C、D、E、F、G、H 8 个顶点,点和点之间的联系如下图所示, 对这个图进行深度优先的遍历。
依赖队列(Queue),先进先出(FIFO)。