problemofgraph.java

算法设计课中关于无向无权图的一些操作

import java.io.*;
import java.util.*;
class edge{
	int col;
	int row;
	public edge(int i,int j)
	{
		this.col=i;
		this.row=j;
	}
	public edge()
	{
		
	}
}
public class ProblemOfGraph {

	static int  readGraph(int g[][],edge edges[])throws Exception
	{
		FileReader fr=new FileReader("e:/matrix.txt");
		BufferedReader br=new BufferedReader(fr);
		String read=null;
		int i,j;
		int max=0,k=0;
		while((read=br.readLine())!=null)
		{
		    String[] tempArray=read.split(" ");
		    i=Integer.parseInt(tempArray[0]);
		    if(i>max) max=i;
		    j=Integer.parseInt(tempArray[1]);
		    if(j>max) max=j;
		    edges[k]=new edge(i,j);
		    k++;
		    g[i][g[i][0]]=j;
		    g[i][0]++;
		    g[j][g[j][0]]=i;
		    g[j][0]++;
		}
		return max;
	}
	static void printGraph(int g[][],int size)
	{
		for(int i=1;i<=size;i++)
		{
			System.out.print(i+"----");
			for(int j=1;j<g[i][0];j++)
				System.out.print(g[i][j]+" ");
			System.out.println();
		}
	}
	static void shorestPath(int g[][],int size)
	{
		int[] visited=new int[size+2];
		int[] father=new int[size+2];
		int[] queue=new int[size+2];
		int[] distance=new int[size+2];
		int front=0,rear=0,s,d;
		
		Scanner bin=new Scanner(System.in);
		System.out.print("输入起始点:");
		s=bin.nextInt();
		System.out.print("输入终止点:");
	    d=bin.nextInt();
	    visited[s]=1;
	    queue[rear]=s;
	    rear++;
	    int u;
	    while(rear!=front)
	    {
	    	u=queue[front];
	    	front++;
	    	for(int i=1;i<g[u][0];i++)
	    		if(visited[g[u][i]]==0)
	    		{
	    			father[g[u][i]]=u;
	    			visited[g[u][i]]=1;
	    			distance[g[u][i]]=distance[u]+1;
	    			queue[rear]=g[u][i];
	    			rear++;
	    		}
	    }
	    if(visited[d]==0) System.out.println(s+"和"+d+"之间不存在路径!");
	    else
	    {
	    	System.out.println(s+"到"+d+"的最短路径是:"+distance[d]);
		    System.out.print("路径为:");
		    System.out.print(d+"-");
		    while(father[d]!=s)
		    {
		    	System.out.print(father[d]+"-");
		    	d=father[d];
		    }
		    System.out.println(s);
	    }
	}
	static int judgeConnected(int g[][],int size)
	{
		int[] visited=new int[size+2];
		int[] queue=new int[size+2];
		int front=0,rear=0;
		queue[rear]=1;
		rear++;
		visited[1]=1;
		while(front!=rear)
		{
			int k=queue[front];
			front++;
			for(int i=1;i<g[k][0];i++)
				if(visited[g[k][i]]==0)
				{
					visited[g[k][i]]=1;
					queue[rear]=g[k][i];
					rear++;
				}
		}
		for(int j=1;j<=size;j++)
			if(visited[j]==0) return 0;
		return 1;
	}
	static void judgeTree(int g[][],int size)
	{
		if(judgeConnected(g,size)==0)
			System.out.println("不是树!");
		else if(judgeConnected(g,size)==1)
		{
			int edges=0;
			for(int i=1;i<=size;i++)
				edges+=g[i][0];
			edges-=size;
			if(size-1==edges) 
				System.out.println("是树!");
			else
				System.out.println("不是树!");
		}
	}
	static int foundSet(int tree[],int n)
	{
		if(tree[n]==n)
			return n;
		else
		{
			int k=tree[n];
			while(tree[k]!=k)
			{
				tree[k]=tree[tree[k]];
				k=tree[k];
			}
			return k;
		}
	}
	static void judgeHaveCircle(edge edges[],int g[][],int size)
	{
		int edgeNum=0;
		int[] tree=new int[size+2];
		int[] father=new int[size+2];
		for(int i=1;i<=size;i++)
			edgeNum+=g[i][0];
		edgeNum-=size;
		edgeNum=edgeNum/2;
		
		for(int i=1;i<=size;i++)
		{
			tree[i]=i;
			father[i]=i;
		}
		int i;
		for(i=0;i<edgeNum;i++)
		{
			int m=foundSet(tree,edges[i].col);
			int n=foundSet(tree,edges[i].row);
			if(father[edges[i].row]==edges[i].row)
				father[edges[i].row]=edges[i].col;
			if(m==n)
			{
				System.out.println("有环");
				System.out.print(edges[i].col+" ");
				int k=father[edges[i].col];
				while(k!=m)
				{
					System.out.print(k+" ");
					k=father[k];
				}
				System.out.println(m);
				System.out.print(edges[i].row+" ");
				k=father[edges[i].row];
				while(k!=m)
				{
					System.out.print(k+" ");
					k=father[k];
				}
				System.out.println(m);
			    break;
			}
			else if(edges[i].col==m&&edges[i].row!=n)
				tree[edges[i].col]=n;
			else if(edges[i].col!=m&&edges[i].row==n)
				tree[edges[i].row]=m;
			else if(edges[i].col==m&&edges[i].row==n)
				tree[n]=tree[m];
		}
	}
	public static void main(String[] args) throws Exception{
		int[][] g=new int[51][51];
		edge[] edges=new edge[1300];
		for(int i=0;i<51;i++)
			g[i][0]=1;
		int size=readGraph(g,edges);
		printGraph(g,size);
		shorestPath(g,size);
		if(judgeConnected(g,size)==1) System.out.println("是连通图!");
		else if(judgeConnected(g,size)==0) System.out.println("不是连通图!");
		judgeTree(g,size);
		judgeHaveCircle(edges,g,size);
	}
}