图
图是非线性数据结构，途中任何两个顶点都可能有关联。定点见的关系是多对多的关系。
本章主要介绍一下内容
- 图的概念
- 图的存储
- 图的遍历
- 生成树和最小生成树
- 最短路径和拓扑排序
1.图的定义
-
完全图
在一个n个顶点的无向图中，若每个顶点到其他n-1顶点都有一条边，则图中有n个顶点且有n(n-1)/2条边的图成为五项完全图。
权和带权图
2.图的存储
本章主要介绍图的存储
1.邻接矩阵
2.邻接表存储
3.关联矩阵
邻接表
3.图的遍历（重点）
本章主要介绍图的深度遍历dfs和广度遍历bfs
1.深度遍历VS广搜
dfs利用stack；bfs利用队列；思想类似于树的层次遍历。只不过树由于父子节点关系不需要判断该节点是否被访问过。图的话需要生命一个数组，来保存节点是否访问过。
package graph;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
public class GraphSearch {
int n;//节点个数
int e;//边的个数
int[][] mtx;//邻接矩阵存储
int[] visited;//是否访问过
//create
void create(){
Scanner sc= new Scanner(System.in);
n=sc.nextInt();
e=sc.nextInt();
System.out.println(n +":"+ e);
mtx= new int[n][n];
visited=new int[n];
Arrays.fill(visited, 0);
for(int j=0;j<e;j++){
int x=sc.nextInt();
int y=sc.nextInt();
int v=sc.nextInt();
mtx[x][y]=v;
}
}
//dfs
void dfs(int x){
Stack<Integer> stack= new Stack<Integer>();
stack.add(x);
Arrays.fill(visited, 0);
visited[x]=1;
while(!stack.isEmpty()){
int point=stack.pop();
System.out.println(point);
for(int i=0;i<mtx[point].length;i++){
if(visited[i]!=1 && mtx[point][i]!=0){
stack.push(i);
visited[i]=1;
}
}
}
}
//bfs
void bfs(int x){
LinkedList<Integer> queue=new LinkedList<>();
queue.add(x);
Arrays.fill(visited, 0);
visited[x]=1;
while(!queue.isEmpty()){
int point=queue.removeFirst();
System.out.println(point);
for(int i=0;i<mtx[point].length;i++){
if(visited[i]!=1 && mtx[point][i]!=0){
queue.addLast(i);
visited[i]=1;
}
}
}
}
public static void main(String[] args) {
GraphSearch gs= new GraphSearch();
gs.create();
gs.dfs(0);
System.out.println();
gs.bfs(0);
}
}
4.生成树和最小生成树
本节主要讲最小生成树，以及prim算法和kruskal算法。
图论中，通常将树作为一个无回路连通图，对于无回路连通图，只要选定某个顶点作为根，以此顶点为树根对每条边定向，就能得到通常的树。
生成树：
一个连通图的一个字图如果是一个包含G的多有顶点的树，则盖子图称为G的生成树。
最小生成树：
实现最小生成树的两种主要算法
prim
创建并扩展一棵树，为它添加新的树枝。
kruskal
扩展一个树的集构成一颗生成树。
5.最短路径
最小生成树势无向图的一个典型应用。本章将重点介绍最短路径和拓扑排序。
最短路径
单源路径最短问题是指，对于给定的有向网络g=（v,e）及单个源点v，求从v到g的其余各个顶点的最短路径。
dijkstra算法：
基本思想：设置两个顶点集合S和T，s中存放已确定最短路径的顶点。t中存放待确定最短路径的顶点。初始时，s中只有一个顶点。t中包换除了源点以外的其他顶点。此时各个顶点的当前路径为原点到该顶点上弧度的值。接着选择t中当前路径最小的的一个顶点v加入到s中。然后修改t中剩余的顶点的当前的最短路径。
思路（重要）：
package graph;
import java.util.Arrays;
import java.util.Scanner;
public class Dijkstra {
int n;//顶点个数
int e;//边的个数
int[][] mtx; //邻接矩阵
int[] visited;//是否访问过
int[] dist; //最短距离
int[] prev;//顶点i的前驱节点prev[i]
final int MAX=-1;//不可达
/**
* 6 8
0 5 100
0 2 10
0 4 30
1 2 5
2 3 50
3 5 10
4 5 60
4 3 20
*/
//create
void create(){
Scanner sc= new Scanner(System.in);
n=sc.nextInt();
e=sc.nextInt();
mtx= new int[n][n];
visited=new int[n];
prev=new int[n];
for(int i=0;i<n;i++){
Arrays.fill(mtx[i], -1);
}
for(int j=0;j<e;j++){
int x=sc.nextInt();
int y=sc.nextInt();
int v=sc.nextInt();
mtx[x][y]=v;
}
}
void dj(int x){
//1.初始化
Arrays.fill(visited, 0);
Arrays.fill(prev, -1);
for(int i=0;i<mtx[x].length;i++){
prev[i]=mtx[x][i]>0?0:-1;
}
dist=Arrays.copyOf(mtx[x], n);
//起点x
visited[x]=1;
dist[x]=0;
//2.while
int k=0;
for(int i=0;i<n;i++){
//寻找临接顶点x最小的距离的点k
int min=Integer.MAX_VALUE;
for(int j=0;j<n;j++){
if(dist[j]!=MAX &&dist[j]<min &&visited[j]!=1){
min=dist[j];
k=j;
}
}
//将k标记为已经访问
visited[k]=1;
//根据k修正当前的最短路径
for(int j=0;j<n;j++){
if(mtx[k][j]!=-1 &&visited[j]!=1){
int tmp=dist[k]+mtx[k][j];
//这里面要注意，最远距离设置的是-1.-1小于任何正值，所以，如果之前的是不可达，就设置为最新的距离。如果可达，就进行比较。
if(dist[j]==-1){
dist[j]=tmp;
}else{
dist[j]=dist[j]<tmp?dist[j]:tmp;
}
prev[j]=k;
}
}
}
for (int i=0; i <n; i++)
System.out.println( x+","+ i+":"+ dist[i]);
System.out.println();
for(int i=0;i<prev.length;i++){
System.out.print(prev[i]+" ");
}
System.out.println();
//打印x到各个顶点的最短路径
for(int i=0;i<n;i++){
System.out.print(i);
int t=prev[i];
while(t!=-1 ){
System.out.print(" "+t);
t=prev[t];
}
System.out.println();
}
}
public static void main(String[] args) {
Dijkstra dj= new Dijkstra();
dj.create();
dj.dj(0);
}
}
6.拓扑排序
思路：
思路：
int[][] mtx
int[] visited
for(i->n){
//sum
for(j->n){
找出入度为0的点。即 sum(mtx[][j])
}
//判断sum
if(sum=0)
标记为visited[j]=1;
将mtx[j][] 设置为0；
}
