Java教程

数据结构-图

本文主要是介绍数据结构-图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、概念

图(Graph),是一种复杂的非线性表结构。

图中的元素我们就叫做顶点(vertex)

图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边(edge)
跟顶点相连接的边的条数叫做度(degree)

image-20220423001801867

图这种结构有很广泛的应用,比如社交网络,电子地图,多对多的关系就可以用图来表示。

有向图:边有方向的图,比如A点到B点的直线距离,微信的添加好友是双向的

无向图:边无方向的图,比如网络拓扑图

带权图:在带权图中,每条边都有一个权重(weight),我们可以通过这个权重 来表示 一些可度量的值

image-20220423001934043

二、图的存储

2.1 邻接矩阵(Adjacency Matrix)

邻接矩阵的底层是一个二维数组

image-20220423002022234

无向图:如果顶点 i 与顶点 j 之间有边,我们就将 A[i][j]和 A[j][i]标记为 1

image-20220423002050723

有向图:

如果顶点 i 到顶点 j 之间,有一条箭头从顶点 i 指向顶点 j 的边,那我们就将 A[i][j]标记为 1。同理,如 果有一条箭头从顶点 j 指向顶点 i 的边,我们就将 A[j][i]标记为 1

image-20220423002142415

带权图:

数组中就存储相应的权重

image-20220423002207286

代码

/**
* 邻接矩阵实现 */
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());
    }
  
}

2.2 邻接表

用邻接矩阵来表示一个图,虽然简单、直观,但是比较浪费存储空间,

于无向图来说,如果 A[i][j]等于 1,那 A[j][i]也肯定等于 1。实际上,我们只需要存储一个就可以了。 也就是说,无向图的二维数组中,如果我们将其用对角线划分为上下两部分,那我们只需要利用上面或 者下面这样一半的空间就足够了,另外一半白白浪费掉了

还有,如果我们存储的是稀疏图(Sparse Matrix),也就是说,顶点很多,但每个顶点的边并不多, 那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户,对应到图上就是好几亿的顶点。 但是每个用户的好友并不会很多,一般也就三五百个而已。如果我们用邻接矩阵来存储,那绝大部分的 存储空间都被浪费了

image-20220423002428142

  • 每个顶点对应一条链表,链表中存储的是与这个顶点相连接的其他顶点。

  • 图中画的是一个有向图的邻接表存储方式,每个顶点对应的链表里面,存储的是指向的顶点

    image-20220423002508750

代码

/**
* 顶点 */
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 个顶点,点和点之间的联系如下图所示, 对这个图进行深度优先的遍历。

image-20220423002809966

必须依赖栈(Stack),特点是后进先出(LIFO)。

直观地讲,它其实就是一种“地毯式”层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近 的,依次往外搜索。

假设我们有这么一个图,里面有A、B、C、D、E、F、G、H 8 个顶点,点和点之间的联系如下图所示, 对这个图进行深度优先的遍历。

image-20220423002943534

依赖队列(Queue),先进先出(FIFO)。

这篇关于数据结构-图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!