자바 구현 그림 의 인접 표 저장 구조의 두 가지 방식 및 인 스 턴 스 응용 상세 설명

머리말
본 편 은 그림 의 인접 표 가 실현 하 는 두 가지 방식 에 대해 이야기 하고 자 한다.먼저 우 리 는'그림 을 배 우 는 인접 표 가 실현 하 는 관건 은':당신 이 만 든 그림 의 인접 표 의 대상 이 무엇 입 니까?
먼저 에서 그림 의 인접 표 에 대한 정 의 를 살 펴 보 자.
그림 G=(V,E)의 인접 표 는|V|개 목록 을 포함 하 는 배열 Adj 로 구성 되 어 있 음 을 나타 낸다.그 중에서 각 목록 은 V 의 정점 에 대응 하고 모든 u*8712°V 에 대해 인접 표 Adj[u]는 모든 만족 조건(u,v)*8712°E 의 정점 v 를 포함한다.즉,Adj[u]는 그림 G 에 있 는 정점 u 와 인접 한 정점 을 포함한다.(또는 그 는 이 정점 의 지침 을 가리 킬 수도 있다.)모든 인접 표 의 정점 은 보통 임의의 순서 로 저장 된다.
그림 의 인접 표 는 다음 그림 과 같다.

정 의 는 항상 어렵 고 이해 하기 어 려 운 것 입 니 다.다음은 그림 의 인접 표를 어떻게 실현 하 는 지 에 대해 이야기 하 겠 습 니 다!
1.인접 표 구축 도 는 반드시 그래프 대상,즉 그림 대상 이 필요 합 니 다!이 대상 은 정점 수,변수 와 그림 의 정점 집합 을 포함 합 니 다.
2.위 에서 말 한 바 와 같이 인접 링크 의 대상 은 먼저 우 리 는 인접 표 의 대상 을 확인 해 야 한다.정점 을 인접 링크 의 대상 으로 할 수 있 고 자 연 스 럽 게 옆 을 인접 링크 의 대상 으로 할 수 있다!다음은 이 두 가지 방식 에 대해 각각 설명 하 겠 습 니 다!
1.인접 링크 는 정점 을 대상 으로 구축 도 를 사용한다.
1.그래프 대상 클래스

/**
*      
* @author King
*/
public class Graph1 {
Vertex1[] vertexArray=new Vertex1[100];
int verNum=0;
int edgeNum=0;
}

2.Vertex 대상 클래스

/**
*      
* @author King
*/
public class Vertex1 {
String verName;
Vertex1 nextNode;
}

3.그림 의 실현 류

import java.util.Scanner;
public class CreateGraph3 {
/**
*        string          
* @param graph  
* @param str     
* @return      
*/
public Vertex1 getVertex(Graph1 graph,String str){
for(int i=0;i<graph.verNum;i++){
if(graph.vertexArray[i].verName.equals(str)){
return graph.vertexArray[i];
}
}
return null;
}
/**
*                ，         !
* @param graph     
*/
public void initialGraph(Graph1 graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("         ：");
graph.verNum=scan.nextInt();
graph.edgeNum=scan.nextInt();
System.out.println("         ：");
for(int i=0;i<graph.verNum;i++){
Vertex1 vertex=new Vertex1();
String name=scan.next();
vertex.verName=name;
vertex.nextNode=null;
graph.vertexArray[i]=vertex;
}
System.out.println("         ：");
for(int i=0;i<graph.edgeNum;i++){
String preV=scan.next();
String folV=scan.next();
Vertex1 v1=getVertex(graph,preV);
if(v1==null)
System.out.println("            ！");
//           ：    
Vertex1 v2=new Vertex1();
v2.verName=folV;
v2.nextNode=v1.nextNode;
v1.nextNode=v2;
//                    ，          ！
// Vertex1 reV2=getVertex(graph,folV);
// if(reV2==null)
// System.out.println("            ！");
// Vertex1 reV1=new Vertex1();
// reV1.verName=preV;
// reV1.nextNode=reV2.nextNode;
// reV2.nextNode=reV1;
}
}
/**
*        
* @param graph      
*/
public void outputGraph(Graph1 graph){
System.out.println("         ：");
for(int i=0;i<graph.verNum;i++){
Vertex1 vertex=graph.vertexArray[i];
System.out.print(vertex.verName);

Vertex1 current=vertex.nextNode;
while(current!=null){
System.out.print("-->"+current.verName);
current=current.nextNode;
}
System.out.println();
}
}
public static void main(String[] args) {
Graph1 graph=new Graph1();
CreateGraph3 createGraph=new CreateGraph3();
createGraph.initialGraph(graph);
createGraph.outputGraph(graph);
}
}

2.인접 링크 사용 변 을 대상 으로 구축 그림
1.그래프 대상 클래스

import java.util.ArrayList;
public class Graph {
ArrayList<Vertex> vertexList=new ArrayList<Vertex>();
int vertexNum=0;
int edgeNum=0;
public Graph(){}
}

2.Edge 대상 클래스

/**
*       
* @author King
*/
public class Edge {
int edgeName;
Edge next;
public Edge(){
}
}

3.Vertex 대상 클래스<여기 정점 대상 은 보조 변 구축 그림 일 뿐 인접 링크 의 대상 이 아 닙 니 다>

/**
*       
* @author King
*/
public class Vertex {
String vertexName;
Edge firstEdge=new Edge();
public Vertex(){
}
}

4.그림 의 실현 유형

