Cho danh sách kề Adj của đồ thị G. Viết hàm GraphEdge(Adj) trả lại danh sách E các cạnh của đồ thị G. Viết chương trình cho hai trường hợp riêng biệt, G là đồ thị vô hướng và G là đồ thị có hướng.

Để viết hàm GraphEdge(Adj) trả về danh sách các cạnh của đồ thị từ danh sách kề Adj, chúng ta cần xác định cách thức biểu diễn cạnh từ danh sách kề. Trong trường hợp đồ thị vô hướng, mỗi cạnh sẽ được biểu diễn một lần. Trong trường hợp đồ thị có hướng, mỗi cạnh sẽ được biểu diễn hai lần (một lần cho mỗi hướng).

Dưới đây là cách triển khai hàm này cho cả hai trường hợp:

• Trường hợp đồ thị vô hướng:

def GraphEdgeUndirected(Adj):

   edges = []

    for i in range(len(Adj)):

       for j in Adj[i]:

           if j > i:  # Chỉ thêm cạnh một lần, tránh trùng lặp

               edges.append((i, j))

   return edges

# Sử dụng:

Adj_undirected = [

    [1, 2],

    [0, 3],

    [0, 3],

    [1, 2]

]

print(GraphEdgeUndirected(Adj_undirected))

• Trường hợp đồ thị có hướng:

def GraphEdgeDirected(Adj):

   edges = []

    for i in range(len(Adj)):

       for j in Adj[i]:

           edges.append((i, j))

   return edges

# Sử dụng:

Adj_directed = [

    [1, 2],

    [3],

    [3],

    []

]

print(GraphEdgeDirected(Adj_directed))

Trong cả hai trường hợp, chúng ta duyệt qua mỗi đỉnh trong danh sách kề Adj và tạo các cạnh tương ứng dựa trên thông tin trong danh sách kề. Trong trường hợp đồ thị vô hướng, chúng ta chỉ thêm cạnh một lần (đảm bảo tránh trùng lặp). Trong trường hợp đồ thị có hướng, chúng ta thêm cạnh theo cách thông thường. Cuối cùng, chúng ta trả về danh sách các cạnh đã tạo.