無(wú)向圖的實(shí)現(xiàn)和一些常用算法（一）

Lsnsh 發(fā)布于2019-08-14 12:08 / 2050人閱讀

摘要：無(wú)向圖的數(shù)據(jù)結(jié)構(gòu)邊數(shù)邊的數(shù)目鄰接表，存儲(chǔ)與該節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，一個(gè)鏈表數(shù)組無(wú)向圖的創(chuàng)建一個(gè)含有個(gè)節(jié)點(diǎn)但不含邊的無(wú)向圖從輸入流中讀取一幅圖返回圖中有多少個(gè)節(jié)點(diǎn)邊數(shù)添加一條邊節(jié)點(diǎn)相鄰的所有頂點(diǎn)對(duì)象的字符串表示實(shí)現(xiàn)很簡(jiǎn)單鄰接表既然實(shí)現(xiàn)了圖這種數(shù)據(jù)結(jié)

無(wú)向圖的數(shù)據(jù)結(jié)構(gòu)

Class Graph
private final int V;  邊數(shù)
private int E; 邊的數(shù)目
private Bag[] adj; 鄰接表，存儲(chǔ)與該節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，一個(gè)鏈表數(shù)組

無(wú)向圖的API

public class Graph
    Graph(int V)   創(chuàng)建一個(gè)含有V個(gè)節(jié)點(diǎn)但不含邊的無(wú)向圖
    Graph(In)    從輸入流中讀取一幅圖
    int V()      返回圖中有多少個(gè)節(jié)點(diǎn)
    int E()      邊數(shù)
    addEdge(int v,int w)  添加一條邊
    Iterable adj(int v)   V節(jié)點(diǎn)相鄰的所有頂點(diǎn)
    String toString       對(duì)象的字符串表示

實(shí)現(xiàn)很簡(jiǎn)單

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];
    }

}

既然實(shí)現(xiàn)了圖這種數(shù)據(jù)結(jié)構(gòu)，那么接下來(lái)可以考慮圖的處理算法了。見(jiàn)下一篇