无向图

Author Avatar
Brian Lee 9月 04, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:无向图


定义

无向图是由一组顶点和一组能够将两个顶点相连的边组成的。边仅仅是两个顶点之间的连接,没有方向。

无向图


术语

图基本术语

当两个顶点通过一条边相连时,称这两个顶点是 相邻 的,并称该连接 依附于 这两个顶点。某个顶点的 度数 即为依附于它的边的总数。

子图 是由一幅图的所有边的一个子集(以及它们所依附的所有顶点)组成的图。

在图中,路径 是由边顺序连接的一系列顶点。简单路径 是一条没有重复顶点的路径。 是一条至少含有一条边且起点和终点相同的路径。简单环 是一条除了起点和终点必须相同之外不含有重复顶点和边的环。路径或者环的 长度 为其中包含的边数。

一条连接一个顶点和其自身的边称为 自环

连接同一对顶点的两条边称为 平行边 。(下面内容暂不讨论自环和平行边)

特殊图

如果从任意一个顶点都存在一条路径到达另一个任意顶点,称这幅图是 连通图 。一个 非连通图 由若干连通的部分组成,它们都是其 极大连通子图。一般来说,处理一张图就需要一个个地处理它的连通分量(子图)。

图的 密度 是指已经连接的顶点对占所有可能被连接的顶点对的比例。

二分图 是一种能够将所有结点分为两部分的图,其中图的每条边所连接的两个顶点都分别属于不同的部分。如下图所示,红色结点为一个集合,黑色结点为另一个集合。

二分图

关于树

是一种无环连通图。互不相连的树组成的集合称为 森林 。连通图的 生成树 是它的一幅子图,它含有图中的所有顶点且是一棵树。图的 生成树森林 是它的所有连通子图的生成树的集合。

树

当且仅当一幅含有 $V$ 个结点的图 $G$ 满足下列5个条件之一时,它就是一棵树:

  • $G$ 有 $V-1$ 条边且不含有环
  • $G$ 有 $V-1$ 条边且是连通的
  • $G$ 是连通的,但删除任意一条边都会使它不再连通
  • $G$ 是无环图,但添加任意一条边都会产生一条环
  • $G$ 中的任意一对顶点之间仅存在一条简单路径

图表示方法

使用 邻接表数组 ,它是一个以顶点为索引的列表数组,其中每个元素都是和该顶点相邻的顶点列表。

邻接表


图数据结构

public class Graph {
    private int V;      //顶点个数(Vertices)
    private int E;      //边数(Eage)
    private Bag<Integer>[] adj;     //邻接表
    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<Integer>();
    }
    //输入初始化构造函数
    public Graph() {
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<Integer>();
        int e = in.nextInt();
        for (int i = 0; i < e; i++) {
            int v = in.nextInt();
            int w = in.nextInt();
            addEage(v, w);
        }
    }
    //复制别的图
    public Graph(Graph G) {
        this(G.V());
        this.E = G.E();
        for (int v = 0; v < G.V(); v++) {
            Stack<Integer> reverse = new Stack<>();
            for (int w : G.adj[v])
                reverse.push(w);
            for (int w : reverse)
                adj[v].add(w);
        }
    }
    public int V() {
        return V;
    }
    public int E() {
        return E;
    }
    //添加边
    public void addEage(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    //查找与某顶点相邻的顶点
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
    //返回某顶点的度
    public int degree(int v) {
        return adj[v].size();
    }
    //计算最大度
    public int maxDegree() {
        int max = 0;
        for (int v = 0; v < V; v++)
            max = Math.max(adj[v].size(), max);
        return max;
    }
    //计算平均度
    public int avgDegree() {
        return 2 * E / V;
    }
    //计算自环数量
    public int numOfSelfLoops() {
        int count = 0;
        for (int v = 0; v < V; v++) {
            for (int w : adj[v])
                if (v == w) count++;
        }
        return count;
    }
    public String toString() {
        String s = V + " vertices, " + E + " edges\n";
        for (int v = 0; v < V; v++) {
            s += v + ": ";
            for (int w : this.adj[v])
                s += w + " ";
            s += "\n";
        }
        return s;
    }
}

性能

空间 :$O(V+E)$

添加一条边时间 :$O(1)$

遍历某顶点相邻顶点 :$O(degree(V))$


源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_1_Undirected_Graph/S4_1_2_Graph


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/09/04/undirected_graph/