表示多對(duì)多的關(guān)系時(shí)，這里我們就用到了圖
圖的常用概念
- 頂點(diǎn)
- 邊
- 路徑
- 無(wú)向圖
- 有向圖
- 帶權(quán)圖（邊帶權(quán)值的圖也叫做網(wǎng)）
圖的表示方式有兩種：二維數(shù)組表示（鄰接矩陣）；鏈表表示（鄰接表）
鄰接矩陣
鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣，對(duì)于n個(gè)頂點(diǎn)的圖而言，矩陣的是用row和col來(lái)表示1……n文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-619904.html
鄰接表
1.鄰接矩陣需要為每個(gè)頂點(diǎn)分配n個(gè)邊的空間，其實(shí)有很多邊都是不存在的，會(huì)造成一定的空間損失
2.鄰接表的實(shí)現(xiàn)只關(guān)心存在的邊，不關(guān)心不存在的邊，因此沒(méi)有空間浪費(fèi)，鄰接表由數(shù)據(jù)+鏈表組成
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-619904.html
public class Graph {
private ArrayList<String> vertexList;//存儲(chǔ)頂點(diǎn)集合
private int[][] edges;//存儲(chǔ)圖對(duì)應(yīng)的鄰接矩陣
private int numOfEdges;//表示邊的數(shù)目
public static void main(String[] args) {
//測(cè)試
int n=5;//節(jié)點(diǎn)個(gè)數(shù)
String VertexValue[]= {"A","B","C","D","E"};
//創(chuàng)建圖對(duì)象
Graph graph=new Graph(n);
//循環(huán)添加頂點(diǎn)
for(String value:VertexValue) {
graph.insertVertex(value);
}
//添加邊
//A-B,A-C,B-C,B-D,B-E
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
//顯示
graph.showGraph();
}
//構(gòu)造器
public Graph(int n) {
//初始化矩陣和vertexList
edges=new int[n][n];
vertexList=new ArrayList<String>(n);
numOfEdges=0;
}
//圖中常用方法
//返回節(jié)點(diǎn)個(gè)數(shù)
public int getNumOfVertex() {
return vertexList.size();
}
//得到邊的數(shù)目
public int getNumOfEdges() {
return numOfEdges;
}
//返回節(jié)點(diǎn)i對(duì)應(yīng)的數(shù)據(jù)
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//返回v1和v2對(duì)應(yīng)的權(quán)值
public int getWeight(int v1,int v2) {
return edges[v1][v2];
}
//插入節(jié)點(diǎn)
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
//添加邊
public void insertEdge(int v1,int v2,int weight) {
edges[v1][v2]=weight;
edges[v2][v1]=weight;
numOfEdges++;
}
//顯示圖對(duì)應(yīng)的矩陣
public void showGraph() {
for(int[]link:edges) {
System.err.println(Arrays.toString(link));
}
}
}
到了這里，關(guān)于java 數(shù)據(jù)結(jié)構(gòu)- 圖的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![讀書(shū)筆記-《數(shù)據(jù)結(jié)構(gòu)與算法》-摘要4[插入排序]](https://imgs.yssmx.com/Uploads/2024/02/759772-1.gif)
![讀書(shū)筆記-《數(shù)據(jù)結(jié)構(gòu)與算法》-摘要8[桶排序]](https://imgs.yssmx.com/Uploads/2024/01/801768-1.png)
