測試類
public class TestALGraph {
public static <E> void main(String[] args){
Scanner read=new Scanner(System.in);
ALGraph g=new ALGraph();
System.out.println("------------------------");
System.out.println("操作選項菜單:");
System.out.println("1.輸出圖");
System.out.println("2.添加邊");
System.out.println("3.刪除邊");
System.out.println("4.添加頂點");
System.out.println("5.刪除頂點");
System.out.println("6.圖的遍歷");
System.out.println("7.最短路徑");
System.out.println("8.最小生成樹");
System.out.println("0.退出");
System.out.println("------------------------");
int f=0,C=0,e,A,B;
char s;
do{
System.out.println("請輸入操作選項:");
e=read.nextInt();
if(e>8||e<0)
throw new InputMismatchException();//防止非法輸入
switch(e){
? case 1:{
? g.pntGraph();
? break;
? ? }
? ? case 2:{
? g.insertEdge();
? break;
? ? }
? ? case 3:{
? g.deleteEdge();
? break;
? ? }
? ? case 4:{
? g.insertVex();
? break;
? ? }
? ? case 5:{
? g.deleteVex();
? break;
? ? }
? ? case 6:{
? System.out.println("輸入遍歷方式:1 廣度優(yōu)先遍歷? 2 深度優(yōu)先遍歷");
? C=read.nextInt();
? if(C==1)
? g.DFSTraverse();
? else
? g.BFSTraverse();
? break;
? ? }
? ? case 7:{
? ? g.dijkstra();
? ? break;
? ? }
? ? case 8:{
? ? g.prim();
? break;
? ? }
}
}while(e!=0);
read.close();//測試類中不能關(guān)閉輸入,否者程序?qū)⒔K止
}
}
頂點類 用數(shù)組實現(xiàn)存儲頂點
public class VNode<E>{//存儲表的頂點
E data;//頂點
int indegree;//頂點的入度數(shù)
ENode firstadj;//頂點的鄰接邊
VNode(E vex){
this.data=vex;
}
}
邊類 用鏈表實現(xiàn)存儲頂點的關(guān)聯(lián)邊
public class ENode {//每個一個所連鏈表中的節(jié)點
int adjvex;//鄰接頂點的序號
int weight;//邊的權(quán)值
ENode next;
ENode(int adj,int data){//i,j,w
adjvex=adj;//j
weight=data;//w
}? ?
ENode(int adj){//i,j,w
adjvex=adj;//j
}? ?
}
public class ALGraph<E>{
VNode<E>[] vexs;//頂點表
? ? int vexnum=0;//實際最大點數(shù)
? ? int vex=0;//最大的點數(shù) 比實際值大5
? ? int edgenum=0;//需要添加的邊數(shù)
? ? int isdirection=0;//是否為有向圖
? ? final int MAXVALUE=10000;//模擬無窮大值
? ? boolean[] visited;//標記點是否被遍歷
? ? Scanner st=new Scanner(System.in);
? ? public ALGraph(){
? ? System.out.println("請輸入儲存的結(jié)點數(shù)和邊的條數(shù)以及圖的性質(zhì):例如 x y z(1無向圖,2有向圖)");
? ? vexnum=st.nextInt();
? ? edgenum=st.nextInt();
? ? isdirection=st.nextInt();
? ? vex=vexnum+5;//創(chuàng)建數(shù)組存儲點和邊時預(yù)留5的空間方便后續(xù)點的添加
? ? vexs=(VNode<E>[])Array.newInstance(VNode.class, vex);//創(chuàng)建存儲節(jié)點的數(shù)組
create_Graph(vexs);//構(gòu)造圖
? ? }
private void create_Graph(VNode<E>[] vexs) {//創(chuàng)建圖
int i,j,k,vi,vj;
char ch;
Scanner in=new Scanner(System.in);
System.out.println("請使用一行連續(xù)輸入圖的"+this.vexnum+"頂點名稱字符如AB...:");
char[] vname=in.nextLine().toCharArray();
//初始化頂點表
for(i=0;i<vexnum;i++)vexs[i]=new VNode(vname[i]);
//初始化鄰接矩陣
System.out.println("請輸入"+edgenum+"邊信息,使用頂點的序號輸入,如(i,j)為第i頂點到第j頂點的邊的權(quán)值轧拄,輸入i j weight,第一個頂點序號為0:");
int w=0;
for(i=0;i<edgenum;i++){
vi=in.nextInt();
vj=in.nextInt();
w=in.nextInt();
ENode vex1=new ENode(vj,w);//創(chuàng)建新插入的邊
? ? ENode vex2=new ENode(vi,w);
? ? if(vexs[vi].firstadj==null){//節(jié)點沒有相鄰點
? ? vexs[vi].firstadj=vex1;
? ? if(isdirection==1){//如果是無向圖在對應(yīng)vj-vi也添加數(shù)據(jù)
? ? vexs[vj].firstadj=vex2;
? ? }
? ? }else{//節(jié)點存在相鄰點 在距離頂點最近的地方添加
? ? vex1.next=vexs[vi].firstadj;
? ? vexs[vi].firstadj=vex1;
? ? if(isdirection==1){
? ? vex2.next=vexs[vj].firstadj;
? ? vexs[vj].firstadj=vex2;
? ? }
? ? }
}
}
public void pntGraph(){//輸出圖的信息
System.out.println("圖的頂點表為:");
ENode p;
if(vexnum==0){
System.out.println("圖未創(chuàng)建!");
return;
}
for(int i=0;i<vexnum;i++){
System.out.print(i+":");//輸出頂點名? valueOffCex函數(shù)用來獲取數(shù)組某個標號對應(yīng)的節(jié)點名稱? 例如A節(jié)點在數(shù)組的標號為0
p=vexs[i].firstadj;
while(p!=null){
System.out.print(vexs[i].data+"-->["+valueOffCex(p.adjvex)+","+p.weight+"]\t");
p=p.next;
}
System.out.println();
}
}
public boolean insertVex() {//插入點
System.out.println("請輸入需要添加的點:");
? char v=st.next().charAt(0);
if(vexnum>vex)?
return false;
vexs[vexnum++]=new VNode(v);
return true;
}
public boolean deleteVex() {//刪除點
System.out.println("請輸入需要刪除的點:");
? char v=st.next().charAt(0);
for(int i=0;i<vexnum;i++){
char ss=(char) vexs[i].data;
if(ss==v){
for(int j=i;j<vexnum-1;j++){
vexs[j]=vexs[j+1];
}
vexs[vexnum-1]=null;
vexnum--;
ENode ren;
ENode pre;
//刪除與點相關(guān)的邊
for(int col=0;col<vexnum;col++){//刪除與與頂點v相關(guān)的所有邊
if(vexs[col].firstadj==null)
? ? continue;
if(vexs[col].firstadj.adjvex==i){//刪除 與頂點直接相連的v的關(guān)聯(lián)邊
if(vexs[col].firstadj.next==null){
vexs[col].firstadj=null;//如果節(jié)點直接連接被刪除的節(jié)點不能直接指向空? 否則節(jié)點后面鏈表其他的點都無法訪問
}
else
vexs[col].firstadj=vexs[col].firstadj.next;
continue;
}
ren=vexs[col].firstadj;//刪除頂點鏈表中與v相關(guān)聯(lián)的邊
while(ren!=null){//刪除頂點鏈表內(nèi)部與刪除頂點的關(guān)聯(lián)邊
pre=ren;
ren=ren.next;
if(ren!=null&&ren.adjvex==i){
if(ren.next!=null)
? ? pre.next=ren.next;
else
pre.next=null;
break;
}
}
}
for(int col=0;col<vexnum;col++){//被刪除后面序號的點的序號-1 例如刪除4? 5就變成4 6變成5.
? ? ? ? ? ? ? ? ? ? ? ? ren=vexs[col].firstadj;
? ? ? ? ? ? ? ? ? ? ? ? while(ren!=null){
? ? ? ? ? ? if(ren.adjvex>i)
? ? ? ? ? ? ? ren.adjvex--;
? ? ? ? ? ? ren=ren.next;
? ? ? ? ? ? ? ? ? ? ? ? }
}
? ? return true;
}
}
return false;
}
public boolean insertEdge() {//插入邊
System.out.println("請輸入需要插入的邊:");
? int v1=st.nextInt();
? int v2=st.nextInt();
? ? if(v1<0||v2<0||v1>=vexnum||v2>=vexnum)
? ? throw new ArrayIndexOutOfBoundsException();
? ? ENode vex1=new ENode(v2);
? ? ENode vex2=new ENode(v1);
? ? if(vexs[v1].firstadj==null){//節(jié)點沒有相鄰點
? ? vexs[v1].firstadj=vex1;
? ? if(isdirection==1){
? ? vexs[v2].firstadj=vex2;
? ? }
? ? }else{//節(jié)點存在相鄰點 在距離頂點最近的地方添加
? ? vex1.next=vexs[v1].firstadj;
? ? vexs[v1].firstadj=vex1;
? ? if(isdirection==1){
? ? vex2.next=vexs[v2].firstadj;
? ? vexs[v2].firstadj=vex2;
? ? }
? ? }
? ? return true;
}
public boolean deleteEdge() {//刪除邊
System.out.println("請輸入需要刪除的邊:");
? int v1=st.nextInt();
? int v2=st.nextInt();
if(v1<0||v2<0||v1>=vexnum||v2>=vexnum)
? ? throw new ArrayIndexOutOfBoundsException();
? ? ENode ren=vexs[v1].firstadj;
? ? ENode pre=null;
? ? while(ren!=null&&ren.adjvex!=v2){
? ? pre=ren;
? ? ren=ren.next;
? ? }
? ? if(ren!=null){
? ? pre.next=ren.next;
? ? }
? ? if(isdirection==1){//無向圖
? ? ren=vexs[v2].firstadj;
? ? while(ren!=null&&ren.adjvex!=v1){
? ? pre=ren;
? ? ren=ren.next;
? ? }
? ? if(ren!=null){
? ? pre.next=ren.next;
? ? }
? ? }
? return true;
}
? ? public void DFSTraverse() {//深度優(yōu)先遍歷
? ? System.out.println("請輸入遍歷的源點名稱:");
? char v=st.next().charAt(0);
? ? int i=indexOfVex(v);
? ? if(i<0||i>vexnum)
throw new ArrayIndexOutOfBoundsException();
visited = new boolean[vexnum];//初始化用來標記的數(shù)組
StringBuilder sb=new StringBuilder();//創(chuàng)建字符串用來儲存遍歷的點 特點是創(chuàng)建后大小還可以變動? String則不行
Stack<Integer> stack =new Stack<Integer>();//創(chuàng)建棧用來存儲圖的點
stack.push(i);//將源點壓棧
visited[i]=true;//標記該點已經(jīng)被訪問
ENode ren;
while(!stack.isEmpty()){//取出棧頂元素并把該點關(guān)聯(lián)的未被訪問的點繼續(xù)壓入棧中直到全部訪問完畢
i=stack.pop();
sb.append(vexs[i].data+"-->");//將遍歷的點存在字符串中
ren=vexs[i].firstadj;
while(ren!=null){
if(visited[ren.adjvex]!=true){//點未被訪問并且不為無窮大有具體的數(shù)值就是可達
stack.push(ren.adjvex);
? ? ? visited[ren.adjvex]=true;
}
ren=ren.next;
}
}
sb.append("^");
System.out.println("深度優(yōu)先搜索結(jié)果:");
? ? String s=sb.length()>0?sb.substring(0,sb.length()):null;
? ? System.out.println(s);
}
public void BFSTraverse() {// 廣度優(yōu)先搜索遍歷
System.out.println("請輸入遍歷的源點名稱:");
? char v=st.next().charAt(0);
int i=indexOfVex(v);
if(i<0||i>vexnum)
throw new ArrayIndexOutOfBoundsException();
visited = new boolean[vexnum];
StringBuilder sb1=new StringBuilder();
Queue<Integer> queue =new LinkedList<Integer>();//創(chuàng)建隊列
queue.offer(i);//源點入隊
visited[i]=true;//標記已被訪問
ENode ren;
while(!queue.isEmpty()){
i=queue.poll();//出隊 并把該點相關(guān)的點入隊
sb1.append(vexs[i].data+"-->");
ren=vexs[i].firstadj;
while(ren!=null){
if(visited[ren.adjvex]!=true){
queue.offer(ren.adjvex);
visited[ren.adjvex]=true;
}
ren=ren.next;
}
}
sb1.append("^");
System.out.println("廣度優(yōu)先搜索結(jié)果:");
? ? String s=sb1.length()>0?sb1.substring(0,sb1.length()):null;
? ? System.out.println(s);
}
public void dijkstra() {//dijkstra算法實現(xiàn)最短路徑
System.out.println("請輸入遍歷的源點名稱:");
? char v=st.next().charAt(0);
int t=indexOfVex(v);
if(t<0||t>vexnum)
throw new ArrayIndexOutOfBoundsException();
int[] flag=new int[vexnum];//標記點是否被訪問
int[] D=new int[vexnum];//存儲該點到 源點 的最短距離
int[] P=new int[vexnum];//記錄到達該點最短路徑上的上一個節(jié)點
//選擇vi為源點床蜘,進行初始化 數(shù)組P 悠垛、D和flag組
for(int hi=0;hi<vexnum;hi++)//初始化D的數(shù)組 防止空指
D[hi]=MAXVALUE;
D[t]=0;flag[t]=1;P[t]=-1;//初始化源點的相關(guān)數(shù)組數(shù)值
ENode ren;
ren=vexs[t].firstadj;
while(ren!=null){//將源點數(shù)據(jù)存進D數(shù)組 并且將所有的點的上一個節(jié)點標記為源點
? ? D[ren.adjvex]=ren.weight;
? ? P[ren.adjvex]=t;
? ? ren=ren.next;
}
for(int n=1;n<vexnum;n++){//除源點還有n-1個節(jié)點未訪問蕾额,所以需要在循環(huán)上一步對源點操作的步驟n-1次
? int min=MAXVALUE;
? int j=0;
? for(int k=0;k<vexnum;k++){//假設(shè)選擇頂點k
? ? ? if(flag[k]==0&&D[k]<min){//未被訪問的節(jié)點,并且是數(shù)值D數(shù)組里最小的一個
? ? ? ? ? min=D[k];
? ? ? ? ? j=k;
? ? ? ? } ? ? ? ? ? ? ? ? ? ?
? ? }
? ? ? ? ? ? flag[j]=1; //標記頂點j已經(jīng)被訪問?
? ? ? ? ? ? ren=vexs[j].firstadj;
? ? ? ? ? ? while(ren!=null){ //修改通過Vj到達的頂點距離绩鸣,近修改怀大,反之不改
? ? ? ? ? ? //其余未被確定為最小距離的點到達改j點的距離加上j到源點的距離小于該點直接到達源點的距離就修改D的數(shù)據(jù) 同時把P改為j
? ? ? ? ? if(flag[ren.adjvex]==0&& ren.weight+min<D[ren.adjvex]){
? ? ? ? ? ? ? ? ? D[ren.adjvex]=ren.weight+min;
? ? ? ? P[ren.adjvex]=j;
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ren=ren.next;
? ? ? }
? ? ? ? ? if(j==0){//當(dāng)所有的點遍歷完了還是找不到不為無窮大最近的點時視該點孤立? 與其他點路徑不可達
? ? ? ? ? System.out.println("路徑不可達!");
? ? ? ? ? return;
? ? ? }
}
System.out.println("請輸入遍歷的終點:");
? char ss=st.next().charAt(0);
int r=indexOfVex(ss);//獲取該節(jié)點在數(shù)組的標號? 例如A點的標號為0
pntShortPath(t,r,D,P);//調(diào)用最短路徑輸出函數(shù)
}
public void pntShortPath(int v1,int v2,int[] d,int[] p){//輸出最短路徑
Stack<Integer> st=new Stack<Integer>();//創(chuàng)建棧 因為訪問的時候是從重點的標記反過來查找的? 利用棧先進后出的特點把錯誤順序反過來正序輸出
int k=v2;
while(p[k]!=-1){//將數(shù)組數(shù)據(jù)壓站
st.push(p[k]);
k=p[k];
}
System.out.println("頂點"+valueOffCex(v1)+"到頂點"+valueOffCex(v2)+"最短路徑長度為:"+d[v2]);
System.out.print("最短路徑為:");
int w;
while(!st.isEmpty()){
w=st.pop();
System.out.print(valueOffCex(w)+"-->");
}
System.out.println(valueOffCex(v2));
}
public void prim(){//prim算法實現(xiàn)最小生成樹
System.out.println("請輸入遍歷的源點名稱:");
? char v=st.next().charAt(0);
int p=indexOfVex(v);
if(p<0||p>vexnum)
throw new ArrayIndexOutOfBoundsException();
int[] cost=new int[vexnum];//存儲該點到達最近節(jié)點的距離
for(int hi=0;hi<vexnum;hi++)//初始化數(shù)組 防止空指
? cost[hi]=MAXVALUE;
int[] tree=new int[vexnum];//記錄最近的哪個點的標號
int vnum=vexnum;
boolean[] flag=new boolean[vnum];//標記該點是否被訪問? 被訪問的我們視為已經(jīng)找到了距離該點最近的點
int i,j,k=0,mincost;
ENode ren;
ren=vexs[p].firstadj;
while(ren!=null){//將源點到達各個點的距離賦給數(shù)組
? ? cost[ren.adjvex]=ren.weight;
? ? tree[ren.adjvex]=p;//頂點0到達的頂點為i
? ? ren=ren.next;
}
tree[p]=-1;//防止進入死循環(huán)造成越界異常 將源點的最近的節(jié)點的標號設(shè)為1
flag[p]=true;//以p為第一個樹根節(jié)點
for(i=1;i<vnum;i++){
mincost=MAXVALUE;
k=0;
for(j=0;j<vnum;j++){
if(flag[j]==false && cost[j]<mincost){
mincost=cost[j];
k=j;//k表示到鄰接頂點k到邊權(quán)小
}
}
flag[k]=true;//表示第k頂點已經(jīng)加入U集合
? ? ? ? ren=vexs[k].firstadj;
? ? ? ? while(ren!=null){
? ? ? ? ? ? if(flag[ren.adjvex]==false &&ren.weight<cost[ren.adjvex]){
? ? ? ? ? ? ? ? ? cost[ren.adjvex]=ren.weight;
? ? ? ? tree[ren.adjvex]=k;
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ren=ren.next;
? ? ? ? }
}
pntPrimTree(tree,cost,p);
System.out.println("^");
}
public void pntPrimTree(int[] tree,int[] cost,int begin){//輸出最小生成樹
int N=tree.length;
for(int i=0;i<N;i++){
if(tree[i]==begin){
System.out.print("("+valueOffCex(begin)+","+valueOffCex(i)+")["+cost[i]+"] --> ");
pntPrimTree(tree,cost,i);
}
}
}
public int getNumOfVertex() {//返回節(jié)點數(shù)
return vexnum;
}
public int indexOfVex(char v) {//定位點的位置
for(int i=0;i<vexnum;i++){
if(vexs[i].data.equals(v))
return i;
}
return -1;
}
public char valueOffCex(int v){//定位指定位置的頂點
if(v<0||v>vexnum)
return (Character) null;
return (char) vexs[v].data;
}
public int getEdge(int v1, int v2) {//獲取邊的權(quán)值
if(v1<0 || v2<0 || v1>=vexnum || v2>vexnum)
throw new ArrayIndexOutOfBoundsException();
ENode ren=vexs[v1].firstadj;
while(ren!=null){
if(ren.adjvex==v2){
return ren.weight;
}
ren=ren.next;
}
return 0;
}
}
小編整理了一些java進階學(xué)習(xí)資料和面試題呀闻,需要資料的請加JAVA高階學(xué)習(xí)Q群:701136382 這是小編創(chuàng)建的java高階學(xué)習(xí)交流群,加群一起交流學(xué)習(xí)深造潜慎。群里也有小編整理的2019年最新最全的java高階學(xué)習(xí)資料捡多!