时间戳

首页 > 解决方案 > 在 Java 中读取图形的邻接列表时，如何避免重复边？

java - 在 Java 中读取图形的邻接列表时，如何避免重复边？

问题描述

我有一个代表图形邻接列表的 .txt 文件。它有 200 行，如下所示： 第一列表示顶点 ID，每个对应的行是顶点与之共享边的其他顶点的列表。

1   37  79  164 155 32  87  39  113 15  18  78  175 140 200 4   160 97  191 100 91  20  69  198 196 
2   123 134 10  141 13  12  43  47  3   177 101 179 77  182 117 116 36  103 51  154 162 128 30  
3   48  123 134 109 41  17  159 49  136 16  130 141 29  176 2   190 66  153 157 70  114 65  173 104 194 54  
4   91  171 118 125 158 76  107 18  73  140 42  193 127 100 84  121 60  81  99  80  150 55  1   35  23  93  
5   193 156 102 118 175 39  124 119 19  99  160 75  20  112 37  23  145 135 146 73  35  
6   155 56  52  120 131 160 124 119 14  196 144 25  75  76  166 35  87  26  20  32  23  
7   156 185 178 79  27  52  144 107 78  22  71  26  31  15  56  76  112 39  8   113 93  
8   185 155 171 178 108 64  164 53  140 25  100 133 9   52  191 46  20  150 144 39  62  131 42  119 127 31  7   
9   91  155 8   160 107 132 195 26  20  133 39  76  100 78  122 127 38  156 191 196 115 
10  190 184 154 49  2   182 173 170 161 47  189 101 153 50  30  109 177 148 179 16  163 116 13  90  185 
11  123 134 163 41  12  28  130 13  101 83  77  109 114 21  82  88  74  24  94  48  33  
12  161 109 169 21  24  36  65  50  2   101 159 148 54  192 88  47  11  142 43  70  182 177 179 189 194 33  
13  161 141 157 44  83  90  181 41  2   176 10  29  116 134 182 170 165 173 190 159 47  82  111 142 72  154 110 21  103 130 11  33  138 152 
14  91  156 58  122 62  113 107 73  137 25  19  40  6   139 150 46  37  76  39  127 
15  149 58  68  52  39  67  121 191 1   45  100 18  118 174 40  85  196 122 42  193 119 139 26  127 145 135 57  38  7

我正在尝试将此文件读入我制作的一些 Java 类中，但我不确定如何避免读取重复的边缘。对于每条边，在 .txt 文件中有两个与之关联的数字。前任。在第 8 行中，有一个数字 9 表示由顶点 8 和 9 共享的一条边。然后在第 9 行中，有一个数字 8 表示由 9 和 8 共享的同一条边。

我将此代码与 BufferedReader 一起使用，将每一行放入一个数组中，然后为每个非第一列顶点 ID 添加一条新边。

 

    private static UndirectedGraph constructGraph(String filename) throws IOException {
           
     UndirectedGraph graph = new UndirectedGraph();
    
    //count # of lines in the .txt file and make that many vertices
            int numLines = countLines("/home/paris/Downloads/kargercut.txt");
    
            for (int i = 0; i<=numLines; i++) {
                graph.addVertex(i);
    
            }
            
    //BufferedReader to make each row in .txt file into a split string array, from which I can parse Integers
            BufferedReader br = new BufferedReader(new FileReader("/home/paris/Downloads/kargercut.txt"));
            String s;
            ArrayList<String> vtxIDArray = new ArrayList<>();
            String[] sArray;
            
            while ((s = br.readLine()) != null ) {
                sArray = s.split(" ");
    
                for (int i = 1; i <= sArray.length - 1; i++) {
                graph.addEdge(Integer.parseInt(sArray[0]), Integer.parseInt(sArray[i]));  /*addEdge takes two vertex ID's as arguments and creates an edge in memory in all three of the aforementioned locations: one in each Vertex object, and one in the entire graph's "edgeList" ArrayList. */      
            
    }
    
            }
            System.out.println(Arrays.toString(graph.getVertexIDs()));
            
            br.close();
    
            return graph;
        }

我的 UndirectedEdge 课程：


public class UndirectedEdge {

    private Vertex end1;
    private Vertex end2;

    UndirectedEdge(Vertex end1, Vertex end2) {
        this.end1 = end1;
        this.end2 = end2;

    }

    public Vertex getEnd1() {
        return end1;
    }

    public Vertex getEnd2() {
        return end2;
    }

    public void setEnd1(Vertex end1) {
        this.end1 = end1;
    }

    public void setEnd2(Vertex end2) {
        this.end2 = end2;
    }
}

addEdge 方法：

public void addEdge(Integer end1ID, Integer end2ID) {

        Vertex end1 = findVertex(end1ID);
        Vertex end2 = findVertex(end2ID);

        if ((end1 == null) || (end2 == null)) {
            throw new IllegalArgumentException("1 or 2 of the endpoints don't exist.");
        }
        if (end1 == end2) throw new IllegalArgumentException("No self-loops allowed");


        UndirectedEdge newEdge = new UndirectedEdge(end1, end2);
        edgeList.add(newEdge);
        end1.addEdge(newEdge);
        end2.addEdge(newEdge);

    }

现在，我的程序中的一条边存储在 Vertex 类（每个端点的）和主 edgeList 类中。以我当前读取此文件的方式，对于每个边缘，我将在内存中的这三个位置中的每一个中拥有两倍的边缘。我不知道该怎么做。

标签： javagraph

解决方案

您要做的是在addEdge()方法中，检查该边是否已存在于您的图形中。您可能希望在您的UndirectedGraph类中实现一个新函数，该函数edgeExists(int vertex1, int vertex2)返回一个布尔值，指示您要在 vertex1 和 vertex2 之间添加的边是否已经存在。

然后，每次要添加新边时调用该函数。如果边缘还不存在，则添加它，否则不要。

一个简单的实现edgeExists可能只是检查 vertex1 对象是否在其邻接列表中包含 vertex2。

推荐阅读