我的代码没有显示图形的邻接列表

Question

我对java很陌生。我正在尝试读取一个具有Graph输入的.txt文件，我需要创建另一个文件，该文件将显示该Graph的输出（有向和无向图形的邻接列表和矩阵）。我能够完美地创建邻接矩阵的输出，但它没有正确显示列表。我的.txt文件如下所示：

7
10
0 1 2 4 3 5 6 5 5 3 2 3 5 0 6 2 0 4 1 5

这是我的代码

public class Node{
    int element;
    Node next;
    public Node(int elem, Node n){
        element = elem;
        next    = n;
    }
}
import java.util.*;
import java.io.*;
public class graph {
  public static void main (String[] args) throws IOException{
    Scanner scn = new Scanner(new File("D:/raj.txt"));
    int numVertices = scn.nextInt();
    int numEdges    = scn.nextInt();
    int [][] adMatrix = new int [numVertices][numVertices];
    Node  [] adList   = new Node[numVertices];
    for(int i=0; i<numVertices; i++) 
      adList[i] = new Node(i, null);
    for(int i=0; i<numEdges; i++){
      int u = scn.nextInt();
      int v = scn.nextInt();
      adMatrix[u][v] = 1;
      adMatrix[v][u] = 1;
      Node n;
      for(n=adList[u]; n.next!=null; n=n.next) 
        n.next = new Node(v, null);
      for(n=adList[v]; n.next!=null; n=n.next) 
        n.next = new Node(u, null);
    }
    PrintWriter pw = new PrintWriter(new File("D:/output using Java.txt"));
    pw.print("Adjacency Matrix:");
    pw.println();
    pw.println();
    for(int i=-1; i<numVertices; i++){
      for(int j=-1; j<numVertices; j++){
        if(i==-1 && j==-1) pw.print("     ");
        else if(i==-1 && j!=-1) pw.print(j + "   ");
        else if(i!=-1 && j==-1) pw.print(i + "    ");
        else                    
          pw.print(adMatrix[i][j] + "   ");
      }
      if(i==-1) 
        pw.println();
      pw.println();
    }
    pw.println();
    pw.print("Adjacency List:");
    pw.println();
    pw.println();
    for(int i=0; i<numVertices; i++){
      pw.print(i + " ");
      pw.println();
      pw.print(adList[i].element+ "------>");
       for(Node n = adList[i].next; n!=null; n=n.next){
        pw.print(n.element);
        if(n.next!=null) 
          pw.print("--->");
        else             
          pw.println();
      }
      }
    pw.close();
  }
}

输出文件如下所示：

Adjacency Matrix:
     0   1   2   3   4   5   6   
0    0   1   0   0   1   1   0   
1    1   0   0   0   0   1   0   
2    0   0   0   1   1   0   1   
3    0   0   1   0   0   1   0   
4    1   0   1   0   0   0   0   
5    1   1   0   1   0   0   1   
6    0   0   1   0   0   1   0   
Adjacency List:
0 
0------>1 
1------>2 
2------>3 
3------>4 
4------>5 
5------>6 
6------>

邻接列表未在输出文件中正确显示。请帮助我正确获取邻接列表。:)

Answer 1

您在此处的代码将向每个节点添加一个新节点，直到它到达末尾。换句话说，每次您尝试添加新鼻子时，它都会覆盖已经存在的内容。

  for(n=adList[u]; n.next!=null; n=n.next) 
      n.next = new Node(v, null);
  for(n=adList[v]; n.next!=null; n=n.next) 
      n.next = new Node(u, null);

试试这个。若要遍历到列表的末尾，循环中的唯一语句应该是前进到下一项的语句。此外，使用while使循环的意图更加清晰（IMO）。

n = adList[u];
while (n.next!=null) n=n.next;
n.next= new Node(v, null);

此外，这部分代码似乎没有达到您的预期。

  pw.print(i + " ");
  pw.println();
  pw.print(adList[i].element+ "------>");

根据您共享的输出，我认为您可能希望删除中间的换行符。另外，adList[i].element可能不应该与i相同。但它之所以发生，是因为您正在初始化邻接列表，如下所示：

for(int i=0; i<numVertices; i++) 
    adList[i] = new Node(i, null);

本质上，您正在使用一条循环到自身的边初始化每个顶点。所以你在这里有两个选择。您可以跳过列表中的第一个节点，也可以重写它以在初始化时adList[i]为 null。如果您选择第二个选项，那么您将需要处理一些烦人的边缘情况。我建议改为使用

for(int i=0; i<numVertices; i++) 
    adList[i] = new Node(-1, null);

这样你在每个列表上都有一个"标题"节点。如果您不小心打印了标题节点，它将很明显，因为它是 -1。然后如果你改变这个

  pw.print(i + " ");
  pw.println();
  pw.print(adList[i].element+ "------>");

对此：

  pw.print(i + " ");
  pw.print( "------>");

您将跳过标头节点，它应该按照您希望的方式工作。

------编辑------此外，不保证调用其中的println。

    if(n.next!=null) 
      pw.print("--->");
    else             
      pw.println();
  }
  // move it here
  }

您应该将其移动到外循环的末尾。

Answer 2

我想你想要：

  for(n=adList[u]; n.next!=null; n=n.next) { /* skipping */ }
    n.next = new Node(v, null);
  for(n=adList[v]; n.next!=null; n=n.next) { /* skipping */ }
    n.next = new Node(u, null);