无向图以及图的java代码实现

小鱼儿 2024-03-30 11:32 55阅读 0赞

## 1. 图的定义 ##

> 定义：图是由一组顶点和一组能够将两个顶点相连的边组成的

### 1.1特殊的图 ###

1.  自环：即一条连接一个顶点和其自身的边；
2.  平行边：连接同一对顶点的两条边；  
    ![在这里插入图片描述][5eb88c769a864f45bf257339a1c8bf4c.png]

### 1.2图的分类 ###

按照连接两个顶点的边的不同，可以把图分为以下两种：  
`无向图`：边仅仅连接两个顶点，没有其他含义；  
`有向图`：边不仅连接两个顶点，并且具有方向

## 2.无向图 ##

`相邻顶点`：  
当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。  
`度`：  
某个顶点的度就是依附于该顶点的边的个数  
`子图`：  
是一幅图的所有边的子集(包含这些边依附的顶点)组成的图；  
`路径`：  
是由边顺序连接的一系列的顶点组成  
`环`：  
是一条至少含有一条边且终点和起点相同的路径  
`连通图`：  
如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图  
`连通子图`：  
一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图  
![在这里插入图片描述][43cc9d98b67d46aa85382607f30c416c.png]

## 3.图的存储数据结构 ##

要表示一幅图，只需要表示清楚以下两部分内容即可：  
**1. 图中所有的顶点；  
2. 所有连接顶点的边；**  
常见的图的存储结构有两种：`邻接矩阵`和`邻接表`

### 3.1邻接矩阵 ###

1.  使用一个V\*V的二维数组int\[V\]\[V\] adj,把索引的值看做是顶点；
2.  如果顶点v和顶点w相连，我们只需要将adj\[v\]\[w\]和adj\[w\]\[v\]的值设置为1,否则设置为0即可。

![在这里插入图片描述][1d8e9629f8e348f282a99c1e35423b98.png]

### 3.2邻接表 ###

1.使用一个大小为V的数组 Queue\[V\] adj，把`索引`看做是`顶点`；  
2.每个索引处adj\[v\]存储了一个`队列`，该队列中存储的是所有与该顶点相邻的其他顶点

![在这里插入图片描述][0f335309ee584d62b2d80828bb2bfa71.png]  
**邻接表的空间并不是是线性级别的，所以后面我们一直采用邻接表这种存储形式来表示图。**

## 4.图的实现 ##

### 4.1 图的API设计 ###

![在这里插入图片描述][e132de895aa24baeb21c1d4a30daf56f.png]

### 4.2 图的代码实现 ###

public class Graph {
        
    	//顶点数目
    	private final int V;
    	//边的数目
    	private int E;
    	//邻接表
    	private Queue<Integer>[] adj;
    	public Graph(int V){
        
    		//初始化顶点数量
    		this.V = V;
    		//初始化边的数量
    		this.E=0;
    		//初始化邻接表
    		this.adj = new Queue[V];
    		//初始化邻接表中的空队列
    		for (int i = 0; i < adj.length; i++) {
        
    			adj[i] = new Queue<Integer>();
    		}
    	}
    	//获取顶点数目
    	public int V(){
        
    		return V;
    	}
    	//获取边的数目
    	public int E(){
        
    		return E;
    	}
    	//向图中添加一条边 v-w
    	public void addEdge(int v, int w) {
        
    		//把w添加到v的链表中，这样顶点v就多了一个相邻点w
    		adj[v].enqueue(w);
    		//把v添加到w的链表中，这样顶点w就多了一个相邻点v
    		adj[w].enqueue(v);
    		//边的数目自增1
    		E++;
    	}
    	//获取和顶点v相邻的所有顶点
    	public Queue<Integer> adj(int v){
        
    		return adj[v];
    	}
    }

[5eb88c769a864f45bf257339a1c8bf4c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/43d3121757d14d57bbf86791c620cc8d.png
[43cc9d98b67d46aa85382607f30c416c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fde0ceaa267447be8dc7e5eb076c3f0f.png
[1d8e9629f8e348f282a99c1e35423b98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/70c29dda68d441b7afc59af1ec827ea4.png
[0f335309ee584d62b2d80828bb2bfa71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f7185e568ba84a9c87c167cd643f2348.png
[e132de895aa24baeb21c1d4a30daf56f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a49eca3f869746979641aa92c1037ca2.png