无向图的实现和一些常用算法（一）

Lsnsh 发布于2019-08-14 12:08 / 2042人阅读

摘要：无向图的数据结构边数边的数目邻接表，存储与该节点相邻的节点，一个链表数组无向图的创建一个含有个节点但不含边的无向图从输入流中读取一幅图返回图中有多少个节点边数添加一条边节点相邻的所有顶点对象的字符串表示实现很简单邻接表既然实现了图这种数据结

无向图的数据结构

Class Graph
private final int V;  边数
private int E; 边的数目
private Bag[] adj; 邻接表，存储与该节点相邻的节点，一个链表数组

无向图的API

public class Graph
    Graph(int V)   创建一个含有V个节点但不含边的无向图
    Graph(In)    从输入流中读取一幅图
    int V()      返回图中有多少个节点
    int E()      边数
    addEdge(int v,int w)  添加一条边
    Iterable adj(int v)   V节点相邻的所有顶点
    String toString       对象的字符串表示

实现很简单

package Graph;

import In.In;

public class Graph {
    private final int V;
    private int E;
    private Bag[] adj;   //邻接表

    public Graph(int V){
        this.V = V;
        this.E = 0;
        adj = (Bag[]) new Bag[V];
        for(int v = 0;v < V;v++){
            adj[v] = new Bag();
        }
    }

    public Graph(In in){
        this(in.readInt());
        int E = in.readInt();
        for(int i = 0;i < E;i++){
            int v = in.readInt();
            int w = in.readInt();
            addEdge(v,w);
        }
    }

    public int V(){ return V;}
    public int E(){ return E;}

    public void addEdge(int v,int w){
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterableadj(int v){
        return adj[v];
    }

}

既然实现了图这种数据结构，那么接下来可以考虑图的处理算法了。见下一篇

云服务器 GPU云服务器 linux的一些常用命令 html实现图的遍历图的操作的实现c语言 js中饼状图的实现

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64312.html

算法（第4版） Chapter 4.1 无向图

摘要：边仅由两个顶点连接，并且没有方向的图称为无向图。用分隔符当前为空格，也可以是分号等分隔。深度优先算法最简搜索起点构造函数找到与起点连通的其他顶点。路径构造函数接收一个顶点，计算到与连通的每个顶点之间的路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter...

kamushin233 2019-08-14 17:14 评论0 收藏0
无向图的处理算法（四）连通分量

这篇讲的是连通分量，连通分量是深度优先搜索算法的一个应用。每进行了一次dfs，就会找到一条连通分量。定义如下的API public class CC CC(Graph g) 预处理构造函数 boolean connected(int v,in w) v和w连通吗 int count() 改图中的连通分量个数 int id(int v) ...

asce1885 2019-08-14 12:10 评论0 收藏0
算法第四版4.1-无向图详解

摘要：树是一副无环连通图。互不相连的树组成的集合称为森林。表示无向图的数据类型图的基本操作的两个构造，得到顶点数和边数，增加一条边。该方法不符合第一个条件，上百万个顶点的图是很常见的空间不满足。四种重要的图模型：无向图（简单连接）有向图（连接有方向性）加权图（连接带有权值）加权有向图（连接既有方向性又带有权值）无向图定义：由一组顶点和一组能够将两个顶点相连的边组成。特殊：...

scola666 2019-08-14 17:53 评论0 收藏0
数据结构与算法——图

摘要：什么是图前面说完了树这种数据结构，接下来在看看一种更加复杂的非线性数据结构图。其实图这种数据结构比较适合用来存储我们常用的微信微博好友关系。 1. 什么是图？前面说完了树这种数据结构，接下来在看看一种更加复杂的非线性数据结构——图。先看看下面图这种数据结构的图片演示吧： showImg(https://img-blog.csdnimg.cn/20190319204147662.p...

Paul_King 2019-08-16 16:22 评论0 收藏0
无向图的处理算法（三）

摘要：那还有一个重要的问题就是，从到是否存在一条路径，如果有找出其中最短的那条。最短路径问题当然这路考虑的是每条边的都是权值为的情况。解决这个问题的算法就是广度优先搜索算法下面给出其实现代码，其中的使用了一个队列用来保存需要遍历的顶点。上一篇讲了从一个顶点到另一个顶点是否存在路径，用的时深度优先搜索。那还有一个重要的问题就是，从s到v是否存在一条路径，如果有找出其中最短的那条。最短路径问题...

JeOam 2019-08-14 12:10 评论0 收藏0