Adjacency List Implementation in Python
<p>I'm a newbie to Python (and computer science in general), so bear with me.</p>

<p>I'm having trouble implementing an adjacency list in Python. I have learned how to implement it through a dictionary (I learned how through here lol), but I need to know how to do it using only basic lists (list of lists)</p>

<p>This is my code:</p>

<pre><code>with open("graph1.txt") as infile:
    vertices = []
    for line in infile:
        line = line.split()
        line = [int(i) for i in line]
        vertices.append(line)


adj = dict()

for edge in vertices:
    x, y = int(edge[0]), int(edge[1])
    if x not in adj: adj[x] = set()
    if y not in adj: adj[y] = set()
    adj[x].add(y)
    adj[y].add(x)
print(adj)
</code></pre>

<p>Any help is appreciated.
Cheers</p>

<p>You'll still be thinking in terms of a set of vertices, each with a set of adjacent vertices, but you will be implementing the sets as lists rather than with a more sophisticated <code>set</code> data structure. You will need a fast way to index into the top-level set, and the only way to do that is with integer indexes. So you want to assign a (natural or arbitrary) integer k to each vertex, then put that vertex's adjacency set (implemented as a list) into slot k of the top-level list. It is less important to provide for efficient indexing into the second-level lists, since you typically iterate over them rather than selecting a particular one, but since Python has a built-in list that happens to provide efficient indexing with integers, why not use it?</p>

<p>I agree with the comment that a variable called <code>vertices</code> shouldn't hold edges. Everyone in the world but you will be confused, and later you also will be confused. I suggest you use the name <code>vertices</code> for the top-level list I described above. Then the second-level lists can just hold indices into the top-level <code>vertices</code>. (Well, maybe you need edge objects, too -- I don't know what you are using this for -- but a purist's adjacency-list representation has no room for edge objects.)</p>

python adjacency-list