代码收藏家技术教程 2024-12-29

编程题实训-图Python版

任务描述
密密被困在一个迷宫里，迷宫有n个路口，编号为1-n。密密现在站在第一个路口，出口编号为m。先给出每个路口通向何处，问密密能否逃出迷宫。

编程要求
输入
多组数据，每组数据n+2行。第一行为一个正整数n代表路口的个数，之后n行，这n行中的第i行为第i个路口的向左路口、向前路口、向右路口。最后一行为一个正整数m代表迷宫的终点。当n=0时输入结束。

输出
每组数据输出一行，若密密能走出迷宫，输出“YES”，否则输出“NO”。

测试说明
平台会对你编写的代码进行测试：

测试输入：
6
0 2 0
3 5 6
0 0 4
0 0 0
0 0 0
7 0 0
7
3
2 0 0
0 0 0
0 0 0
3
0

预期输出：
YES
NO

tag=0
def DFS(k,a,m):
#深度搜索第k层，k:当前路口
    global tag
    tag=0
    if k==m:            #到达出口
        tag=1
        return 1
    for i in range(0,3):             #遍历向左路口、向前路口、向右路口
        if a[k][i]!=0 and tag!=1:         #如果当前路口有通路，并且没有走过
            DFS(a[k][i],a,m)           #进入下一个路口 ，递归
    return 0
def check():
    global tag
    if(tag==1):
        return 1
    else:
        return 0

任务描述
一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。

编程要求
输入
多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。

输出
每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 3
A B C
A B 1
B C 1
A C 3
A C
6 8
A B C D E F
A F 100
A E 30
A C 10
B C 5
C D 50
E D 20
E F 60
D F 10
A F
0 0

预期输出：
2
A B C
60
A E D F

class AMGraph:
    def __init__(self):
        self.vexs = []  # 顶点表
        self.arcs = []  # 邻接矩阵
        self.vexnum = 0  # 图的当前点数
        self.arcnum = 0  # 图的当前边数
    def locate_vex(self, name):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum+2):
            if self.vexs[i] == name:
                return i
        return -1
    def OrigialVex(self,u):
        return self.vexs[u]
    def create_udn(self):
        # 采用邻接矩阵表示法，创建无向网g
        self.vexnum,self.arcnum=map(int, input().split())
        if self.vexnum == 0 and self.arcnum == 0:
            return
        #vex_data = list(input().split())
        vex_data=input()
        str_list = vex_data.split()
        for i in range(0, self.vexnum):
           # vex_data.append(input().split())
            self.vexs.append(str_list[i])
        self.arcs = [[23727 for i in range(100)] for i in range(100)]  # 初始化邻接矩阵，边的权值均置为极大值INF
        for k in range(0, self.arcnum):  # 构造邻接矩阵
            v1,v2,w = input().split()  # 输入一条边依附的顶点及权值
            i = self.locate_vex(v1)
            j = self.locate_vex(v2) # 确定v1和v2在g中的位置，即顶点数组的下标
            self.arcs[i][j] = w  # 边<v1,v2>的权值为w
            #self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w
    def show_graph(self):
        for i in range(0, self.vexnum+1):
             if i != self.vexnum :
                  print(self.vexs[i], end=" ")
             else:
                  print(self.vexs[i], end="\n")
        for i in range(0, self.vexnum):
            print(self.vexs[i+1], end=" ")
            for j in range(0, self.vexnum):
               if j != self.vexnum - 1:
                   print(self.arcs[i][j], end=" ")
               else:
                   print(self.arcs[i][j], end="\n")
        return 'OK'
def ShortestPath_DIJ(self,V,D,Path):
#通过广度优先搜索方法遍历G来验证六度空间理论，Start为指定的一个起点（六度空间顶点的始点）
    S=[]
    n=self.vexnum
    v0=self.locate_vex(V)
    for v in range(0,n):      #访问标志数组初始化为false
        S.append(False)
        D.append(int(self.arcs[v0][v]))
        if D[v]< 23727:
            Path.append(v0)
        else:
            Path.append(-1)
    S[v0]=True
    D[v0]=0
    for i in range(1,n):
        Min=23727
        for w in range(0, n):
            if S[w]==False and D[w]<Min:
                v=w
                Min=D[w]
        S[v]=True
        for w in range(0,n):               #统计路径长度小于7的顶点个数
            if S[w]==False and (D[v]+int(self.arcs[v][w])<D[w]):
                D[w]=D[v]+int(self.arcs[v][w])
                Path[w]=v
def Find(self,v,Path):
    if Path[v]==-1:
        return
    else:
        Find(self,Path[v],Path)
        print(self.OrigialVex(Path[v]),end=" ")

任务描述
“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

编程要求
输入
多组数据，每组数据m+1行。第一行有两个数字n和m，代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b，代表这两个人互相认识。当n和m都等于0时，输入结束。

输出
每组数据输出n行，对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

测试说明
平台会对你编写的代码进行测试：

测试输入：
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
9 10
0 0

预期输出：
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%
1: 70.00%
2: 80.00%
3: 80.00%
4: 80.00%
5: 80.00%
6: 80.00%
7: 80.00%
8: 70.00%
9: 20.00%
10: 20.00%

MAX = 100
class LNode:
    def __init__(self):
        self.data = 0
        self.next = None
class ALGragh:
    def __init__(self):
        self.vexnum = 0
        self.arcnum = 0
        self.visit = [0] * MAX
        self.Queue = [0] * MAX
        self.V = []
        lnode = LNode()
        for i in range(MAX):
            self.V.append(lnode)
    def creat(self, vexnum, arcnum):
        self.vexnum = vexnum
        self.arcnum = arcnum
        # for i in range(vexnum):
        for i in range(1, vexnum + 1):
            ln = LNode()
            ln.data = i
            ln.next = None
            self.V[i] = ln
        # for i in range(arcnum):
        for i in range(1, 1 + arcnum):
            x, y = map(int, input().split())
            p = LNode()
            p.data = y
            p.next = self.V[x].next
            self.V[x].next = p
            q = LNode()
            q.data = x
            q.next = self.V[y].next
            self.V[y].next = q
        return 0