import java.util.Scanner;
/**
*               
* @author King
*/
public class CreateGraph {
/**
*       String，      
* @param graph  
* @param str     
* @return           
*/
public int vtoe(Graph graph,String str){
for(int i=0;i<graph.vertexNum;i++){
if(graph.vertexList.get(i).vertexName.equals(str)){
return i;
}
}
return -1;
}
/**
*              
* @param graph  
*/
public void initialGraph(Graph graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("         ：");
graph.vertexNum=scan.nextInt();
graph.edgeNum=scan.nextInt();
System.out.println("         ：");
for(int i=0;i<graph.vertexNum;i++){
Vertex vertex=new Vertex();
String name=scan.next();
vertex.vertexName=name;
vertex.firstEdge=null;
graph.vertexList.add(vertex);
}
System.out.println("        ：");
for(int i=0;i<graph.edgeNum;i++){
String preV=scan.next();
String folV=scan.next();
int v1=vtoe(graph,preV);
int v2=vtoe(graph,folV);
if(v1==-1 || v2==-1)
System.out.println("        ！");
//           ：    
Edge edge1=new Edge();
edge1.edgeName=v2;
edge1.next=graph.vertexList.get(v1).firstEdge;
graph.vertexList.get(v1).firstEdge=edge1;
//              ，         
// Edge edge2=new Edge();
// edge2.edgeName=v1;
// edge2.next=graph.vertexList.get(v2).firstEdge;
// graph.vertexList.get(v2).firstEdge=edge2;
}
}
/**
*           
* @param graph  
*/
public void outputGraph(Graph graph){
Edge edge=new Edge();
for(int i=0;i<graph.vertexNum;i++){
System.out.print(graph.vertexList.get(i).vertexName);
edge=graph.vertexList.get(i).firstEdge;
while(edge!=null){
System.out.print("-->"+graph.vertexList.get(edge.edgeName).vertexName);
edge=edge.next;
}
System.out.println();
}
}
public static void main(String[] args) {
CreateGraph createGraph=new CreateGraph();
Graph graph=new Graph();
createGraph.initialGraph(graph);
createGraph.outputGraph(graph);
}
}

5.위 에 제 시 된 그림 의 그림 을 예 로 들 어 실행 결 과 를 보 여 줍 니 다.

3.인접 표 구축 그림 의 인 스 턴 스 사용
문제:무 작위 로 그림 을 만 듭 니 다(방향 이 있 거나 방향 이 없 는 그림 일 수 있 습 니 다).그림 의 정점 은 100 개 정도 입 니 다.방향 이 있 으 면 2000 개 정도 입 니 다.방향 이 없 으 면 1000 개 정도 입 니 다!변 의 입도 와 출 도 를 계산 하 다.
코드:
1.그래프 클래스

public class GraphRandom {
VertexRandom[] vertexArray=new VertexRandom[200];
int verNum=0;
int edgeNum=0;
}

2.Vertexl 류

public class VertexRandom {
int verName;
int inRadius,outRadius;
VertexRandom nextNode;
}

3.랜 덤 맵 구현 클래스

import java.util.Scanner;
/**
*        ，            
* @author King
*
*/
public class CreateGraph2 {
/**
*                 
* @param graph  
* @param name     
* @return      
*/
public VertexRandom getVertex(GraphRandom graph,int name){
for(int i=0;i<graph.verNum;i++){
if(graph.vertexArray[i].verName==name){
return graph.vertexArray[i];
}
}
return null;
}
/**
*             
* @param graph  
*/
public void randomSpanning(GraphRandom graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("           ：");
graph.verNum=scan.nextInt();
for(int i=1;i<=graph.verNum;i++){
VertexRandom vertex=new VertexRandom();
vertex.verName=i;
vertex.nextNode=null;
graph.vertexArray[i-1]=vertex;
}
int number=(int)(Math.random()*200+1000);
System.out.println("          ："+number);
graph.edgeNum=number;
for(int i=0;i<graph.edgeNum;i++){
int preV=(int)(Math.random()*100+1);
int folV=(int)(Math.random()*100+1);
while(folV==preV){
folV=(int)(Math.random()*100+1);
}
VertexRandom vertex1=getVertex(graph,preV);
if(vertex1==null)
System.out.println("         ！");
VertexRandom vertex2=new VertexRandom();
vertex2.verName=folV;
vertex2.nextNode=vertex1.nextNode;
vertex1.nextNode=vertex2;
//                
vertex1.outRadius++;
VertexRandom v2=getVertex(graph,folV);
if(v2==null)
System.out.println("         ！");
v2.inRadius++;
//              
// VertexRandom reVertex2=getVertex(graph,folV);
// if(reVertex2==null)
// System.out.println("         ！");
// VertexRandom reVertex1=new VertexRandom();
// reVertex1.verName=preV;
// reVertex1.nextNode=reVertex2.nextNode;
// reVertex2.nextNode=reVertex1;
}
}
/**
*         
* @param graph  
*/
public void outputGraph(GraphRandom graph){
System.out.println("         ：");
for(int i=0;i<graph.verNum;i++){
VertexRandom vertex=graph.vertexArray[i];
System.out.print(vertex.verName);

VertexRandom current=vertex.nextNode;
while(current!=null){
System.out.print("-->"+current.verName);
current=current.nextNode;
}
System.out.println();
}
}
/**
*          
* @param graph  
*/
public void IORadius(GraphRandom graph){
for(int i=0;i<graph.verNum;i++){
System.out.print("  "+(i+1)+"    ："+graph.vertexArray[i].outRadius);
System.out.println(",   ："+graph.vertexArray[i].inRadius);
}
}
public static void main(String[] args) {
GraphRandom graph=new GraphRandom();
CreateGraph2 createGraph2=new CreateGraph2();
createGraph2.randomSpanning(graph);
createGraph2.outputGraph(graph);
createGraph2.IORadius(graph);
}
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.