数据结构第六章关于图的相关作业（一）函数的接口定义：裁判测试程序样例：输入样例：

65 阅读 0 评论 43 点赞

我是靠谱客的博主超帅火，最近开发中收集的这篇文章主要介绍数据结构第六章关于图的相关作业（一）函数的接口定义：裁判测试程序样例：输入样例：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

以邻接矩阵作为存储结构，实现以下图的基本操作：
① 增加⼀个新顶点 v，insert_vex()；
② 删除顶点 v 及其相关的边，delete_vex()；
③ 增加⼀条边<v, w>，insert_arc()；
④ 删除⼀条边<v, w>，delete_arc()。

函数的接口定义：

在这里描述函数接口。例如：

def insert_vex(self, v):

def delete_vex(self, v):

def insert_arc(self, v, w):

def delete_arc(self, v, w):

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如：
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):
if self.vexs[i] == name:
return i

def create_udn(self):
# 采用邻接矩阵表示法，创建无向网
self.vexnum = int(input()) # 输入总顶点数
self.arcnum = int(input()) # 输入总边数
for i in range(0, self.vexnum):
vexname = input()
self.vexs.append(vexname)
self.arcs = [[INF for i in range(self.vexnum)] for i in range(self.vexnum)] # 初始化邻接矩阵，边的权值均置为无穷大
for k in range(0, self.arcnum): # 构造邻接矩阵
v1 = input()
v2 = input()
w = int(input()) # 输入一条边依附的顶点及权值
i = self.locate_vex(v1)
j = self.locate_vex(v2) # 确定v1和v2在图中的位置，即顶点数组的下标
self.arcs[i][j] = w # 边<v1,v2>的权值为w
self.arcs[j][i] = self.arcs[i][j] # 置<v1,v2>的对称边<v2,v1>的权值为w

##请在这里填写答案

def show(self):
for i in range(0, self.vexnum):
for j in range(0, self.vexnum):
if j != self.vexnum-1:
if(self.arcs[i][j] < INF):
print(self.arcs[i][j], end="t")
else:
print("∞t", end="")
else:
if (self.arcs[i][j] < INF):
print(self.arcs[i][j])
else:
print("∞")

if __name__ == '__main__':
g = AMGraph()
g.create_udn()
print(str(g.vexnum)+'个顶点'+str(g.arcnum)+'条边的初始图')
g.show()
g.delete_vex('E')
print('删除顶点E')
g.show()
g.insert_vex('E')
print('增加顶点E')
g.show()
print('增加边AC')
g.insert_arc('A','C')
g.show()
print('删除边AC')
g.delete_arc('A','C')
g.show()

输入样例：

在这里给出一组输入。例如：

5
4
A
B
C
D
E
A
B
1
B
C
2
C
D
3
D
E
4

输出样例：

在这里给出相应的输出。例如：

5个顶点4条边的初始图
∞   1   ∞   ∞   ∞
1   ∞   2   ∞   ∞
∞   2   ∞   3   ∞
∞   ∞   3   ∞   4
∞   ∞   ∞   4   ∞
删除顶点E
∞   1   ∞   ∞
1   ∞   2   ∞
∞   2   ∞   3
∞   ∞   3   ∞
增加顶点E
∞   1   ∞   ∞   ∞
1   ∞   2   ∞   ∞
∞   2   ∞   3   ∞
∞   ∞   3   ∞   ∞
∞   ∞   ∞   ∞   ∞
增加边AC
∞   1   1   ∞   ∞
1   ∞   2   ∞   ∞
1   2   ∞   3   ∞
∞   ∞   3   ∞   ∞
∞   ∞   ∞   ∞   ∞
删除边AC
∞   1   ∞   ∞   ∞
1   ∞   2   ∞   ∞
∞   2   ∞   3   ∞
∞   ∞   3   ∞   ∞
∞   ∞   ∞   ∞   ∞

上面的是原题
先给大家看看我第一遍写的答案吧，但是还有bug（结果只能得出实例案例的答案，应该是没有考虑到特殊情况。

    def insert_vex(self, v):
        self.vexs.append(v)
        inf = [INF for i in range(self.vexnum+1)]
        if self.vexnum == len(self.arcs):
            for i in range(self.vexnum):
                 self.arcs[i].append(INF)
            self.arcs.append(inf)
        else:
            for i in range(self.vexnum):
                self.arcs[i][self.vexnum] = INF
            self.arcs[self.vexnum] = inf
        self.vexnum += 1

    def delete_vex(self, v):
        local = self.vexs.index(v)
        for k in range(self.vexnum):
            if self.arcs[local][k] != INF:
                self.arcnum -= 1
        self.vexs.pop(local)
        self.arcs.pop(local)
        self.vexnum -= 1
        for i in range(self.vexnum):
            self.arcs[i].pop(local)

    def insert_arc(self, v, w):
        self.arcnum += 1
        locale_v = self.vexs.index(v)
        locale_w = self.vexs.index(w)
        self.arcs[locale_v][locale_w] = 1
        self.arcs[locale_w][locale_v] = self.arcs[locale_v][locale_w]

    def delete_arc(self, v, w):
        self.arcnum -= 1
        locale_v = self.vexs.index(v)
        locale_w = self.vexs.index(w)
        self.arcs[locale_v][locale_w] = INF
        self.arcs[locale_w][locale_v] = self.arcs[locale_v][locale_w]

我实验了一些我能想到的结果，但是都没有什么问题。希望可以得到大家指点。

过来几天，终于找到了解决方法，如下：

    def delete_vex(self, v):
        local = self.vexs.index(v)
        for k in range(self.vexnum):
            if self.arcs[local][k] != INF:
                self.arcnum -= 1
        #self.vexs.pop(local)
        self.arcs.pop(local)
        self.vexnum -= 1
        for i in range(self.vexnum):
            self.arcs[i].pop(local)

可以看到，其实并没有改动多少，只是在每次删除顶点时，对vexs不做任何处理，就可以正常运行了