提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

1.引入库

1.邻接表


1. 请根据无向图填空。
1. 2 2. 3 3. 4 4. 4 5. 6 6. 0 7. 0 8. 5 9. 1 10. 2 11. 3 12. 2

代码如下（示例）：

2. 请使用邻接表构造以上无向图，按照以下顺序。
（1） 创建Vertex类，用来存放顶点信息（包括data和firstEdge）；

class Vertex(object):
    def __init__(self,data):
        self.data = data
        self.firstEdge = None

（2） 创建Edge类，用来存放边信息（包括adjVex和next）；

class Edge(object):
    def __init__(self,adjVex):
        self.adjVex = adjVex
        self.next = None

（3） 创建LinkedGraph类，能通过该类构造无向图；

class LinkedGraph(object):
    # 实现输入图的顶点和边，能够得到邻接表
    def __init__(self,vers,edges):
        # 图的顶点
        self.vers = vers
        # 图的边
        self.edges = edges
        # vexLen 图的顶点个数
        self.vexLen = len(self.vers)
        # 存放顶点的列表
        self.listVex = [Vertex for i in range(self.vexLen)]
        for i in range(self.vexLen):
            self.listVex[i] = Vertex(self.vers[i])
        # 表示图的表
        for edge in self.edges:
            c1 = edge[0]
            c2 = edge[1]
            self.__addEdge(c1,c2)
            
    def __addEdge(self,c1,c2):
        # 找到c1,c2的下标值
        p1 = self.__getPosition(c1)
        p2 = self.__getPosition(c2)
        edge1 = Edge(p1)
        edge2 = Edge(p2)
        if self.listVex[p1].firstEdge is None:
            self.listVex[p1].firstEdge = edge2
        else:
            self.__LinkLast(self.listVex[p1],edge2)

        if self.listVex[p2].firstEdge is None:
            self.listVex[p2].firstEdge = edge1
        else:
            self.__LinkLast(self.listVex[p2], edge1)

    def __getPosition(self,key):
        for i in range(self.vexLen):
            if self.vers[i] == key:
                return i

    def __LinkLast(self,list,edge):
        p = list.firstEdge
        while p.next:
            p = p.next
        p.next = edge

    def print(self):
        for i in range(self.vexLen):
            print(self.listVex[i].data,end="->")
            edge = self.listVex[i].firstEdge
            while edge:
                print(self.listVex[edge.adjVex].data,end=" ")
                edge = edge.next
            print()

（提示：构造时接收两个参数，一个是顶点列表，另一个是边列表）
（4） 测试类，能够输出邻接表。

if __name__ == "__main__":
    vers = ['A','B','C','D','E','F','G']
    edges = [['A','C'],['A','D'],['B','E'],['B','F'],['C','E'],['C','G'],['D','F']]
    g = LinkedGraph(vers,edges)
    g.print()

9.png)

2.读入数据

代码如下（示例）：
可根据无向无权图的邻接表的，表示出无向有权图，有向无权图，有向有权图邻接表的代码。

# 图的存储结构——邻接表法
class Vertex(object):
    def __init__(self,data):
        self.data = data
        self.firstEdge = None

# 边类
class Edge(object):
    def __init__(self,adjVex):
        self.adjVex = adjVex
        self.next = None

# 邻接表类,输入顶点和边，得到邻接表
class LinkedGraph(object):
    # 实现输入图的顶点和边，能够得到邻接表
    def __init__(self,vers,edges):
        # 图的顶点
        self.vers = vers
        # 图的边
        self.edges = edges
        # vexLen 图的顶点个数
        self.vexLen = len(self.vers)
        # 存放顶点的列表
        self.listVex = [Vertex for i in range(self.vexLen)]
        for i in range(self.vexLen):
            self.listVex[i] = Vertex(self.vers[i])
        # 表示图的表
        for edge in self.edges:
            c1 = edge[0]
            c2 = edge[1]
            self.__addEdge(c1,c2)
            
    def __addEdge(self,c1,c2):
        # 找到c1,c2的下标值
        p1 = self.__getPosition(c1)
        p2 = self.__getPosition(c2)
        edge1 = Edge(p1)
        edge2 = Edge(p2)
        if self.listVex[p1].firstEdge is None:
            self.listVex[p1].firstEdge = edge2
        else:
            self.__LinkLast(self.listVex[p1],edge2)

        if self.listVex[p2].firstEdge is None:
            self.listVex[p2].firstEdge = edge1
        else:
            self.__LinkLast(self.listVex[p2], edge1)

    def __getPosition(self,key):
        for i in range(self.vexLen):
            if self.vers[i] == key:
                return i

    def __LinkLast(self,list,edge):
        p = list.firstEdge
        while p.next:
            p = p.next
        p.next = edge

    def print(self):
        for i in range(self.vexLen):
            print(self.listVex[i].data,end="->")
            edge = self.listVex[i].firstEdge
            while edge:
                print(self.listVex[edge.adjVex].data,end=" ")
                edge = edge.next
            print()
if __name__ == "__main__":
    vers = ['A','B','C','D','E','F','G']
    edges = [['A','C'],['A','D'],['B','E'],['B','F'],['C','E'],['C','G'],['D','F']]
    g = LinkedGraph(vers,edges)
    g.print()

运行结果如下：

data = pd.read_csv(
    'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
print(data.head())

该处使用的url网络请求的数据。

总结

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。
如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。