图-最小生成树
麦兜 / 2020-04-28 / 算法 / 阅读量 291

Prim 算法

示例

Map

算法思想

Prim算法

代码

import java.util.Scanner;
public class main {

    static int Vnum=9;
    static  int Map[][]=new  int[Vnum][Vnum];
    static int MAX=Integer.MAX_VALUE;
  public static void main(String[] args) {

      Scanner scanner=new Scanner(System.in);
     //初始化
      for(int i=0;i<Vnum;i++)
      {
          for(int j=0;j<Vnum;j++)
          {
              if(i==j)
              {
                  Map[i][j]=0; //(i,j)=0
              }
              else {
                  Map[i][j]=MAX;
              }
          }
      }

      //权值数据输入
      for(int i=0;i<27;i++)
      {
          int x,y,value;
          x=scanner.nextInt();
          y=scanner.nextInt();
          value=scanner.nextInt();
          Map[x][y]=value;
      }
      MiniSpanTree();  //最小生成树开始
  }
  static void MiniSpanTree()
  {
        int adj[]=new int[9];   //顶点相关的索引
        int lowcost[]=new int[9]; // 顶点相关边的权值
        //把v0 放入从v0开始
        adj[0]=0;
        lowcost[0]=0;
        //v0相关的边存入
        for(int i=1;i<Vnum;i++)
        {
            lowcost[i]=Map[0][i];
            adj[i]=0;
        }

        for(int i=1;i<Vnum;i++)  //n个顶点只需要找n-1条边即可
        {
            int min=MAX;
            int k=0;
            for(int j=1;j<Vnum;j++)  //v0 已经放入了最小生成树内了 而且lowcost[0]=0   lowcost[index]=0 说明已经比较过了
            {
                //找最小相关权边值,并用k记录下标
                if(lowcost[j]!=0&&lowcost[j]<min)
                {
                    min=lowcost[j];
                    k=j;
                }
            }
            //输出并标记属于最小生成树的顶点
            System.out.println(adj[k]+"->"+k+" ");
            lowcost[k]=0;
            //把k所相关的边放入lowcost 条件是比lowcost小 并把相关顶点加入。
            for(int j=1;j<Vnum;j++)
            {
                if(lowcost[j]!=0&&Map[k][j]<lowcost[j])
                {
                    lowcost[j]=Map[k][j];
                    adj[j]=k;
                }
            }
        }
  }
}

输入:    
0 1 10
0 5 11
1 0 10
1 2 18
1 6 16
1 8 12
2 3 22
2 8 8
3 2 22
3 4 20
3 7 16
3 8 21
4 3 20
4 5 26
4 7 7
5 0 11
5 4 26
5 6 17
6 1 16
6 5 17
6 7 19
7 3 16
7 4 7
7 6 19
8 1 12
8 2 8
8 3 21
输出:
   0->1 
   0->5 
   1->8 
   8->2 
   1->6 
   6->7 
   7->4 
   7->3
    

Kruskal算法

示例

邻接矩阵转换begin为从小到大 ,过滤冲突的边。比如v3 到v8 edges[11] 已经有了 就不没有必要存储 v8到v3

算法思想:根据权值排序好了从小拿到大,然后设计parent去记录有没有成环。

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class main {

  static int MAXEDGE = 15;
  static EdgeNode[] e = new EdgeNode[MAXEDGE];

  public static void main(String[] args) 
  {
    Scanner scanner = new Scanner(System.in);
    for (int i = 0; i < MAXEDGE; i++) {
      EdgeNode edgeNode = new EdgeNode();
      edgeNode.begin = scanner.nextInt();
      edgeNode.end = scanner.nextInt();
      edgeNode.weight = scanner.nextInt();
      e[i] = edgeNode;
    }
    // 从小到大排序
    Arrays.sort(
        e,
        new Comparator<EdgeNode>()
        {
          @Override
          public int compare(EdgeNode o1, EdgeNode o2) 
          {
            return o1.weight - o2.weight;
          }
        });
    MiniSpanTree();
  }

  static void MiniSpanTree() 
  {
    int n, m;
    int[] parent = new int[MAXEDGE]; // parent[i] 存储i的邻接的顶点
    for (int i = 0; i < MAXEDGE; i++)
    {
      parent[i] = 0; // 初始化
    }

    for (int i = 0; i < MAXEDGE; i++) 
    {
      n = find(parent, e[i].begin);
      m = find(parent, e[i].end);
      if (n != m) // 防止成环
      {
        parent[n] = m;
        System.out.println(e[i].begin + "->" + e[i].end);
      }
    }
  }

  static int find(int[] parent, int index)
  {
    while (parent[index] > 0) {
      index = parent[index];
    }
    return index;
  }
}

输入:
4 7 7
2 8 8
0 1 10
0 5 11
1 8 12
3 7 16
1 6 16
5 6 17
1 2 18
6 7 19
3 4 20
3 8 21
2 3 22
3 6 24
4 5 26
输出:    
    4->7
    2->8
    0->1
    0->5
    1->8
    3->7
    1->6
    6->7
1 + 3 =
快来做第一个评论的人吧~