def SixDegree_BFS(g:ALGragh):
    # 通过广度优先搜索方法遍历G来验证六度空间理论,并按题目要求进行输出
    # 数据已经读入完成，完善BFS代码即可
    for j in range(1, 1 + g.vexnum):
        Visit_Num = 1
        front, rear, last = 0, 0, 0
        for i in range(1, 1 + g.vexnum):
            g.visit[i] = 0
        g.Queue[0] = j
        g.visit[j] = 1
        js = 0
        while front <= last:
            p = g.V[g.Queue[front]].next
            front += 1
            while p:
                if not g.visit[p.data]:
                    g.visit[p.data] = 1
                    Visit_Num += 1
                    rear += 1
                    g.Queue[rear] = p.data
                p = p.next
            if front > last:
                last = rear
                js += 1
                if js == 6:
                    break
        print("%d: %.2f%%" % (j, 100.0*Visit_Num/g.vexnum))

任务描述
给定一个无向图，在此无向图中增加一个新顶点。

编程要求
输入
多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有一个数字f，代表新插入的顶点编号。当n和m都等于0时，输入结束。

输出
每组数据输出n+1行。为增加顶点后的邻接表。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
2 3
4
2 1
1 2
4
0 0

预期输出：
1 2
2 3 1
3 2
4
1 2
2 1
4

class ArcNode:  # 边结点
    def __init__(self):
        self.adjvex = 0  # 该边所指向的顶点的位置
        self.nextarc = None  # 指向下一条边的指针
        self.info = None  # 和边相关的信息
class VNode:  # 顶点信息
    def __init__(self, data):
        self.data = data  # 顶点信息
        self.firstarc = None  # 指向第一条依附该顶点的边的指针
class ALGraph:  # 邻接表
    def __init__(self):
        self.vertices = []
        self.vexnum = 0  # 图当前的顶点数
        self.arcnum = 0  # 图当前的边数
    def locate_vex(self, data):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vertices[i].data == int(data):
                return i
        return -1;
    def create_udg(self):
        # 采用邻接表表示法，创建无向图g
        self.vexnum,self.arcnum=map(int, input().split())
        for i in range(0, self.vexnum):
            vdata = i+1  # 输入顶点值
            vertex = VNode(vdata)
            self.vertices.append(vertex)
        for k in range(0, self.arcnum):  # 输入各边，构造邻接表
            v1,v2=map(int ,input().split())  # 输入一条边依附的两个顶点
            i = self.locate_vex(v1)
            j = self.locate_vex(v2) # 确定v1和v2在self中位置，即顶点在self.vertices中的序号
            p1 = ArcNode()  # 生成一个新的边结点p1
            p1.adjvex = j+1  # 邻接点序号为j
            p1.nextarc = self.vertices[i].firstarc
            self.vertices[i].firstarc = p1  # 将新结点p1插入顶点v1的边表头部
            p2 = ArcNode()  # 生成另一个对称的新的边结点p2
            p2.adjvex = i+1  # 邻接点序号为i
            p2.nextarc = self.vertices[j].firstarc
            self.vertices[j].firstarc = p2  # 将新结点p1插入顶点v1的边表头部
    def PrintGraph(self):
        # 输出图G
        for i in range(0, self.vexnum):
            print(self.vertices[i].data, end="")
            p = self.vertices[i].firstarc  # 初始化指针p指向与顶点邻接的第一个边结点
            if (p == None):  # 不存在与顶点邻接的第一个边结点
                print(end="\n")
                continue
            else:
                print(end=" ")
                while (p.nextarc):
                    print(p.adjvex, end=" ")
                    p = p.nextarc
                print(p.adjvex, end="\n")
def insert_vex(self, v):
    # 在以邻接表形式存储的无向图g上插入顶点v
    if self.vexnum + 1 > 100:
        return 'INFEASIBLE'  # 判断插入操作是否合法
    self.vexnum = self.vexnum + 1  # 增加图的顶点数量
    vertex = VNode(v)  # 初始化新顶点对应的链表的头结点数据域的值并将指针域赋值为None
    self.vertices.append(vertex)
    return 'OK'

任务描述
给定一个无向图，在此无向图中增加一个新顶点。

输出
每组数据输出n+1行。为增加顶点后的邻接矩阵。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
2 3
4
2 1
1 2
4
0 0

预期输出：
0 1 2 3 4
1 0 1 0 0
2 1 0 1 0
3 0 1 0 0
4 0 0 0 0
0 1 2 4
1 0 1 0
2 1 0 0
4 0 0 0

INF = 0x3f3f3f3f
class AMGraph:
    def __init__(self):
        self.vexs = []  # 顶点表
        self.arcs = []  # 邻接矩阵
        self.vexnum = 0  # 图的当前点数
        self.arcnum = 0  # 图的当前边数
    def locate_vex(self, name):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum+1):
            if self.vexs[i] == name:
                return i
        return -1
    def create_udn(self):
        # 采用邻接矩阵表示法，创建无向网g
        self.vexnum,self.arcnum=map(int, input().split())
        for i in range(0, self.vexnum+1):
            vex_data = i
            self.vexs.append(vex_data)
        self.arcs = [[0 for i in range(100)] for i in range(100)]  # 初始化邻接矩阵，边的权值均置为极大值INF
        for k in range(0, self.arcnum):  # 构造邻接矩阵
            v1,v2=map(int ,input().split())
            w = 1  # 输入一条边依附的顶点及权值
            i = self.locate_vex(v1)-1
            j = self.locate_vex(v2)-1 # 确定v1和v2在g中的位置，即顶点数组的下标
            self.arcs[i][j] = w  # 边<v1,v2>的权值为w
            self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w
    def show_graph(self):
        for i in range(0, self.vexnum+1):
             if i != self.vexnum :
                  print(self.vexs[i], end=" ")
             else:
                  print(self.vexs[i], end="\n")
        for i in range(0, self.vexnum):
            print(self.vexs[i+1], end=" ")
            for j in range(0, self.vexnum):
               if j != self.vexnum - 1:
                   print(self.arcs[i][j], end=" ")
               else:
                   print(self.arcs[i][j], end="\n")
        return 'OK'
