博客

图

1、图的原理


1）图：顶点和边组成

2）实现

（1）邻接矩阵

（2）邻接表


2、深度优先搜索


1）定义：首先访问初始节点的第一个邻接节点，再访问该邻接节点的第一个邻接节点，……

2）实现步骤

（1）访问初始节点 v，并把其标记为已访问；

（2）查找 v 的第一个邻接节点 w；

（3）判断 w 是否存在，若 w 存在，则执行第（4）；若不存在，则从v之后的节点继续开始步骤1-3；

（4）判断 w 是否已访问，若未被访问，则以 w 为初始节点进行深度优先搜索；

（5）查找 v 的下一个邻接节点 新w。


3、广度优先搜索


1）定义：首先访问初始节点的所有邻接节点，若访问完毕，则以初始节点的第一个邻接节点为初始节点访问其所有的邻接节点，……

2）实现步骤

（1）访问初始节点 v ，并把其标记为已访问，把 v 入队列；

（2）判断队列是否为空，若非空，弹出队列的队头元素 u；若为空，则执行完毕；

（3）查找 u 的第一个邻接节点 w；

（4）判断 w 是否存在，若不存在，则执行步骤2，若存在，则执行以下：

①判断节点 w 是否已访问，若未访问，则先把其标记为已访问，再把其入队，最后查找 u 的下一个邻接节点 新w；

②若已访问，则查找 u 的下一个邻接节点 新w；

class Graph {
	public static void main(String[] args) {
	}
	// 图的顶点
	ArrayList<String> vertexList;
	// 邻接矩阵存放图的边
	int[][] edges;
	// 图中节点是否访问
	boolean[] isVisited;
	// 图中边的个数
	int numOfEdges;
	// 构造器
	public Graph(int n) {
		vertexList = new ArrayList<String>();
		edges = new int[n][n];
		isVisited = new boolean[n];
	}
	
	// 返回节点的第一个邻接节点
	public int getFirstNeighbor(int v) {
		for(int i = 0; i < vertexList.size(); i++) {
			if(edges[v][i] != 0) {
				return i;
			}
		}
		return -1;
	}
	// 返回节点的下一个邻接节点
	public int getNextNeighbor(int v, int w) {
		for(int i = w + 1; i < vertexList.size(); i++) {
			if(edges[v][i] != 0) {
				return i;
			}
		}
		return -1;
	}
	// 深度优先搜索
	public void dfs(boolean[] isVisited, int v) {
		System.out.print(getValueByIndex(v) + "->");
		isvisited[v] = true;
		int w = getFirstNeighbor(v);
		while(w != -1) {
			if(!isVisited[w]) {
				dfs(isVisited, w);
			}
			w = getNextNeighbor(v, w);
		}
	}
	// 重载dfs
	public void dfs() {
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				dfs(isVisited, i);
			}
		}
	}
	// 广度优先搜索
	public void bfs(boolean[] isVisited, int v) {
		System.out.print(getValueByIndex(v) + "->");
		isVisited[v] = true;
		Queue<Integer> queue = new LinkedList();
		queue.add(v);
		while(!queue.isEmpty()) {
			int u = queue.remove();
			int w = getFirstNeighbor(u);
			while(w != -1) {
				if(!isVisited[w]) {
					isVisited[w] = true;
					queue.add(w);
				}
				w = getNextNeighbor(u, w);
			}
		}
	}
	// 重载bfs
	public void bfs() {
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				bfs(isVisited, i);
			}
		}
	}

	// 添加节点
	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++;
	}
	// 根据下标返回节点存放的元素
	public String getValueByIndex(int v) {
		return vertexList.get(v);
	}
	// 返回节点数目
	public int getNumOfVertex() {
		return vertexList.size();
	}
	// 返回边的数目
	public int getNumOfEdge() {
		return numOfEdges;
	}
	// 显示图的邻接矩阵
	public void show() {
		for(int[] link: edges) {
			System.out.println(Arrays.toString(link));
		}
	}
}