为什么要有图: 线性表局限于一个前驱一个直接的后继关系 树也只能有一个前驱也就是父节点 当我们需要多对多的关系时,我们就用到了图
图是一种数据结构,节点可以具有零个或者多个相邻的元素,两个结点之间的连接称之为边,结点也可以成为顶点。
举例 :北京市地铁图。。。
概念
1,顶点 2,边 3,路径 4,无向图
无向图:顶点之间的连接没有方向,比如 A - B , 也可以是 B - A 路径 :比如从D -> C 的路径有 1):D -> B -> C 2):D -> A -> B -> C
5,有向图
有向图:顶点之间的连接方向, 比如 A -> B , 只能是A -> B , 不能是B -> A .
6,带权图
这种边带也全值的图也叫网
图的表示方式
1,二维数组 2,链表表示(邻接表)
邻接矩阵是表示图形中的顶点之间的矩阵,对于N个顶点的图而言,矩阵的row和col 表示的是 1…n 个点
邻接表,邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失,邻接表的实现,只关心存在的边,不关心不存在的边,因此,没有空间浪费,邻接表由数组+链表组成
图的快速入门案例
1)要求代码实现如下图结构
2)思路分析:
- 顶点存储用String ,使用ArrayList 保存顶点
- 保存矩阵用 int[][] edges
- 代码实现
代码
package com.huan.graph;
import java.util.ArrayList;
import java.util.Arrays;
public class Graph {
private ArrayList<String> vertexList;
private int[][] edges;
private int numOfEdges;
public static void main(String[] args) {
int n = 5;
String Vertexs[] = {"A","B","C","D","E"};
Graph graph = new Graph( 5 );
for (String vertex : Vertexs){
graph.insertVertex( vertex );
}
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.insertEdge( 1,0,1 );
graph.showGraph();
}
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
}
public int getNumOfVertex(){
return vertexList.size();
}
public int getNumOfEdges(){
return numOfEdges;
}
public String getValueByIndex(int i){
return vertexList.get( i );
}
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
public void showGraph(){
for (int[] link : edges){
System.err.println( Arrays.toString( link ) );
}
}
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++;
}
}
|