def insert_vex(self, v):
    # 在以邻接矩阵形式存储的无向图g上插入顶点v
    if self.vexnum + 1 > 100:
        return 'INFEASIBLE'  # 判断插入操作是否合法
    self.vexnum = self.vexnum + 1  # 增加图的顶点数量
    self.vexs.append(v)  # 将新顶点v存入顶点表
    for k in range(0, self.vexnum):  # 邻接矩阵相应位置的元素置为1
        self.arcs[self.vexnum][k] = 0
        self.arcs[k][self.vexnum] = 0
    return 'OK'

任务描述
给定一个无向图，在此无向图中删除一个顶点。

编程要求
输入
多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有一个数字f，代表删除的顶点编号。当n和m都等于0时，输入结束。

输出
每组数据输出n-1行。为删除顶点后的邻接表。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
2 3
1
2 1
1 2
2
0 0

预期输出：
2 3
3 2
1

class ArcNode:  # 边结点
    def __init__(self):
        self.adjvex = 0  # 该边所指向的顶点的位置
        self.nextarc = None  # 指向下一条边的指针
        self.info = None  # 和边相关的信息
class VNode:  # 顶点信息
    def __init__(self, data):
        self.data = data  # 顶点信息
        self.firstarc = None  # 指向第一条依附该顶点的边的指针
class ALGraph:  # 邻接表
    def __init__(self):
        self.vertices = []
        self.vexnum = 0  # 图当前的顶点数
        self.arcnum = 0  # 图当前的边数
    def locate_vex(self, data):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vertices[i].data == int(data):
                return i
        return -1;
    def create_udg(self):
        # 采用邻接表表示法，创建无向图g
        self.vexnum, self.arcnum = map(int, input().split())
        for i in range(0, self.vexnum):
            vdata = i + 1  # 输入顶点值
            vertex = VNode(vdata)
            self.vertices.append(vertex)
        for k in range(0, self.arcnum):  # 输入各边，构造邻接表
            v1, v2 = map(int, input().split())  # 输入一条边依附的两个顶点
            i = self.locate_vex(v1)
            j = self.locate_vex(v2)  # 确定v1和v2在self中位置，即顶点在self.vertices中的序号
            p1 = ArcNode()  # 生成一个新的边结点p1
            p1.adjvex = j + 1  # 邻接点序号为j
            p1.nextarc = self.vertices[i].firstarc
            self.vertices[i].firstarc = p1  # 将新结点p1插入顶点v1的边表头部
            p2 = ArcNode()  # 生成另一个对称的新的边结点p2
            p2.adjvex = i + 1  # 邻接点序号为i
            p2.nextarc = self.vertices[j].firstarc
            self.vertices[j].firstarc = p2  # 将新结点p1插入顶点v1的边表头部
    def PrintGraph(self):
           # 输出图G
           for i in range(0, self.vexnum):
               print(self.vertices[i].data, end=" ")
               p = self.vertices[i].firstarc  # 初始化指针p指向与顶点邻接的第一个边结点
               if (p == None):  # 不存在与顶点邻接的第一个边结点
                   print(end="\n")
                   continue
               else:
                   # print(" ")
                   while (p.nextarc):
                       print(p.adjvex, end=" ")
                       p = p.nextarc
                   print(p.adjvex, end="\n")
def delete_vex(self, v):
    # 在以邻接表形式存储的无向图g上删除顶点v
    n = self.locate_vex(v)+1
    if n == -1:  # 如果n的值为-1，表示删除的顶点v不存在
        return 'ERROR'
    for i in range(n-1, self.vexnum - 1):  # 把v的顶点信息删除，后面顶点向前移动
        self.vertices[i] = self.vertices[i + 1]
    self.vexnum = self.vexnum - 1  # 顶点数减1
    for i in range(0, self.vexnum):  # 遍历图，删除顶点v相关的边
        p = self.vertices[i].firstarc
        q = self.vertices[i].firstarc  # p指向当前结点的前驱,q指向当前结点
        if n == p.adjvex:
            # 如果当前结点的第一条边关联的结点为v，则直接删除该边
            self.vertices[i].firstarc = self.vertices[i].firstarc.nextarc
            self.arcnum = self.arcnum - 1
            continue
        else:
            q = q.nextarc  # 继续比较后面的边结点
            while q is not None:
                #print(q.adjvex, end=' ')
                if n == q.adjvex:
                    # 存在与v相关联的边，则删除该边
                    p.nextarc = q.nextarc
                    self.arcnum = self.arcnum - 1
                    break
                p = q  # 没找到与v相关联的边，指针后移
                q = q.nextarc
        #print()
    return 'OK'

任务描述
给定一个无向图，在此无向图中增加一条边。

编程要求
输入
多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有两个数字f和g，代表增加的边所依附的两个顶点。当n和m都等于0时，输入结束。

输出
每组数据输出n行。为增加边后的邻接表。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
2 3
3 1
3 1
1 2
1 3
0 0

预期输出：
1 3 2
2 3 1
3 1 2
1 3 2
2 1
3 1

class ArcNode:  # 边结点
    def __init__(self):
        self.adjvex = 0  # 该边所指向的顶点的位置
        self.nextarc = None  # 指向下一条边的指针
        self.info = None  # 和边相关的信息
class VNode:  # 顶点信息
    def __init__(self, data):
        self.data = data  # 顶点信息
        self.firstarc = None  # 指向第一条依附该顶点的边的指针
