图及其简单创建

喜欢ヅ旅行 2023-07-21 05:49 2阅读 0赞

## 图 ##

#### 定义 ####

一个二元组，G=(V,E)  
V：顶点的有限集  
E：边的关系的有限集  
分为无向图（边）和有向图（弧）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]

#### 特点 ####

图是一种网状的数据结构，结点之间的关系是任意的，即图中任何两个结点之间都可能直接相关

#### 基本术语 ####

顶点：图中的数据元素  
边/弧：两个顶点之间的关系  
完全图：有n(n-1)/2条边的无向图  
有向完全图：有n(n-1)条边的有向图  
稠密图：有很多边或弧的图  
稀疏图：有很少边或弧的图  
子图：对于G=(V,E)和G’=(V’,E’)，若V’是V的子集且E’是E的子集，则称G’为G的子图。  
权：与图的边相关的数值  
网：带权的图  
邻接点：对于G=(V,E)，若存在(x,y)∈E，无向图称x和y相邻接，有向图称x邻接到y  
顶点的度：与该点相关联边的数目，有向图中分为入度和出度  
路径：在图G中，从顶点x经过一系列顶点到达顶点y，则称顶点序列（x，…，y）为x到y的路径  
路径长度：非带权图为路径边的条数，带权图为路径上各边权之和  
回路（环）：第一个顶点和最后一个顶点相同的路径  
连通：在无向图中，若从x到y存在路径，称x和y是连通的  
连通图：无向图G中，如果任意两个顶点x，y之间都是连通的，称图G为连通图  
连通分量：无向图中的极大连通子图  
强连通图：有向图中任意两个顶点x，y之间都是相互可达的，称图G是强连通图  
强连通分量：有向图中的极大连通子图  
树图：极小连通子图（无环图），n个顶点，n-1条边

## 图的简单存储结构 ##

#### 数组表示法（邻接矩阵） ####

①邻接矩阵：表示顶点之间相邻关系的矩阵  
存在（x，y）的边即axy=1（或权值），否则axy=0（或∞）  
②邻接矩阵的特点  
无向图的邻接矩阵是一个对称矩阵  
无向图的邻接矩阵的第i行/列的非零/∞元素个数为第i个顶点的度  
有向图的邻接矩阵第i行的非零/∞元素个数为出度，第i列为入度  
如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]  
例：

//使用数组存储图
    class SimpleMap{
     	//顶点个数
     	public int num;
     	//图
     	public int[][] map; 
    }
    
    public static final int MAX=100000;
    
     /**
      * 根据文件内容，生成一个无向图图
      * @param file  文件路径
      * @return 存储图数据的二阶数组
      */
     public static SimpleMap createMap(String file){
      	SimpleMap sMap = new SimpleMap();
      	BufferedReader bReader = null;
      	try {
       		bReader = new BufferedReader(new FileReader(file));
       		String data = bReader.readLine();
       		int number = Integer.parseInt(data);
    		sMap.num = number;
    		sMap.map = new int[number][number];
    		 //初始化图
    		for(int i=0; i<number; i++) {
    	    		for(int j=0; j<number; j++) {
    	     			sMap.map[i][j] = MAX;
    	     			if(i == j) {
    	      				sMap.map[i][j] = 0;
    	     			}
    	    		}  
    	   	}
    	   	//读取文件，初始化边
    	   	while((data=bReader.readLine()) != null) {
    	    		String[] value = data.split("&");
    	    		int x = Integer.parseInt(value[0])-1;
    	    		int y = Integer.parseInt(value[1])-1;
    	    		int info = Integer.parseInt(value[2]);
    	    		sMap.map[x][y] = info;
    	    		sMap.map[y][x] = info;
    	   	}
    	  } catch (Exception e) {
    	   	e.printStackTrace();
    	  } finally {
    	    	try {
    	    		if(bReader != null) {
    	     			bReader.close();
    	     		}
    	    	} catch (IOException e) {
    	     		e.printStackTrace();
    	    	}
    	  }
    	  return sMap;
    }

文件存储样式：  
![在这里插入图片描述][20200402165155261.png]  
第一行为顶点个数，用以决定二阶矩阵的大小；后面的即1----2,权值为6

#### 邻接表（邻接链表） ####

头结点：data（顶点），firstarc（指针域）  
表结点：adjcex（数据域），info（权值），nextarc（指针域）  
如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]  
例：

//使用静态链表存储图
    //头结点
    class HeadNode{
     	//结点入度
     	public int imNum;
     	//结点数据
     	public String data;
     	//结点输出
     	public MidNode nextIndex;
    }
    //表结点
    class MidNode{
     	//数据
     	public String data;
     	//权值
     	public int info;
     	//下一位
     	public MidNode nextIndex;
    }
    
    /**
      * 使用静态链表构建一个有向图
      * @param file 文件输入
      * @return 生成的静态链表
      */
     public static HeadNode[] createDirectMap(String file) {
      	HeadNode[] mapHead = null;
      	BufferedReader bReader = null;
      	try {
       		bReader = new BufferedReader(new FileReader(file));
       		String data = bReader.readLine();
       		String[] value = data.split("&");
       		int number = Integer.parseInt(value[0]);
       		mapHead = new HeadNode[number];
       		//初始化静态链表头
       		for(int i=0; i<number; i++) {
        			mapHead[i] = new HeadNode();
        			mapHead[i].imNum = 0;
        			mapHead[i].data = value[1].substring(i, i+1);
        			mapHead[i].nextIndex = null;
       		}
       		//构建静态链表
       		while((data = bReader.readLine()) != null) {
        			value = data.split("&");
        			String fromData = value[0];
        			String toData = value[1];
        			int info = Integer.parseInt(value[2]);
        			for(int i=0; i<number; i++) {
         				//当该结点是出点时，新建结点
         				if(mapHead[i].data.equals(fromData)) {
          					MidNode mNode = new MidNode();
          					mNode.data = toData;
          					mNode.info = info;
          					//链接
          					mNode.nextIndex = mapHead[i].nextIndex;
          					mapHead[i].nextIndex = mNode;
        				 }else if(mapHead[i].data.equals(toData)) {
         					 //当该结点是入点时，入度加一
          					mapHead[i].imNum ++;
         				}
        			}
       		}
      	} catch (Exception e) {
       		e.printStackTrace();
      	} finally {
        		try {
        			if(bReader != null) {
         				bReader.close();
           			}
        		} catch (IOException e) {
         			e.printStackTrace();
        		}
       	}
      return mapHead;
     }

文件存储样式：  
![在这里插入图片描述][20200402165401532.png]  
第一行为顶点个数&顶点名称；后面的即A—>B，权值为1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: /images/20230528/b6342754277841f69a2c24977a0b9f97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: /images/20230528/6c9889e77b1647d8b2ded9a7d5d89b41.png
[20200402165155261.png]: /images/20230528/397615811efa477cb606524ce9757e2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]: /images/20230528/7ef793cd84594ae181a94a04e25c409c.png
[20200402165401532.png]: /images/20230528/eca14e79f3434c159c8edd3a58e3e83f.png