如何在邻接链表中列出链表的所有成员

Question

我一直在研究这段代码，它从边的文本文件创建邻接表。它功能齐全，但我现在正在尝试弄清楚如何获取每个节点的度数：

    import java.io.*;
    import java.util.*;


    class Neighbor {
        public int vertexNum;
        public Neighbor next;
        public Neighbor(int vnum, Neighbor nbr) {
                this.vertexNum = vnum;
                next = nbr;
        }
    }

    class Vertex {
        String name;
        Neighbor adjList;
        Vertex(String name, Neighbor neighbors) {
                this.name = name;
                this.adjList = neighbors;
        }
    }


    public class Graph 
    {

        Vertex[] adjLists;

        public Graph(String file) throws FileNotFoundException 
        {
            Scanner fileScanner = new Scanner(new File(file));
            fileScanner.useDelimiter("[^A-Za-z0-9]");


            ArrayList<String> words = new ArrayList<String>();

            while (fileScanner.hasNext())
            {
                String nextWord = fileScanner.next();
                if (!words.contains(nextWord))
                {
                    words.add(nextWord);
                }
            }

            adjLists = new Vertex[words.size()];

            // read vertices
            for (int v=0; v < adjLists.length; v++) 
            {
                adjLists[v] = new Vertex(words.get(v), null);
            }

            // read edges
            Scanner sc = new Scanner(new File(file));

            while (sc.hasNext()) 
            {
                 // read vertex names and translate to vertex numbers
                int v1 = indexForName(sc.next());
                int v2 = indexForName(sc.next());

                // add v2 to front of v1's adjacency list and
                // add v1 to front of v2's adjacency list
                adjLists[v1].adjList = new Neighbor(v2, adjLists[v1].adjList);
                // Doesn't add the node twice if it's connected to itself
                if(v1!=v2) {
             adjLists[v2].adjList = new Neighbor(v1, adjLists[v2].adjList);
                }
            }         
        }

        int indexForName(String name) 
        {
            for (int v=0; v < adjLists.length; v++) {
                if (adjLists[v].name.equals(name)) {
                    return v;
                }
            }
            return -1;
        }  

        public void print() 
        {
            System.out.println();
            for (int v=0; v < adjLists.length; v++) {
                System.out.print(adjLists[v].name);
                for (Neighbor nbr=adjLists[v].adjList; nbr != null;nbr=nbr.next) {
                    System.out.print(" --> " + adjLists[nbr.vertexNum].name);
                }
                System.out.println("\n");
            }          

        }

        public static void main(String[] args) 
        throws IOException 
        {
            Scanner br = new Scanner(System.in);
            System.out.print("Enter graph input file name: ");
            String file = br.nextLine();
            Graph graph = new Graph(file);
            graph.print();
            br.close();

        }

    }

这是文本文件：

Sara Sam
Sara Ajay
Sam Sean
Sam Mira
Mira Jane
Jane Maria
Rahul Sapna
Sapna Rohit
Sapna Sapna
Rahul Sam

这是我从中得到的输出：

Sara --> Ajay --> Sam

Sam --> Rahul --> Mira --> Sean --> Sara

Ajay --> Sara

Sean --> Sam

Mira --> Jane --> Sam

Jane --> Maria --> Mira

Maria --> Jane

Rahul --> Sam --> Sapna

Sapna --> Sapna --> Rohit --> Rahul

Rohit --> Sapna

我想知道是否有某种方法可以计算出号码。邻接链表中每个顶点的边数。例如，如果我查看 Sapna：

Sapna --> Sapna --> Rohit --> Rahul

我希望我的输出显示 Sapna 的度数为 3 或者她有 3 条边连接到她。

所以，我一直想创建一个计算边的方法，但我不确定要将什么添加到我的 sum 变量中：

int countEdges()
    {
        int sum = 0;

        //traverse all vertex
        for (int v=0; v < adjLists.length; v++)

            // add all edge that are linked to the
            // current vertex
            sum += /*???*/;

        return sum;
    }

Answer 1

类似 print() 方法的东西怎么样？类似（未测试）：

    public void printNrOfEdges() 
    {
        System.out.println();
        for (int v=0; v < adjLists.length; v++) {
            int sum = 0;
            for (Neighbor nbr=adjLists[v].adjList; nbr != null;nbr=nbr.next) {
                //Add 1 for each neighbour
                sum++;
            }
            System.out.print(adjLists[v].name + ": " + sum);
            System.out.println("\n");
        }
    }

如何在邻接链表中列出链表的所有成员

How to list out all the members of a linked list in an adjacency linked list

java

networking

graph

linked-list

adjacency-list