class ALGraph:  # 邻接表
    def __init__(self):
        self.vertices = []
        self.vexnum = 0  # 图当前的顶点数
        self.arcnum = 0  # 图当前的边数
    def locate_vex(self, data):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vertices[i].data == int(data):
                return i
        return -1;
    def create_udg(self):
        # 采用邻接表表示法，创建无向图g
        self.vexnum, self.arcnum = map(int, input().split())
        for i in range(0, self.vexnum):
            vdata = i + 1  # 输入顶点值
            vertex = VNode(vdata)
            self.vertices.append(vertex)
        for k in range(0, self.arcnum):  # 输入各边，构造邻接表
            v1, v2 = map(int, input().split())  # 输入一条边依附的两个顶点
            i = self.locate_vex(v1)
            j = self.locate_vex(v2)  # 确定v1和v2在self中位置，即顶点在self.vertices中的序号
            p1 = ArcNode()  # 生成一个新的边结点p1
            p1.adjvex = j + 1  # 邻接点序号为j
            p1.nextarc = self.vertices[i].firstarc
            self.vertices[i].firstarc = p1  # 将新结点p1插入顶点v1的边表头部
            p2 = ArcNode()  # 生成另一个对称的新的边结点p2
            p2.adjvex = i + 1  # 邻接点序号为i
            p2.nextarc = self.vertices[j].firstarc
            self.vertices[j].firstarc = p2  # 将新结点p1插入顶点v1的边表头部
    def PrintGraph(self):
           # 输出图G
           for i in range(0, self.vexnum):
               print(self.vertices[i].data, end=" ")
               p = self.vertices[i].firstarc  # 初始化指针p指向与顶点邻接的第一个边结点
               if (p == None):  # 不存在与顶点邻接的第一个边结点
                   # print("\n")
                   continue
               else:
                   # print(" ")
                   while (p.nextarc):
                       print(p.adjvex, end=" ")
                       p = p.nextarc
                   print(p.adjvex, end="\n")
def insert_arc(self, v, w):
    # 在以邻接表形式存储的无向图g上插入边(v,w)
    i = self.locate_vex(v)
    j = self.locate_vex(w)  # 确定v和w在g中的位置
    if i == -1:  # 判断插入位置是否合法
        return 'ERROR'
    if j == -1:  # 判断插入位置是否合法
        return 'ERROR'
    p1 = ArcNode()  # 生成一个新的边结点*p1
    p1.adjvex = j+1
    p1.nextarc = self.vertices[i].firstarc
    self.vertices[i].firstarc = p1  # 将新结点*p1插入顶点v的边表头部
    p2 = ArcNode()
    p2.adjvex = i+1
    p2.nextarc = self.vertices[j].firstarc  # 将新结点*p1插入顶点w的边表头部
    self.vertices[j].firstarc = p2
    self.arcnum = self.arcnum + 1
    return 'OK'

任务描述
给定一个无向图，在此无向图中增加一条边。

输出
每组数据输出n行。为增加边后的邻接矩阵。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
2 3
3 1
3 1
1 2
1 3
0 0

预期输出：
0 1 2 3
1 0 1 1
2 1 0 1
3 1 1 0
0 1 2 3
1 0 1 1
2 1 0 0
3 1 0 0

class AMGraph:
    def __init__(self):
        self.vexs = []  # 顶点表
        self.arcs = []  # 邻接矩阵
        self.vexnum = 0  # 图的当前点数
        self.arcnum = 0  # 图的当前边数
    def locate_vex(self, name):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum+1):
            if self.vexs[i] == int(name):
                return i
        return -1
    def create_udn(self):
        # 采用邻接矩阵表示法，创建无向网g
        self.vexnum,self.arcnum=map(int, input().split())
        for i in range(0, self.vexnum+1):
            vex_data = i
            self.vexs.append(vex_data)
        self.arcs = [[0 for i in range(100)] for i in range(100)]  # 初始化邻接矩阵，边的权值均置为极大值INF
        for k in range(0, self.arcnum):  # 构造邻接矩阵
            v1,v2=map(int ,input().split())
            w = 1  # 输入一条边依附的顶点及权值
            i = self.locate_vex(int(v1))-1
            j = self.locate_vex(int(v2))-1 # 确定v1和v2在g中的位置，即顶点数组的下标
            self.arcs[i][j] = w  # 边<v1,v2>的权值为w
            self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w
    def show_graph(self):
        for i in range(0, self.vexnum+1):
             if i != self.vexnum :
                  print(self.vexs[i], end=" ")
             else:
                  print(self.vexs[i], end="\n")
        for i in range(0, self.vexnum):
            print(self.vexs[i+1], end=" ")
            for j in range(0, self.vexnum):
               if j != self.vexnum - 1:
                   print(self.arcs[i][j], end=" ")
               else:
                   print(self.arcs[i][j], end="\n")
        return 'OK'
def insert_arc(self, v, w):
    # 在以邻接矩阵形式存储的无向图g上插入边(v,w)
    i = self.locate_vex(v)-1
    j = self.locate_vex(w)-1
    if i < 0:  # 判断插入位置是否合法
        return 'ERROR'
    if j < 0:  # 判断插入位置是否合法
        return 'ERROR'
    self.arcs[i][j] = self.arcs[j][i] = 1  # 在邻接矩阵上增加对应的边
    self.arcnum = self.arcnum + 1  # 边数加１
    return 'OK'

任务描述
给定一个无向图，在此无向图中删除一条边。

编程要求
输入
多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有两个数字f和g，代表删除的边所依附的两个顶点。当n和m都等于0时，输入结束。

输出
每组数据输出n行。为删除边后的邻接表。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
2 3
3 2
3 1
1 2
1 2
0 0

预期输出：
1 2
2 1
3
1
2
3

class ArcNode:  # 边结点
    def __init__(self):
        self.adjvex = 0  # 该边所指向的顶点的位置
        self.nextarc = None  # 指向下一条边的指针
        self.info = None  # 和边相关的信息
class VNode:  # 顶点信息
    def __init__(self, data):
        self.data = data  # 顶点信息
        self.firstarc = None  # 指向第一条依附该顶点的边的指针
