脚本宝典收集整理的这篇文章主要介绍了数据结构-图,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
图(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)。
以上是脚本宝典为你收集整理的数据结构-图全部内容,希望文章能够帮你解决数据结构-图所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。