无向图的数据结构

Class Graphprivate 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 Iterable
       
        adj(int v){        return adj[v];    }}
       
      
     
    

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