class ALGraph:  # 邻接表
    def __init__(self):
        self.vertices = []
        self.vexnum = 0  # 图当前的顶点数
        self.arcnum = 0  # 图当前的边数
    def locate_vex(self, data):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vertices[i].data == int(data):
                return i
        return -1;
    def create_udg(self):
        # 采用邻接表表示法，创建无向图g
        self.vexnum,self.arcnum= map(int, input().split())  # 输入总顶点数和总边数
        for i in range(0, self.vexnum):
            vdata = i+1  # 输入顶点值
            vertex = VNode(vdata)
            self.vertices.append(vertex)
        for k in range(0, self.arcnum):  # 输入各边，构造邻接表
            v1, v2 = map(int, input().split())  # 输入一条边依附的两个顶点
            i = self.locate_vex(v1)
            j = self.locate_vex(v2) # 确定v1和v2在self中位置，即顶点在self.vertices中的序号
            p1 = ArcNode()  # 生成一个新的边结点p1
            p1.adjvex = j+1  # 邻接点序号为j
            p1.nextarc = self.vertices[i].firstarc
            self.vertices[i].firstarc = p1  # 将新结点p1插入顶点v1的边表头部
            p2 = ArcNode()  # 生成另一个对称的新的边结点p2
            p2.adjvex = i+1  # 邻接点序号为i
            p2.nextarc = self.vertices[j].firstarc
            self.vertices[j].firstarc = p2  # 将新结点p1插入顶点v1的边表头部
    def PrintGraph(self):
           # 输出图G
           for i in range(0, self.vexnum):
               print(self.vertices[i].data, end=" ")
               p = self.vertices[i].firstarc  # 初始化指针p指向与顶点邻接的第一个边结点
               if (p == None):  # 不存在与顶点邻接的第一个边结点
                   print(end="\n")
                   continue
               else:
                   # print(" ")
                   while (p.nextarc):
                       print(p.adjvex, end=" ")
                       p = p.nextarc
                   print(p.adjvex, end="\n")
def delete_arc(self, v, w):
    # 在以邻接表形式存储的无向图g上删除边<v，w>
    i = self.locate_vex(v)
    j = self.locate_vex(w)  # 确定v和w在g中的位置
    if i == -1:  # 判断删除位置是否合法
        return 'ERROR'
    if j == -1:  # 判断删除位置是否合法
        return 'ERROR'
    if self.vertices[i].firstarc.adjvex == j+1:
        # 从顶点v所在的边链表遍历链表进行查找，第一个边结点是(v,w)，直接删除
        self.vertices[i].firstarc = self.vertices[i].firstarc.nextarc
    else:
        # 第一个边结点不是(v,w)，继续向后查找(v,w)
        p1 = self.vertices[i].firstarc  # p1为前驱结点，p2为当前结点
        p2 = p1.nextarc
        while p2 is not None:
            if p2.adjvex == j+1:  # 在链表中找到边结点(v,w)
                p1.nextarc = p2.nextarc
                break
            p1 = p2
            p2 = p2.nextarc
    if self.vertices[j].firstarc.adjvex == i+1:
        # 从顶点w所在的边链表遍历链表进行查找，第一个边结点是(w,v)，直接删除
        self.vertices[j].firstarc = self.vertices[j].firstarc.nextarc
    else:
        # 第一个边结点不是(w,v)，继续向后查找(w,v)
        p1 = self.vertices[j].firstarc
        p2 = p1.nextarc
        while p2 is not None:
            if p2.adjvex == i+1:  # 在链表中找到边结点(w,v)
                p1.nextarc = p2.nextarc
                break
            p1 = p2
            p2 = p2.nextarc
    self.arcnum = self.arcnum - 1  # 边的数目减1
    return 'OK'

任务描述
给定一个无向图，在此无向图中删除一条边。

输出
每组数据输出n行。为删除边后的邻接矩阵。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
2 3
3 2
3 1
1 2
1 2
0 0

预期输出：
0 1 2 3
1 0 1 0
2 1 0 0
3 0 0 0
0 1 2 3
1 0 0 0
2 0 0 0
3 0 0 0

class AMGraph:
    def __init__(self):
        self.vexs = []  # 顶点表
        self.arcs = []  # 邻接矩阵
        self.vexnum = 0  # 图的当前点数
        self.arcnum = 0  # 图的当前边数
    def locate_vex(self, name):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum+1):
            if self.vexs[i] == int(name):
                return i
        return -1
    def create_udn(self):
        # 采用邻接矩阵表示法，创建无向网g
        self.vexnum,self.arcnum=map(int, input().split())
        for i in range(0, self.vexnum+1):
            vex_data = i
            self.vexs.append(vex_data)
        self.arcs = [[0 for i in range(100)] for i in range(100)]  # 初始化邻接矩阵，边的权值均置为极大值INF
        for k in range(0, self.arcnum):  # 构造邻接矩阵
            v1,v2=map(int ,input().split())
            w = 1  # 输入一条边依附的顶点及权值
            i = self.locate_vex(int(v1))-1
            j = self.locate_vex(int(v2))-1 # 确定v1和v2在g中的位置，即顶点数组的下标
            self.arcs[i][j] = w  # 边<v1,v2>的权值为w
            self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w
    def show_graph(self):
        for i in range(0, self.vexnum+1):
             if i != self.vexnum :
                  print(self.vexs[i], end=" ")
             else:
                  print(self.vexs[i], end="\n")
        for i in range(0, self.vexnum):
            print(self.vexs[i+1], end=" ")
            for j in range(0, self.vexnum):
               if j != self.vexnum - 1:
                   print(self.arcs[i][j], end=" ")
               else:
                   print(self.arcs[i][j], end="\n")
        return 'OK'
def delete_arc(self, v, w):
    # 在以邻接矩阵形式存储的无向图g上删除边(v,w)
    i = self.locate_vex(v)-1
    j = self.locate_vex(w)-1
    if i < 0:  # 判断插入位置是否合法
        return 'ERROR'
    if j < 0:  # 判断插入位置是否合法
        return 'ERROR'
    self.arcs[i][j] = self.arcs[j][i] = 0 # 在邻接矩阵上删除边
    self.arcnum = self.arcnum - 1  # 边数减１
    return 'OK'

