数据结构之图【深搜，广搜】

心已赠人 2022-08-11 15:29 183阅读 0赞

package com.zhiru;
    
    import java.util.Queue;
    import java.util.LinkedList;
    
    public class MyGraph {
    
    	private int maxVertices;// 最大顶点数
    	private int numVertices;// 当前顶点数
    	private int numEdges;// 当期边数
    	private int[] verticesList;// 顶点表
    	private int[][] edge;// 边邻接矩阵
    
    	public MyGraph(int size) {
    		maxVertices = size;
    		numVertices = 0;
    		numEdges = 0;
    		int i, j;
    		verticesList = new int[maxVertices];
    		edge = new int[maxVertices][];
    		for (i = 0; i < maxVertices; i++) {
    			edge[i] = new int[maxVertices];
    		}
    		for (i = 0; i < maxVertices; i++) {
    			for (j = 0; j < maxVertices; j++)
    				edge[i][j] = (i == j) ? 0 : Integer.MAX_VALUE;
    		}
    	}
    
    	public int getPos(int v) {
    		for (int i = 0; i < numVertices; i++) {
    			if (verticesList[i] == v)
    				return i;
    		}
    		return -1;// 没找到
    	}
    
    	// 插入顶点v
    	public void insertVertex(int v) {
    		if (numVertices == maxVertices)
    			return;
    		verticesList[numVertices++] = v;
    	}
    
    	// 删除顶点v
    	public void deleteVertex(int v) {
    		if (v < 0 || v >= numVertices)
    			return;
    		if (numVertices == 1)
    			return;// 只有一个顶点不删除
    		int i, j, k, m;
    		k = getPos(v);
    		m = k;
    		for (; k < numVertices - 1; k++) {
    			verticesList[k] = verticesList[k + 1];
    		}
    		for (i = 0; i < numVertices; i++)
    			if (edge[i][v] > 0 && edge[i][v] < Integer.MAX_VALUE)
    				numEdges--;
    		for (i = 0; i < numVertices; i++) {
    			for (j = m; j < numVertices - 1; j++) {
    				edge[i][j] = edge[i][j + 1];
    			}
    		}
    		int n = numVertices;
    		numVertices--;
    		for (j = 0; j < numVertices; j++) {
    			for (i = m; i < n - 1; i++) {
    				edge[i][j] = edge[i + 1][j];
    			}
    		}
    
    	}
    
    	// 插入边v1,v2,权值cost
    	public void insertEdge(int v1, int v2, int cost) {
    		if (v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices
    				&& edge[v1][v2] == Integer.MAX_VALUE) {
    			edge[v1][v2] = edge[v2][v1] = cost;
    			numEdges++;
    		} else {
    			return;
    		}
    	}
    
    	public void deleteEdge(int v1, int v2) {
    		if (v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices
    				&& edge[v1][v2] > 0 && edge[v1][v2] < Integer.MAX_VALUE) {
    
    			edge[v1][v2] = edge[v2][v1] = Integer.MAX_VALUE;
    			numEdges--;
    		} else
    			return;
    	}
    
    	// 建立图
    	/*
    	 * l是顶点一维矩阵，a是邻接矩阵，n是顶点数，m是边数
    	 */
    	public void buildGraph(int[] l, int[][] a, int n, int m) {
    		numVertices = n;
    		numEdges = m;
    		for (int k = 0; k < numVertices; k++) {
    			verticesList[k] = l[k];
    		}
    		for (int i = 0; i < numVertices; i++) {
    			for (int j = 0; j < numVertices; j++) {
    				edge[i][j] = a[i][j];
    			}
    		}
    	}
    
    	public void prtGraph() {
    		for (int i = 0; i < numVertices; i++) {
    			for (int j = 0; j < numVertices; j++) {
    				System.out.print(edge[i][j] + " ");
    			}
    			System.out.print("\n");
    		}
    	}
    
    	// 给出顶点v的第一个邻接顶点的位置，找不到返回-1
    	public int getFirstNeighbor(int v) {
    		if (v != -1) {
    			for (int col = 0; col < numVertices; col++)
    				if (edge[v][col] > 0 && edge[v][col] < Integer.MAX_VALUE)
    					return col;
    		}
    		return -1;
    
    	}
    
    	// 给出顶点v的邻接顶点w的下一个邻接顶点
    	public int getNextNeighbor(int v, int w) {
    		if (v != -1 && w != -1) {
    			for (int col = w + 1; col < numVertices; col++)
    				if (edge[v][col] > 0 && edge[v][col] < Integer.MAX_VALUE)
    					return col;
    		}
    		return -1;
    	}
    
    	public int getValue(int i) {
    		if (i >= 0 && i < numVertices)
    			return verticesList[i];
    		return -1;
    	}
    
    	// 图的深度优先搜索
    	public void traversal(int k) {
    		int loc, n = numVertices;
    		boolean[] visited = new boolean[n];
    		loc = getPos(k);
    		dfs(loc, visited);
    	}
    
    	private void dfs(int loc, boolean[] visited) {
    		prt("" + getValue(loc));
    		visited[loc] = true;
    		int w = getFirstNeighbor(loc);
    		while (w != -1) {
    			if (visited[w] == false)
    				dfs(w, visited);
    			w = getNextNeighbor(loc, w);
    		}
    	}
    
    	// 图的广度优先搜索算法,从节点k开始遍历图
    	public void bfs(int k) {
    		int i, j, loc;
    		Queue<Integer> q = new LinkedList<Integer>();
    		loc = getPos(k);
    		boolean[] visited = new boolean[numVertices];
    		prt(getValue(loc) + "");
    		visited[k] = true;
    		q.offer(k);// k进队列
    		while (!q.isEmpty()) {
    			i = q.poll();
    			for (j = 0; j < numVertices; j++) {
    				if (!visited[j]) {
    					prt(getValue(j) + "");
    					visited[j] = true;// 标记已被访问
    					q.offer(j);// 访问过的j入队
    				}
    			}
    		}
    	}
    
    	public static void prt(String s) {
    		System.out.print(s + "\n");
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		MyGraph mg = new MyGraph(10);
    		int[][] a = { { 0, 1, Integer.MAX_VALUE, 4 },
    				{ Integer.MAX_VALUE, 0, 9, 2 }, { 3, 5, 0, 8 },
    				{ Integer.MAX_VALUE, Integer.MAX_VALUE, 6, 0 } };
    		int[] vl = { 0, 1, 2, 3 };
    		mg.buildGraph(vl, a, 4, 8);
    		mg.prtGraph();
    		mg.insertVertex(4);
    		mg.insertEdge(0, 4, 100);
    		prt("插入顶点4和0-->4边后");
    		mg.prtGraph();
    		// prt("删除顶点1后:");
    		// mg.deleteVertex(1);
    		//mg.prtGraph();
    		prt("深度优先搜索：");
    		mg.traversal(3);
    		 prt("广度优先搜索：");
    		 mg.bfs(4);
    	}
    
    }

0 1 2147483647 4   
2147483647 0 9 2   
3 5 0 8   
2147483647 2147483647 6 0   
插入顶点4和0-->4边后  
0 1 2147483647 4 100   
2147483647 0 9 2 2147483647   
3 5 0 8 2147483647   
2147483647 2147483647 6 0 2147483647   
100 2147483647 2147483647 2147483647 0   
深度优先搜索：  
3  
2  
0  
1  
4  
广度优先搜索：  
4  
0  
1  
2  
3