实现的功能:
1、建一个100个点,3000条边的随机图,用邻接链表保存图的信息。(图是随机建成的)
2、给一个点,找出该点到其他点的最短路。
package text1;
import java.util.Random;
import java.util.Scanner;
/*实验一:随机生成3000条边,100个顶点的有向图,找出从一个点到其他点的路径* * 用邻接链表来存图* * * *///定义链表结构
class note{note next = null;int pot;
}public class sf1 {//插边static void insert(note n,int p){//n是起点 p是终点note t = n;boolean b = true;while(t.next!=null){//去重t = t.next;if(t.pot == p){b = false;break;}}if(b == true){note newt = new note();newt.pot = p;newt.next = n.next;n.next = newt;}}//初始化100个顶点的有向随机图static note[] init(){Random r = new Random();int firp,desp;//分别代表生成随机边的起点和终点note[] pot = new note[100];//生成100个点for(int j = 0;j < 100;j ++){pot[j] = new note();//初始化顶点}for(int i = 0;i < 3000;i ++){ //生成3000条边firp = r.nextInt(100); //起点desp = r.nextInt(100); //终点insert(pot[firp],desp); //边存到邻接链表中}return pot;}//展示邻接链表static void display(note[] nt){note tem;for(int i = 0;i < 100;i ++){tem = nt[i];System.out.print("第"+i+"个点连接:");while(tem.next!=null){tem = tem.next;System.out.print(tem.pot + "-");}System.out.println("");}}//入队static void push(int[] que,int end,int pot){que[end] = pot;}static int pop(int fst){fst = fst + 1;return fst;}public static void main(String args[]){note[] link; //邻接链表link = init(); //初始化
// display(link);System.out.println("请随机输入一个0-99间的数,作为源点");int first; //源点Scanner sc = new Scanner(System.in);first = sc.nextInt();char[] color = new char[100];for(int i = 0;i < 100;i ++){color[i] = 'w';}int[] dest = new int[100];for(int j = 0;j < 100;j ++){dest[j] = -1;}int fst,end;int[] queue = new int[200]; //顶点队列push(queue,0,first);end = 1;fst = 0;dest[queue[fst]] = 0;color[queue[fst]] = 'g';while(end > fst){note t = link[queue[fst]];while(t.next!=null){t = t.next;if(color[t.pot]=='w'){color[t.pot] = 'g';dest[t.pot] = dest[queue[fst]] + 1;push(queue,end,t.pot);end ++;}}color[queue[fst]] = 'b';fst = pop(fst); }System.out.println("");for(int j = 0;j < 100;j ++){System.out.print("点"+j+"到源点的距离为: ");System.out.println(dest[j]);}}
}