任务描述
一个连通图采用邻接表作为存储结构。设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

编程要求
输入
多组数据，每组m+2数据行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个整数h和k，代表边依附的两个顶点。第m+2行有一个整数d，代表从d开始遍历。当n和m都等于0时，输入结束。

输出
每组数据输出一行，为深度优先搜索的遍历结果。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
1 3
1
2 1
1 2
2
0 0

预期输出：
1 2 3
2 1

max_size = 100
class SqStack:
    def __init__(self):
        # 初始化顺序栈
        self.elem = [None] * max_size  # 为顺序栈动态分配一个最大容量为max_size的数组空间
        self.top, self.base = 0, 0  # top和base都指向栈底元素在顺序栈中的位置，空栈
        self.stack_size = max_size  # stack_size置为栈的最大容量max_size
    def push(self, e):
        # 将元素压入栈
        if self.top - self.base == self.stack_size:  # 栈满
            raise Exception('栈空间已满')
        self.elem[self.top] = e  # 元素e压入栈顶,栈顶指针加1
        self.top += 1
    def pop(self):
        # 将栈顶元素弹出
        if self.top == self.base:
            raise Exception('栈已空')
        self.top -= 1  # 栈顶指针减1，并返回栈顶元素
        return self.elem[self.top]
    def stack_empty(self):
        # 判断栈是否为空
        return self.top == self.base
class ArcNode:  # 边结点
    def __init__(self):
        self.adjvex = 0  # 该边所指向的顶点的位置
        self.nextarc = None  # 指向下一条边的指针
        self.info = None  # 和边相关的信息
class VNode:  # 顶点信息
    def __init__(self, data):
        self.data = data  # 顶点信息
        self.firstarc = None  # 指向第一条依附该顶点的边的指针
class ALGraph:  # 邻接表
    def __init__(self):
        self.vertices = []
        self.vexnum = 0  # 图当前的顶点数
        self.arcnum = 0  # 图当前的边数
    def locate_vex(self, data):
    # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vertices[i].data == int(data):
                return i
    def create_udg(self):
        # 采用邻接表表示法，创建无向图g
        self.vexnum, self.arcnum = map(int, input().split())
        for i in range(0, self.vexnum):
            vdata = i + 1  # 输入顶点值
            vertex = VNode(vdata)
            self.vertices.append(vertex)
        for k in range(0, self.arcnum):  # 输入各边，构造邻接表
            v1, v2 = map(int, input().split())  # 输入一条边依附的两个顶点
            i = self.locate_vex(v1)
            j = self.locate_vex(v2)  # 确定v1和v2在self中位置，即顶点在self.vertices中的序号
            p1 = ArcNode()  # 生成一个新的边结点p1
            p1.adjvex = j + 1  # 邻接点序号为j
            p1.nextarc = self.vertices[i].firstarc
            self.vertices[i].firstarc = p1  # 将新结点p1插入顶点v1的边表头部
            p2 = ArcNode()  # 生成另一个对称的新的边结点p2
            p2.adjvex = i + 1  # 邻接点序号为i
            p2.nextarc = self.vertices[j].firstarc
            self.vertices[j].firstarc = p2  # 将新结点p1插入顶点v1的边表头部
def dfs(self, V):
    # 从第v个顶点出发非递归实现深度优先遍历图G
    visited = []  # 访问标志数组，其初值为"false"
    for i in range(0, 100):
        visited.append('false')  # 访问标志数组初始化
    s = SqStack()  # 构造一个空栈
    v = self.locate_vex(V)+1
    s.push(v)  # 顶点v进栈
    cnt=0
    while not s.stack_empty():
        k = int(s.pop()) -1# 栈顶元素k出栈
        if visited[k] == 'false':  # k未被访问
            cnt=cnt+1
            if cnt<self.vexnum:
                print(self.vertices[k].data, end=" ")  # 访问第k个顶点
            else:
                print(self.vertices[k].data, end="\n")
            visited[k] = 'true'
        p = self.vertices[k].firstarc  # p指向k的边链表的第一个边结点
        while p is not None:  # 边结点非空
            w = p.adjvex   # 表示w是k的邻接点
            k=w-1
            if visited[k] == 'false':
                s.push(w)  # 如果w未访问，w进栈
            p = p.nextarc  # p指向下一个边结点

任务描述
设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点。

编程要求
输入
多组数据，每组数据m+2行。每组数据第一行为两个整数n和m，代表有n个顶点m条路。顶点编号为1到n。第二行到第m+1行每行有三个整数a，b和c，代表顶点a和顶点b之间有一条长度为c的路。第m+2有一个整数v，代表顶点v。当n和m都等于0时，输入结束。

输出
每组数据输出两行。第一行为最短路径最长的顶点编号c，第二行为两点的最短距离d。

测试说明
平台会对你编写的代码进行测试：

测试输入：
4 4
1 2 1
2 3 1
3 4 1
2 4 1
4
4 3
1 2 3
2 3 2
2 4 6
3
0 0

预期输出：
1
2
4
8

class AMGraph:
    def __init__(self):
        self.vexs = []  # 顶点表
        self.arcs = []  # 邻接矩阵
        self.vexnum = 0  # 图的当前点数
        self.arcnum = 0  # 图的当前边数
    def locate_vex(self, name):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum+1):
            if self.vexs[i] == int(name):
                return i
    def create_udn(self):
        # 采用邻接矩阵表示法，创建无向网g
        self.vexnum,self.arcnum=map(int, input().split())
        self.vexs.append(0)
        for i in range(1, self.vexnum+1):
            Vexname = i
            self.vexs.append(Vexname)
        self.arcs = [[32727 for i in range(self.vexnum+1)] for i in range(self.vexnum+1)]  # 初始化邻接矩阵，边的权值均置为极大值32727
        for k in range(0, self.arcnum):  # 构造邻接矩阵
            v1,v2,w = map(int,input().split())
            i = self.locate_vex(v1)
            j = self.locate_vex(v2)  # 确定v1和v2在g中的位置，即顶点数组的下标
            self.arcs[i][j] = w  # 边<v1,v2>的权值为w
            self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w
