图的表示与基础

基础"/>

图的表示与基础

1.图的基础知识

该图片来自于：  

2.稀疏图与稠密图

G(V,E)：V顶点个数，E边的个数

稀疏图：E<<V²        一般用邻接表表示(数组+链表)

稠密图：E接近V²        一般用邻接矩阵表示（二维数组）

3.图的两种表示

邻接表法：

class Graph {int[][] matrix;int size;public Graph(int size) {this.size = size;matrix = new int[size][size];}public void addEdge(int from, int to) {matrix[from][to] = 1;matrix[to][from] = 1; // 如果是无向图，需要加上这一行}public void printGraph() {for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {System.out.print(matrix[i][j]+"  ");}System.out.println();}}public static void main(String[] args) {Graph graph = new Graph(5);graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(0, 3);graph.addEdge(0, 4);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(1, 4);graph.addEdge(2, 3);graph.addEdge(2, 4);graph.addEdge(3, 4);graph.printGraph();}

邻接矩阵法：

public class Graph2 {int V;	//图的顶点个数LinkedList<Integer> adjListArray[];//数组链表：数组位置存储的是链表，链表里的元素是IntegerGraph2(int V) {this.V = V;adjListArray = new LinkedList[V];for (int i = 0; i < V; i++) {adjListArray[i] = new LinkedList<>();}}void addEdge(int src, int dest) {//添加边adjListArray[src].add(dest);adjListArray[dest].add(src); // 如果是无向图，需要加上这一行}void printGraph() {for (int v = 0; v < V; v++) {System.out.println("Adjacency list of vertex " + v);System.out.print("head");for (Integer pCrawl : adjListArray[v]) {System.out.print(" -> " + pCrawl);}System.out.println("\n");}}public static void main(String[] args) {Graph2 graph2 = new Graph2(5);System.out.println("顶点个数为："+graph2.V);graph2.addEdge(0, 1);graph2.addEdge(0, 2);graph2.addEdge(0, 3);graph2.addEdge(0, 4);graph2.addEdge(1, 2);graph2.addEdge(1, 3);graph2.addEdge(1, 4);graph2.addEdge(2, 3);graph2.addEdge(2, 4);graph2.addEdge(3, 4);graph2.printGraph();}
}