算法-数据结构-图的构建(邻接矩阵表示)

发布于:2025-02-26 ⋅ 阅读:(14) ⋅ 点赞:(0)

数据定义


//邻接矩阵表示图
//1.无向图是对称的
//2.有权的把a,到b 对应的位置换成权的值

/**
 * 无向图
 *    A  B
 * A  0  1
 * B  1  0
 */
/**
 * 有向图
 *    A  B
 * A  0  1
 * B  0  0
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 带权图
 *    A  B
 * A  0  1
 * B  0  0
 */
public class GraphM {
    GraphM(List<Character> vList, int [][] gArr){
        v=vList;
        //构造时候顶点个数代表邻接矩阵的长度
        //邻接矩阵存储边是否联通和权
        g=gArr;
    }
    //顶点
    private List<Character> v=new ArrayList<>();
    //边
    private int[][] g;

    public List<Character> getV() {
        return v;
    }

    public int[][] getG() {
        return g;
    }
}

图的创建



import org.springframework.integration.graph.Graph;

import java.util.ArrayList;
import java.util.List;

public class GraphTest {
    //创造一个无向图 边长为6 都联通
    //顶点为6

    public static void wuXiangGraphCreat()
    {
        List<Character> v1=new ArrayList<>();
        for(int i=0;i<6;i++)
        {
            v1.add((char)('A'+i));
        }
        int [][] g1=new int[v1.size()][v1.size()];
        for(int i=0;i<v1.size();i++)
        {
            for(int j=0;j<v1.size();j++)
            {
                if(i!=j)
                {
                    //不是对称轴上都是1
                    g1[i][j]=1;
                }else {
                    //对称轴都是0
                    g1[i][j]=0;
                }
            }
        }
        GraphM wuXiangGraph=new GraphM(v1,g1);
        //打印校验
        //顶点
        System.out.println(wuXiangGraph.getV());
        //边
        for(int i= 0;i<v1.size();i++)
        {
            for(int j=0;j<v1.size();j++)
            {
                System.out.print(wuXiangGraph.getG()[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
    //有向图
    //创造一个有向图 边长为6 A-B B-C C-D D_E E-F
    //顶点为6
    public static void youXiangGraphCreat()
    {
        List<Character> v1=new ArrayList<>();
        for(int i=0;i<6;i++)
        {
            v1.add((char)('A'+i));
        }
        int [][] g1=new int[v1.size()][v1.size()];

        for(int i=0;i<v1.size();i++)
        {
            for(int j=0;j<v1.size();j++)
            {
                if(i==0&&j==1||i==1&&j==2||i==2&&j==3|| i==3&&j==4||i==4&&j==5||
                i==5&&j==0)
                {
                    //边长为6 A-B B-C C-D D_E E-F
                    g1[i][j]=1;
                }else {
                    //其余都是0
                    g1[i][j]=0;
                }
            }
        }
        GraphM wuXiangGraph=new GraphM(v1,g1);
        //打印校验
        //顶点
        System.out.println(wuXiangGraph.getV());
        //边
        for(int i= 0;i<v1.size();i++)
        {
            for(int j=0;j<v1.size();j++)
            {
                System.out.print(wuXiangGraph.getG()[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
    //有向图带权,权每到下一条边加10
    //创造一个有向图 边长为6 A-B B-C C-D D_E E-F
    public static void youXiangGraphQuCreat()
    {
        List<Character> v1=new ArrayList<>();
        for(int i=0;i<6;i++)
        {
            v1.add((char)('A'+i));
        }
        int [][] g1=new int[v1.size()][v1.size()];
        //权
        int tem=0;
        for(int i=0;i<v1.size();i++)
        {
            for(int j=0;j<v1.size();j++)
            {
                if(i==0&&j==1||i==1&&j==2||i==2&&j==3|| i==3&&j==4||i==4&&j==5||
                        i==5&&j==0)
                {
                    //边长为6 A-B B-C C-D D_E E-F
                    g1[i][j]=1+tem;
                    tem+=10;
                }else {
                    //其余都是0
                    g1[i][j]=0;
                }
            }
        }
        GraphM wuXiangGraph=new GraphM(v1,g1);
        //打印校验
        //顶点
        System.out.println(wuXiangGraph.getV());
        //边
        for(int i= 0;i<v1.size();i++)
        {
            for(int j=0;j<v1.size();j++)
            {
                System.out.print(wuXiangGraph.getG()[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        //无向图
        wuXiangGraphCreat();
        youXiangGraphCreat();
        youXiangGraphQuCreat();
    }


}

结果打印