def shortest_path_max(self, v0):
    # 用Dijkstra算法求有向网g的v0顶点到其余顶点的最短路径
    n = self.vexnum  # n为g中顶点的个数
    d = []  # 用于记录最短路的长度
    s = []  # 标记顶点是否进入s集合
    path = []  # 用于记录最短路顶点的前驱
    s.append('false')  # s初始为空集
    d.append(32727)
    path.append(-1)
    for v in range(1, n+1):  # n个顶点依次初始化
        s.append('false')  # s初始为空集
        d.append(self.arcs[v0][v])  # 将v0到各个终点的最短路径长度初始化为弧上的权值
        if d[v] < 32727:
            path.append(v0)  # 如果v0和v之间有弧，则将v的前驱置为v0
        else:
            path.append(-1)  # 如果v0和v之间无弧，则将v的前驱置为-1
    s[v0] = 'true'  # 将v0加入s
    d[v0] = 0  # 源点到源点的距离为0
        #―初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加到s集―
    for i in range(1, n+1):  # 对其余n-1个顶点，依次进行计算
        min = 32727
        for w in range(1, n+1):
            if s[w] == 'false' and d[w] < min:  # 选择一条当前的最短路径，终点为v
                v = w
                min = d[w]
        s[v] = 'true'  # 将v加入s
        for w in range(1, n+1):  # 更新从v0出发到集合V?s上所有顶点的最短路径长度
            if s[w] == 'false' and d[v] + self.arcs[v][w] < d[w]:
                d[w] = d[v] + self.arcs[v][w]  # 更新D[w]
                path[w] = v  # 更改w的前驱为v
        '''-----------最短路径求解完毕，设距离顶点v0的最短路径长度最大的一个顶点为m--------------'''
    max = 0
    m = 0
    for i in range(1, n+1):
        if max < d[i]:
            m = i
            max=d[i]
    print(self.vexs[m])  # 返回顶点下标
    print(max)

任务描述
设计一个算法，试基于深度优先搜索判断以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。

编程要求
输入
多组数据，每组m+3数据行。第一行有两个数字n和m，代表有n个顶点和m条边。第二行有n个字符，代表n个顶点的编号。第三行到第m+2行每行有两个字符h和k，代表边依附的两个顶点。第m+3行有两个字符vi和vj，代表需要判断的两个顶点。当n和m都等于0时，输入结束。

输出
每组数据输出一行。若存在路径输出“YES”，反之输出“NO”。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
abc
ab
bc
ac
4 2
bcsw
bs
sw
cs
0 0

预期输出：
YES
NO

class ArcNode:  # 边结点
    def __init__(self):
        self.adjvex = 0  # 该边所指向的顶点的位置
        self.nextArc = None  # 指向下一条边的指针
        self.info = None  # 和边相关的信息
class VNode:  # 顶点信息
    def __init__(self, data):
        self.data = data  # 顶点信息
        self.firstarc = None  # 指向第一条依附该顶点的边的指针
class ALGraph:  # 邻接表
    def __init__(self):
        self.vertices = []
        self.vexnum = 0  # 图当前的顶点数
        self.arcnum = 0  # 图当前的边数
    def locate_vex(self, data):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vertices[i].data == data:
                return i
    def create_udg(self):
        # 采用邻接表表示法，创建无向图g
        self.vexnum,self.arcnum=map(int, input().split())
        if self.vexnum == 0 and self.arcnum == 0:
            return
        vdata = input()
        for i in range(0, self.vexnum):  # 输入各点，构造表头结点表
            vertex = VNode(vdata[i])
            self.vertices.append(vertex)
          #  self.vertices[i].data=vdata[i]
        for k in range(0, self.arcnum):  # 输入各边，构造邻接表
            t = input()
            v1 = t[0]
            v2 = t[1]
            i = self.locate_vex(v1)
            j = self.locate_vex(v2)  # 确定v1和v2在self中位置，即顶点在self.vertices中的序号
            p1 = ArcNode()  # 生成一个新的边结点p1
            p1.adjvex = j  # 邻接点序号为j
            p1.nextArc = self.vertices[i].firstarc
            self.vertices[i].firstarc = p1  # 将新结点p1插入顶点v1的边表头部
            p2 = ArcNode()  # 生成另一个对称的新的边结点p2
            p2.adjvex = i  # 邻接点序号为i
            p2.nextArc = self.vertices[j].firstarc
            self.vertices[j].firstarc = p2  # 将新结点p1插入顶点v1的边表头部
def path_dfs(self, i, j):
    # 基于深度优先搜索判断有向图g中顶点i到顶点j是否有路径,是则返回1,否则返回0
    level = 1  # 递归进行的层数
    visited = []  # 访问标志数组，其初值为"false"
    for m in range(0, 100):
        visited.append(False)  # 访问标志数组初始化
    if i == j:
        return 1  # 递归结束的条件，首尾相遇，存在路径
    else:
        visited[i] = True  # 顶点i访问标志为True
        p = self.vertices[i].firstarc
        while p is not None:
            level = level + 1  # 递归层次增1
            k = p.adjvex
            if visited[k] is False and path_dfs(self,k, j):
                return 1  # i下游的顶点到j有路径
            p = p.nextarc
            level = level - 1
    if level == 1:
        return 0  # i到j没有路径

任务描述
一个连通图采用邻接表作为存储结构。设计一个算法，判断无向图中任意给定的两点是否存在一条长度为k的简单路径。

编程要求
输入
多组数据，每组m+3数据行。第一行有两个数字n，m和k，代表有n个顶点，m条边和长度k。第二行有n个字符，代表n个顶点的编号。第三行到第m+2行每行有两个字符h和p，代表边依附的两个顶点。每条边的长度为1。第m+3行有两个字符d和f，代表需要判断的两个字符。

