数据结构-图
文章目录
图论Graph Theory
图有两个重要组成部分
1、结点 Vertex
2、边 Edge
可以表示： 交通运输、社交网络、互联网、工作安排、脑区活动、程序状态执行
图的分类
有向图
无向图
无向图是一种特殊的有向图
无权图（Unweighted Graph）
有权图（Weighted Graph）
图的连通性
可以是一个，也可以是三个
简单图（Simple Graph）
图的表示
链接矩阵，用矩阵的方式表示图
无向图的表示
沿绿线对称
有向图的表示
邻接表，类似哈希表
无向图的表示
有向图的表示
邻接表适合表示稀疏图（Sparse Graph）：边较于节点较少
邻接矩阵适合表示稠密图（Dense Graph）：边较于节点较多
此处是一个完全图（所有节点之间都有边）
Graph接口的定义
package graph;
public interface Graph {
//获得结点的个数
public int V();
//获得边的个数
public int E();
//向图中添加一条边v-w
public void addEdge(int v,int w);
//判断图中两个结点之间是否有边
public boolean hasEdge(int v,int w);
//打印图的内容
public void show();
//返回图中一个结点的所有邻边
public Iterable<Integer> adj(int v);
}
稠密图-邻接矩阵 DenseGraph
package graph;
import java.util.Vector;
public class DenseGraph implements Graph{
private int n;//结点数
private int m;//边数
private boolean directed;//是否双向
private boolean[][] status;//邻接矩阵
public DenseGraph(int n,boolean directed){
//表示双向
directed=true;
status=new boolean[n][n];
this.n=n;
m=0;
}
@Override
public int V() {
// TODO Auto-generated method stub
return n;
}
@Override
public int E() {
// TODO Auto-generated method stub
return m;
}
//添加边
@Override
public void addEdge(int v, int w) {
if(v<0||v>=n){
throw new IllegalArgumentException(v+"结点不存在");
}
if(w<0||w>=n){
throw new IllegalArgumentException(w+"结点不存在");
}
//如果该边已经存在
if(hasEdge(v, w)){
return;
}
status[v][w]=true;
//如果是双向
if(directed){
status[w][v]=true;
}
m++;
}
@Override
public boolean hasEdge(int v, int w) {
if(v<0||v>=n){
throw new IllegalArgumentException(v+"结点不存在");
}
if(w<0||w>=n){
throw new IllegalArgumentException(w+"结点不存在");
}
return status[v][w];
}
//将邻接矩阵打印出来
@Override
public void show() {
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print((status[i][j]?1:0)+" ");
}
System.out.println();
}
}
//返回一个结点的所有边
@Override
public Iterable<Integer> adj(int v) {
if(v<0||v>=n){
throw new IllegalArgumentException("越界");
}
Vector<Integer> vector=new Vector<>();
for(int i=0;i<n;i++){
if(status[v][i]){
vector.add(i);
}
}
return vector;
}
}
稀疏图-领接表 SparseGraph
package graph;
import java.util.Vector;
public class SparseGraph implements Graph{
private int n;//结点数
private int m;//边数
private Vector<Integer>[] table;//邻接表
private boolean directed;//是否双向
public SparseGraph(int n,boolean directed) {
this.n=n;
m=0;
table=(Vector<Integer>[]) new Vector[n];
for(int i=0;i<n;i++){
table[i]=new Vector<>();
}
this.directed=directed;
}
@Override
public int V() {
return n;
}
@Override
public int E() {
return m;
}
//添加边
@Override
public void addEdge(int v, int w) {
if(v<0||v>=n){
throw new IllegalArgumentException(v+"结点不存在");
}
if(w<0||w>=n){
throw new IllegalArgumentException(w+"结点不存在");
}
if(table[v].contains(w)){
return;
}
table[v].add(w);
if(directed){
table[w].add(v);
}
m++;
}
@Override
public boolean hasEdge(int v, int w) {
if(v<0||v>=n){
throw new IllegalArgumentException(v+"结点不存在");
}
if(w<0||w>=n){
throw new IllegalArgumentException(w+"结点不存在");
}
return table[v].contains(w);
}
//打印邻接表
@Override
public void show() {
for(int i=0;i<table.length;i++){
System.out.print(i+": ");
for (Integer integer : table[i]) {
System.out.print(integer+" ");
}
System.out.println();
}
}
@Override
public Iterable<Integer> adj(int v) {
if(v<0||v>=n){
throw new IllegalArgumentException(v+"结点不存在");
}
return table[v];
}
}
图的遍历
深度优先遍历
邻接表的深度优先遍历 O(V+E)
邻接矩阵的深度优先遍历 O(V^2)
邻接表遍历：0 1 2 5 3 4 6
连通分量的问题，其实计算连通分量的过程也在深度优先遍历
求无权图的联通分量
package graph;
public class Components {
private Graph g;
private int ccount;
private boolean[] visited;
private int[] id;
public Components() {
}
//深度优先遍历
private void dfs(int n){
visited[n]=true;
id[n]=ccount;
for (Integer i : g.adj(n)) {
if(!visited[i]){
dfs(i);
}
}
}
public Components(Graph g) {
this.g = g;
ccount=0;
visited=new boolean[g.V()];
id=new int[g.V()];
for(int i=0;i<g.V();i++){
visited[i]=false;
id[i]=-1;
}
//求图的连通分量
for(int i=0;i<g.V();i++){
if(!visited[i]){
dfs(i);
ccount++;
}
}
}
//返回连通分量
public int getCount(){
return ccount;
}
//查询v和m之间是否连通
public boolean isConnected(int v,int m){
if(v<0||v>=g.V()){
throw new IllegalArgumentException("越界");
}
if(m<0||m>=g.V()){
throw new IllegalArgumentException("越界");
}
return id[v]==id[m];
}
}
深度优先遍历求路径
package graph;
import java.util.Stack;
import java.util.Vector;
public class Path {
private Graph g;
private int s;//起点
private int[] from;//前一结点
private boolean[] visited;//是否已查看
public Path(Graph g,int s) {
from=new int[g.V()];
visited=new boolean[g.V()];
this.g=g;
if(s<0||s>g.V()){
throw new IllegalArgumentException(s+"不存在");
}
this.s=s;
for(int i=0;i<g.V();i++){
from[i]=-1;
visited[i]=false;
}
dfs(s);
}
private void dfs(int v) {
visited[v]=true;
for (Integer i:g.adj(v)) {
if(!visited[i]){
from[i]=v;
dfs(i);
}
}
}
//验证从v到w是否有路径
public boolean hasPath(int w){
if(w<0||w>g.V()){
throw new IllegalArgumentException(s+"不存在");
}
return visited[w];
}
//返回从v-w的所经过节点的路径
public Vector<Integer> path(int w){
if(!hasPath(w)){
throw new IllegalArgumentException("此路不通");
}
Stack<Integer> stack=new Stack<>();
Vector<Integer> vect=new Vector<>();
int p=w;
while(p!=-1){
stack.push(p);
p=from[p];
}
while(!stack.isEmpty()) {
vect.add(stack.pop());
}
return vect;
}
public void showPath(int w){
for(Integer i:path(w)){
System.out.print(i+"->");
}
}
}
广度优先遍历求路径（最短）
package graph;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;
import javax.management.Query;
/**
* 广度优先遍历求最短路径
* @author zhang
*
*/
public class ShortestPath {
private Graph g;//图
private boolean[] visited;//是否已经过
private int[] from;//上一结点
private int[] level;//层数
private int s;//开始
public ShortestPath(Graph g,int s) {
this.g=g;
if(s<0||s>g.V()){
throw new IllegalArgumentException(s+"不存在");
}
visited=new boolean[g.V()];
from=new int[g.V()];
level=new int[g.V()];
for(int i=0;i<g.V();i++){
from[i]=-1;
level[i]=-1;
visited[i]=false;
}
level[s]=0;
Queue<Integer> queue=new LinkedList();
queue.add(s);
visited[s]=true;
while(!queue.isEmpty()) {
int v=queue.remove();
for(Integer i:g.adj(v)){
if(!visited[i]){
from[i]=v;
level[i]=level[v]+1;
visited[i]=true;
queue.add(i);
}
}
}
}
public boolean hasPath(int w){
if(w<0||w>g.V()){
throw new IllegalArgumentException(w+"不存在");
}
return visited[w]&&level[w]!=-1;
}
public Vector<Integer> path(int w){
if(w<0||w>g.V()){
throw new IllegalArgumentException(w+"不存在");
}
Stack<Integer> stack=new Stack<>();
Vector<Integer> vector=new Vector<Integer>();
int q=w;
while(q!=-1){
stack.add(q);
q=from[q];
}
while(!stack.isEmpty()){
vector.add(stack.pop());
}
return vector;
}
public String showPath(int w){
StringBuilder sb=new StringBuilder();
Vector<Integer> vector=path(w);
for(Integer i:vector){
sb.append(i+"->");
}
return sb.toString();
}
}