java图（含java图的代码）

目录

一：图的介绍（要离散数学基础）

二：图的表现形式

2.1：邻接链表

2.2：邻接矩阵

三：图的遍历算法

3.1 图的深度优先遍历算法​

3.2 图的广度优先遍历算法

3.3 全部代码

---

一：图的介绍（要离散数学基础）

我们先回顾一下之前介绍的树的概念，在树的定义中，每个节点只能有一个父类，并且树中不能出现有环形。但是你可曾想过，当一棵树没有任何规则的时候，会发生什么吗？
现在，我们给图（graph）下一个定义：
图，是一种用节点和边来表示相互关系的数学模型。（A graph is a mathematical structure for representing relationships using nodes and edges）
其实，用句不是很严谨的话来说，图可以看成是没有任何限制的树（比如，可以有环状，可以有多种关系等等）。
下图是图但它们不是一棵树：

图没有固定的root结点

图必须等待前面的任务完成之后，才可以执行下一个任务

二：图的表现形式

2.1：邻接链表

查找比较浪费时间

2.2：邻接矩阵

比较浪费空间

三：图的遍历算法

3.1 图的深度优先遍历算法

//孤立结点
	public void dfs() {
		for(int i = 0; i < al.size(); i++) {
			if(!is[i]) {
				dfs(is, i);
			}
		}
	}
	
	public void dfs(boolean[] b, int i) {
		System.out.print(al.get(i));
		is[i] = true;
		
		int w = firstNode(i);
		while(w != -1) {
			if(!is[i]) {
				dfs(b,w);
			}
			w = nextNode(i,w);
		}
	}

3.2 图的广度优先遍历算法

//广度
	public void bfs(boolean[] b,int i) {
		
		System.out.print(al.get(i));
		b[i] = true;
		//队列取头结点
		int u;
		//第一个领结点
		int w;
		LinkedList queue = new LinkedList();
		queue.addLast(i);
		
		while(!queue.isEmpty()) {
			u = (int) queue.removeFirst();
			w = firstNode(u);
			
			while(w != -1) {
				if(!is[w]) {
					System.out.print(al.get(w));
					is[w] = true;
					queue.addLast(w);
				}
				w = nextNode(u,w);
			}
		}
	}
	public void bfs() {
		for(int i = 0; i < al.size(); i++) {
			if(!is[i]) {
				bfs(is,i);
			}
		}
	}

3.3 全部代码

package graph;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
 
 
public class G {
	//集合
	private ArrayList al;
	//二维矩阵
	private int[][] array;
	//标记
	private boolean[] is;
	//边的个数
	private int num;
	
	public G(int num) {
		this.al = new ArrayList(num);
		this.array = new int[num][num];
		this.num = 0;
		this.is = new boolean[num];
	}
	//初始化结点
	public void creatAl(String[] string) {
		for(String s:string) {
			this.al.add(s);
		}
	}
	//初始化矩阵
	public void creatArr(int x, int y) {
		this.array[x][y] = 1;
		this.array[y][x] = 1;
		num++;
	}
	//打印矩阵
	public void printArr() {
		for(int[] i:array) {
			System.out.println(Arrays.toString(i));
		}
	}
	
	//访问第一个结点
	public int firstNode(int index) {
		for(int i = index; i < al.size(); i++) {
			if(array[index][i] > 0) {
				return i;
			}
		}
		return -1;
	}
	
	//访问下一个结点
	public int nextNode(int x, int y) {
		for(int i = y + 1; i < al.size(); i++) {
			if(array[x][i] > 0) {
				return i;
			}
		}
		return -1;
	}
	//孤立结点
	public void dfs() {
		for(int i = 0; i < al.size(); i++) {
			if(!is[i]) {
				dfs(is, i);
			}
		}
	}
	
	public void dfs(boolean[] b, int i) {
		System.out.print(al.get(i));
		is[i] = true;
		
		int w = firstNode(i);
		while(w != -1) {
			if(!is[i]) {
				dfs(b,w);
			}
			w = nextNode(i,w);
		}
	}
	
	
	
	
	//广度
	public void bfs(boolean[] b,int i) {
		
		System.out.print(al.get(i));
		b[i] = true;
		//队列取头结点
		int u;
		//第一个领结点
		int w;
		LinkedList queue = new LinkedList();
		queue.addLast(i);
		
		while(!queue.isEmpty()) {
			u = (int) queue.removeFirst();
			w = firstNode(u);
			
			while(w != -1) {
				if(!is[w]) {
					System.out.print(al.get(w));
					is[w] = true;
					queue.addLast(w);
				}
				w = nextNode(u,w);
			}
		}
	}
	public void bfs() {
		for(int i = 0; i < al.size(); i++) {
			if(!is[i]) {
				bfs(is,i);
			}
		}
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
}

package graph;
 
public class T {
	public static void main(String[] args) {
		String[] string = {"A","B","C","D","E"};
		G g = new G(5);
		g.creatAl(string);
		g.creatArr(0, 1);
		g.creatArr(0, 2);
		g.creatArr(1, 3);
		g.creatArr(2, 3);
		g.creatArr(3, 4);
		
		g.printArr();
//		g.index();
		g.bfs();
	}
	
}