图结构题目
图结构题目
图结构通用结构类
图：
package Graph;
import java.util.HashMap;
import java.util.HashSet;
public class Graph {
public HashMap nodeHashMap;
public HashSet edgesHashSet;
public Graph(){
nodeHashMap = new HashMap();
edgesHashSet = new HashSet();
}
}
图结点：
package Graph;
import java.util.ArrayList;
public class GraphNode {
public int value;
public int in;
public int out;
public ArrayList next;
public ArrayList edges;
public GraphNode(int value){
this.value = value;
this.in = 0;
this.out = 0;
this.next = new ArrayList();
this.edges = new ArrayList();
}
}
边：
package Graph;
public class GraphEdges {
public int weight; //权重
public GraphNode in;
public GraphNode from;
public GraphEdges(int weiht, GraphNode from, GraphNode to){
this.weight = weiht;
this.in = to;
this.from = from;
}
}
生成图：
主函数：
package Graph;
import java.util.*;
public class GraphMain {
public static void main(String[] args){
//生成图
int[][] arr = {{0,1,1},{1,0,2},{1,4,4},{4,1,3},{4,2,6},{2,4,5},{0,2,7},{2,0,8},{0,3,9},{3,0,10}}; //无向图
// int[][] arr = {{0,1,1},{2,0,1},{2,4,1},{0,3,1},{1,4,1}}; //有向图
GraphPractice graphPractice = new GraphPractice();
Graph graph = graphPractice.createGraph(arr);
}
实现类:
package Graph;
import java.util.*;
public class GraphPractice {
/**
* 生成图
* */
public Graph createGraph(int[][] arr){
Graph graph = new Graph();
for(int i=0; i题目一：宽度优先遍历和深度优先遍历
主函数类：
package Graph;
import java.util.*;
public class GraphMain {
public static void main(String[] args){
//生成图
int[][] arr = {{0,1,1},{1,0,2},{1,4,4},{4,1,3},{4,2,6},{2,4,5},{0,2,7},{2,0,8},{0,3,9},{3,0,10}}; //无向图
// int[][] arr = {{0,1,1},{2,0,1},{2,4,1},{0,3,1},{1,4,1}}; //有向图
GraphPractice graphPractice = new GraphPractice();
Graph graph = graphPractice.createGraph(arr);
/**
* 宽度优先遍历
* */
System.out.print("宽度优先遍历:");
graphPractice.bfs(graph.nodeHashMap.get(1));
System.out.println();
/**
* 深度优先遍历
* */
System.out.print("深度优先遍历:");
graphPractice.dfs(graph.nodeHashMap.get(1));
System.out.println();
}
实现类：
package Graph;
import java.util.*;
public class GraphPractice {
/**
* 宽度优先遍历
* */
public void bfs(GraphNode graphNode){
if (graphNode == null) return;
Queue queue = new LinkedList();
HashSet set = new HashSet();
((LinkedList) queue).add(graphNode);
set.add(graphNode);
while (!queue.isEmpty()){
GraphNode node = queue.poll();
System.out.print(node.value+" "); //处理区
for(GraphNode nodes: node.next){
if(!set.contains(nodes)){
((LinkedList) queue).add(nodes);
set.add(nodes);
}
}
}
}
/**
* 深度优先遍历
* */
public void dfs(GraphNode node){
if(node == null) return;
Stack stack = new Stack();
HashSet set = new HashSet();
stack.push(node);
set.add(node);
System.out.print(node.value+" ");
while (!stack.isEmpty()){
GraphNode tmp = stack.pop();
for(GraphNode nodes:tmp.next){
if(!set.contains(nodes)){
stack.push(tmp); //重新押回去，防止有结点遗漏
stack.push(nodes);
set.add(nodes);
System.out.print(nodes.value+" "); //处理区
break;
}
}
}
}
}
题目二: 拓扑排序
主函数类：
package Graph;
import java.util.*;
public class GraphMain {
public static void main(String[] args){
//生成图
int[][] arr = {{0,1,1},{1,0,2},{1,4,4},{4,1,3},{4,2,6},{2,4,5},{0,2,7},{2,0,8},{0,3,9},{3,0,10}}; //无向图
// int[][] arr = {{0,1,1},{2,0,1},{2,4,1},{0,3,1},{1,4,1}}; //有向图
GraphPractice graphPractice = new GraphPractice();
Graph graph = graphPractice.createGraph(arr);
/**
* 拓扑排序
* */
List result = graphPractice.sortedTopology(graph);
System.out.print("拓扑排序顺序:");
for(GraphNode node:result) System.out.print(node.value+" ");
}
实现类:
package Graph;
import java.util.*;
public class GraphPractice {
/**
* 拓扑排序
* 从入度为0的结点开始遍历，依次遍历入度为0的结点
* */
public List sortedTopology(Graph graph){
HashMap map = new HashMap(); //value: 结点的入度数
//入度为0的结点才能进队列
Queue queue = new LinkedList<>();
for(GraphNode node:graph.nodeHashMap.values()){
map.put(node,node.in);
if(node.in == 0) ((LinkedList) queue).add(node);
}
List result = new ArrayList();
while (!queue.isEmpty()){
GraphNode cur = queue.poll();
result.add(cur);
for(GraphNode next:cur.next){
map.put(next,map.get(next)-1);
if(map.get(next) == 0) ((LinkedList) queue).add(next);
}
}
return result;
}
}
题目三：最小生成树
package Graph;
import java.util.*;
public class GraphMain {
public static void main(String[] args){
//生成图
int[][] arr = {{0,1,1},{1,0,2},{1,4,4},{4,1,3},{4,2,6},{2,4,5},{0,2,7},{2,0,8},{0,3,9},{3,0,10}}; //无向图
// int[][] arr = {{0,1,1},{2,0,1},{2,4,1},{0,3,1},{1,4,1}}; //有向图
GraphPractice graphPractice = new GraphPractice();
Graph graph = graphPractice.createGraph(arr);
/**
* 生成最小生成树
* */
//k算法
Set kResult = graphPractice.kruskalMST(graph);
System.out.print("完成");
//p算法
Set pResult = graphPractice.primMST(graph);
System.out.print("完成");
}
自定义边的比较器：
package Graph;
import java.util.Comparator;
//自定义边的比较器
public class EdgeComparator implements Comparator {
@Override
public int compare(GraphEdges o1, GraphEdges o2) {
return o1.weight-o2.weight;
}
}
自定义类并查集
package Graph;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
//类并查集
public class MySets {
public HashMap> sets;
public MySets(List list){
sets = new HashMap>();
for (GraphNode node:list){
List newList = new LinkedList();
newList.add(node);
sets.put(node,newList);
}
}
//检查是否为同一个集合
public boolean isSameSet(GraphNode fromNode,GraphNode toNode){
List fromList = sets.get(fromNode);
List toList = sets.get(toNode);
return fromList == toList;
}
//合并为同一个集合
public void union(GraphNode fromNode,GraphNode toNode){
List fromList = sets.get(fromNode);
List toList = sets.get(toNode);
for(GraphNode node:toList) {
fromList.add(node);
sets.put(node,fromList);
}
}
}
实现类:
package Graph;
import java.util.*;
public class GraphPractice {
/**
* k算法 最小生成树
* 通过查看是否在同于一个集合里面
* 从边的角度出发：获取最小的边，确认边俩端的结点是否再同一个集合，如果不在，就合在一起，在就跳过
* 即先挑边再挑点
* */
//k算法实现最小生成树
public Set kruskalMST(Graph graph){
LinkedList nodeList =new LinkedList();
for(GraphNode node : graph.nodeHashMap.values()) nodeList.add(node);
MySets sets = new MySets(nodeList);
PriorityQueue queue = new PriorityQueue(new EdgeComparator());
for(GraphEdges edgs:graph.edgesHashSet){
queue.add(edgs);
}
Set result = new HashSet();
//通过确定是否再同一个集合确定是否能组成一个环
while (!queue.isEmpty()){
GraphEdges edges = queue.poll();
if(!sets.isSameSet(edges.from,edges.in)){
result.add(edges);
sets.union(edges.from,edges.in);
}
}
return result;
}
/**
* p算法 生成最小生成树
* 先挑点，再挑边
* 从结点的所有边中，选择权重最小的点
* */
public Set primMST(Graph graph){
PriorityQueue queue = new PriorityQueue(new EdgeComparator()); //存放可用于选择的边
HashSet set = new HashSet();
Set edgesSet = new HashSet();
for(GraphNode node : graph.nodeHashMap.values()){ //for循环防止有森林的情况出现，即有没联通的俩片点
if(!set.contains(node)){
set.add(node);
for(GraphEdges edges: node.edges) queue.add(edges);
while (!queue.isEmpty()){
GraphEdges edges = queue.poll(); //比较器处理后，弹出来的第一条线一定是权重最小的那条
GraphNode toNode = edges.in;
if(!set.contains(toNode)){
set.add(toNode);
edgesSet.add(edges);
for(GraphEdges edges1:toNode.edges) queue.add(edges1);
}
}
}
}
return edgesSet;
}
}