邻接矩阵

1.基本定义

对图中n个顶点采用顺序存储，点与点之间的关系用一个n*n的矩阵表示，a_ij=1代表<i,j>存在，a_ij=0或∞反之。

[站外图片上传中...(image-af252-1565945712323)]

还可以扩展到带权图，即1换为该边的权。

带权图的邻接矩阵

• 邻接矩阵图类MatrixGraph

class MatrixGraph{
    char[] vexs;//顶点表
    int[][]  edges;//邻接矩阵
    int vnum;//点数
    int enum;//边数
    
    Gragh(int v,int e){
        vexs=new char[v];
        edges=new int[v][v];
        vnum=v;
        enum=e;
    }    
    /*
    成员函数
    */    
}

2.创建矩阵

• 成员函数——建立一个无向图的邻接矩阵

public void Creat_MatrixGraph(){
    Scanner sc=new Scanner(System.in);
    System.out.println("input vertex number:");
    this.vnum=sc.nextInt();
    System.out.println("input edge number:");
    this.enum=sc.nextInt();
    System.out.println("input vxes[]:");    
    for(int i=0;i<vnum;i++){
        this.vxes[i]=(char)System.in.read();
    }
    
    for(int i=0;i<vnum;i++)
        for(int j=0;j<vnum;j++)
           this.edges[i][j]=0;
    
    System.out.println("input edges[][]:");        
    for(int i=0;i<enum;i++){
        int m=sc.nextInt();
        int n=sc.nextInt();
        this.edges[m][n]=1;
        this.edges[n][m]=1;//有向图这步省去
    }
}

解读：先输入点和边的个数，然后依次输入点的值，最后输入边，两个点的下标代表一条边，注意从0开始。

邻接表

1.基本定义

邻接表是图的一中链式存储方式。对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点v_i的边。每个顶点构成头结点顺序存储，每个头结点后面又有单独的链表，跟着表结点（边）。

[站外图片上传中...(image-17de77-1565945712323)]

• 邻接表图类ListGraph

public class ListGraph{
    //边
    class ENode{
        int ivex;//该边指向的点的位置
        ENode nextEdge;//指向下一条边的指针
    }
    
    //顶点
    class VNode{
        char data;//顶点信息
        ENode firstEdge;//指向第一条依附该顶点的边        
    }
    
    VNode mVexs[];//顶点数组
    int vlen;//点数
    int elen;//边数
    /*
    成员函数
    */
   
}

2.创建邻接表

• 成员函数——建立无向图的邻接表

public void creat_ListGraph(){
    Scanner sc=new Scanner(System.in);
    System.out.println("input vertex number:");
    this.vlen=sc.nextInt();
    System.out.println("input edge number:");    
    this.elen=sc.nextInt();
    
    mVexs=new VNode[vlen];
    //顶点数组初始化
    System.out.println("input mVexs[]:");
    for(int i=0;i<mVexs.length;i++){
        mVexs[i]=new VNode();
        mVexs[i].data=(char)System.in.read();
        mVexs[i].firstEdge=null;
    }
    
    //边初始化
    System.out.println("input edges:");
    for(int i=0;i<elen;i++){
        int m=sc.nextInt();
        int n=sc.nextInt();
        
        ENode a=new ENode();
        a.ivex=n;
        a.nextEdge=null;
        if(mVexs[m].firstEdge==null)
            mVexs[m].firstEdge=a;
        else
            link(mVexs[m].firstEdge,a);
            
        ENode b=new ENode();
        b.ivex=m;
        b.nextEdge=null;
        if(mVexs[n].firstEdge==null)
            mVexs[n].firstEdge=b;
        else
            link(mVexs[n].firstEdge,b);
        
    }
}

• 成员函数——连接边

public void link(ENode a,ENode b){
    ENode n=a;
    while(n.nextEdge!=null)
        n=n.nextEdge;
    n.nextEdge=b;
}