欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

无向图

程序员文章站 2022-06-03 18:31:27
...

1. 无向图的概念

图由vertex和edge组成。即众多的vertex由edge相连接,就了图。
无向图中edge不指示方向,仅表示两个vertex是相互连接的关系。

无向图

2. 无向图数据结构的表示方法

我们用一维数组来表示无向图。具体方法是:
首先,数组的序号就可以代表无向图中的vertex。即有N个vertex,我们的数组就设置到N-1。
然后,每个vertex(即数组序号)对应内容是该vertex所有连接对象。我们用bag作为容器,保存到数组内。
代码如下:
import edu.princeton.cs.algs4.In;
import java.util.Iterator;

public class Graph
{
    private final int V;
    private int E;
    //最重要的数据结构,内容为bag的数组。
    private Bag<Integer>[] adj;

    //输入vertex的个数V,生成长度为V的数组,内容(bag)为空。
    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>();
    }

    //这个是根据输入的文本而进行操作,详情见edu.princeton.cs.algs4.In。
    //首先读取vertex的个数V,执行上面的constructor。然后读取edge的个数E。
    //读取每一对连接着的vertex,分别在其对应的包内将对方添加进去。
    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);
        }
    }

    //互相将对方添加到自己的包内。注意edge又重新加了一遍。
    public void addEdge(int v, int w)
    {
        adj[v].addElement(w);
        adj[w].addElement(v);
        E++;
    }

    public int V()
    { return V; }

    public int E()
    { return E; }

    public Iterable<Integer> adj(int v)
    { return adj[v]; }
}

//自己定义的bag。
class Bag<T> implements Iterable<T>
{
    private Node first;
    private int N = 0;

    private class Node
    {
        T item;
        Node next;
    }

    public void addElement(T item)
    {
        if (first == null) {
            first = new Node();
            first.item = item;
        } else {
            Node oldFirst = first;
            first = new Node();
            first.item = item;
            first.next = oldFirst;
        }

        N++;
    }

    public Iterator<T> iterator()
    { return new MyIterator(); }

    class MyIterator implements Iterator<T>
    {
        Node begin = first;

        public boolean hasNext()
        { return begin == null; }

        public T next()
        {
            T item = begin.item;
            begin = begin.next;
            return item;
        }
    }
}