输出
每组数据输出一行。若存在路径输出“YES”，反之输出“NO”。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2 2
abc
ab
bc
ac
4 2 5
bcsw
bs
sw
bw
0 0 0

预期输出：
YES
NO

class ArcNode:  # 边结点
    def __init__(self):
        self.adjvex = 0  # 该边所指向的顶点的位置
        self.nextArc = None  # 指向下一条边的指针
        self.info = None  # 和边相关的信息
class VNode:  # 顶点信息
    def __init__(self, data):
        self.data = data  # 顶点信息
        self.firstarc = None  # 指向第一条依附该顶点的边的指针
class ALGraph:  # 邻接表
    def __init__(self):
        self.vertices = []
        self.vexnum = 0  # 图当前的顶点数
        self.arcnum = 0  # 图当前的边数
    def locate_vex(self, data):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vertices[i].data == data:
                return i
    def create_udg(self,m,n,k):
        # 采用邻接表表示法，创建无向图g
        self.vexnum=m
        self.arcnum=n
        if self.vexnum == 0 and self.arcnum == 0 and k==0:
            return
        vdata = input()
        for i in range(0, self.vexnum):  # 输入各点，构造表头结点表
            vertex = VNode(vdata[i])
            self.vertices.append(vertex)
        for k in range(0, self.arcnum):  # 输入各边，构造邻接表
            t = input()
            v1 = t[0]
            v2 = t[1]
            i = self.locate_vex(v1)
            j = self.locate_vex(v2)  # 确定v1和v2在self中位置，即顶点在self.vertices中的序号
            p1 = ArcNode()  # 生成一个新的边结点p1
            p1.adjvex = j  # 邻接点序号为j
            p1.nextArc = self.vertices[i].firstarc
            self.vertices[i].firstarc = p1  # 将新结点p1插入顶点v1的边表头部
            p2 = ArcNode()  # 生成另一个对称的新的边结点p2
            p2.adjvex = i  # 邻接点序号为i
            p2.nextArc = self.vertices[j].firstarc
            self.vertices[j].firstarc = p2  # 将新结点p1插入顶点v1的边表头部
def path_lenk(self, i, j, k):
    # 判断邻接表方式存储的有向图g的顶点i到j是否存在长度为k的简单路径
    visited = []  # 访问标志数组，其初值为"False"
    for m in range(0, 100):
        visited.append(False)  # 访问标志数组初始化
    if i == j and k == 0:
        return True  # 找到了一条路径,且长度符合要求
    else:
        if k > 0:
            visited[i] = True
            p = self.vertices[i].firstarc  # 从结点i开始遍历，p为i的边链表的第一个边结点
            while p is not None:
                v = p.adjvex
                if not visited[v]:  # v未被访问过
                    if path_lenk(self,v, j, k - 1) != 0:
                        return 1  # 递归继续判断l到j，且剩余路径长度减1
                p = p.nextArc
            visited[i] = False  # 允许曾经被访问过的结点出现在另一条路径中
    return False  # 没找到

任务描述
给定一个无向图，在此无向图中删除一个顶点。

输出
每组数据输出n-1行。为删除顶点后的邻接矩阵。每两个数字之间用空格隔开。

测试说明
平台会对你编写的代码进行测试：

测试输入：
3 2
1 2
2 3
1
2 1
1 2
2
0 0

预期输出：
0 2 3
2 0 1
3 1 0
0 1
1 0

INF = 0x3f3f3f3f
class AMGraph:
    def __init__(self):
        self.vexs = []  # 顶点表
        self.arcs = []  # 邻接矩阵
        self.vexnum = 0  # 图的当前点数
        self.arcnum = 0  # 图的当前边数
    def locate_vex(self, name):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum+1):
            if self.vexs[i] == name:
                return i
        return -1
    def create_udn(self):
        # 采用邻接矩阵表示法，创建无向网g
        self.vexnum,self.arcnum=map(int, input().split())
        for i in range(0, self.vexnum+1):
            vex_data = i
            self.vexs.append(vex_data)
        self.arcs = [[0 for i in range(100)] for i in range(100)]  # 初始化邻接矩阵，边的权值均置为极大值INF
        for k in range(0, self.arcnum):  # 构造邻接矩阵
            v1,v2=map(int ,input().split())
            w = 1  # 输入一条边依附的顶点及权值
            i = self.locate_vex(int(v1))-1
            j = self.locate_vex(int(v2))-1 # 确定v1和v2在g中的位置，即顶点数组的下标
            self.arcs[i][j] = w  # 边<v1,v2>的权值为w
            self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w
    def show_graph(self):
        for i in range(0, self.vexnum+1):
             if i != self.vexnum :
                  print(self.vexs[i], end=" ")
             else:
                  print(self.vexs[i], end="\n")
        for i in range(0, self.vexnum):
            print(self.vexs[i+1], end=" ")
            for j in range(0, self.vexnum):
               if j != self.vexnum - 1:
                   print(self.arcs[i][j], end=" ")
               else:
                   print(self.arcs[i][j], end="\n")
        return 'OK'
def delete_vex(self, v):
    # 在以邻接矩阵形式存储的无向图g上删除顶点v
    n = self.vexnum
    f = self.locate_vex(int(v))
    for i in range(f-1, n-1):        #从目标顶点所在行开始，用下一行的边的权值逐行覆盖上一行边的权值
        for j in range(0, n):
            self.arcs[i][j]=self.arcs[i+1][j];
    self.vexnum=self.vexnum-1
    for i in range(0, n):             #从目标顶点所在列开始，用后一列的边的权值逐列覆盖前一列边的权值
        for j in range(f-1, n):
            self.arcs[i][j]=self.arcs[i][j+1]
    for i in range(f, self.vexnum+1):           #更新顶点表
         self.vexs[i]=self.vexs[i+1]
    return 'OK'

作者：huangqijun679