สร้างกราฟด้วย Dictionary ใน Python

กราฟสามารถนำไปใช้ด้วย Dictionary ใน Python ใน dictionary แต่ละ key จะเป็น vertices และเป็น value จะเก็บลิสต์ของ vertices ที่เชื่อมต่อ โครงสร้างทั้งหมดจะคล้ายกับ Adjacency list ของกราฟ G(V, E)

เราสามารถใช้ dictionary object พื้นฐานได้ แต่เราใช้ defaultdict ซึ่งมีคุณสมบัติเพิ่มเติม มี instance variable ที่เขียนได้เพิ่มเติมหนึ่งตัว

เราให้ไฟล์ข้อความที่มีจำนวน vertices, จำนวน edges, ชื่อ vertices และลิสต์ของ edges สำหรับ undirected graph เราให้สอง edges เช่น (u,v) และ (v,u)

เราใช้กราฟนี้ในตัวอย่าง:

ไฟล์สำหรับกราฟเป็นดังนี้:

Graph_Input.txt

6 8
A|B|C|D|E|F
A,B
B,A
A,C
C,A
B,D
D,B
B,E
E,B
C,E
E,C
D,E
E,D
D,F
F,D
E,F
F,E

ก่อนอื่น เราเอาชื่อ vertices แล้วอ่าน edges เพื่อใส่ในลิสต์

ตัวอย่างโค้ด

from collections import defaultdict

def create_graph(filename):
    graph = defaultdict(list)
    with open(filename, 'r') as graph_file:
        vertex = int(graph_file.readline())
        edges = int(graph_file.readline())
        vert_Names = graph_file.readline()
        vert_Names = vert_Names.rstrip('\n')
        nodes = vert_Names.split('|')
        for node in nodes:
            graph[node] = []
        for line in graph_file:
            line = line.rstrip('\n')
            edge = line.split(',')
            graph[edge[0]].append(edge[1])
    return graph

my_graph = create_graph('Graph_Input.txt')
for node in my_graph.keys():
    print(node + ': ' + str(my_graph[node]))

ผลลัพธ์

A: ['B', 'C']
B: ['A', 'D', 'E']
C: ['A', 'E']
D: ['B', 'E', 'F']
E: ['B', 'C', 'D', 'F']
F: ['D', 'E']

ตอนนี้เราจะดูการดำเนินการพื้นฐานบนกราฟ G(V,E) ก่อนอื่นเราจะดูวิธีหา path จาก source vertex ไป destination vertex โค้ดที่ให้เป็นส่วนหนึ่งของการดำเนินการนี้ เพื่อรัน ต้องสร้างกราฟด้วยวิธีก่อนหน้า

ตัวอย่างโค้ด

# ฟังก์ชันหา path จาก source ไป destination
def get_path(graph, src, dest, path=[]):
    path = path + [src]
    if src == dest:
        return path
    for vertex in graph[src]:
        if vertex not in path:
            path_new = get_path(graph, vertex, dest, path)
            if path_new:
                return path_new
    return None

my_graph = create_graph('Graph_Input.txt')
path = get_path(my_graph, 'A', 'C')
print('Path From Node A to C: ' + str(path))

ผลลัพธ์

Path From Node A to C: ['A', 'B', 'D', 'E', 'C']

ตอนนี้เราจะดูวิธีหา all possible paths จาก Source Vertex ไป Destination Vertex โค้ดที่ให้เป็นส่วนหนึ่งของการดำเนินการนี้ เพื่อรัน ต้องสร้างกราฟด้วยวิธีก่อนหน้า

ตัวอย่างโค้ด

# ฟังก์ชันหา all paths จาก source ไป destination
def get_all_path(graph, src, dest, path=[]):
    path = path + [src]
    if src == dest:
        return [path]
    paths = []
    new_path_list = []
    for vertex in graph[src]:
        if vertex not in path:
            new_path_list = get_all_path(graph, vertex, dest, path)
            for new_path in new_path_list:
                paths.append(new_path)
    return paths

my_graph = create_graph('Graph_Input.txt')
paths = get_all_path(my_graph, 'A', 'C')
print('All Paths From Node A to C: ')
for path in paths:
    print(path)

ผลลัพธ์

All Paths From Node A to C:
['A', 'B', 'D', 'E', 'C']
['A', 'B', 'D', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'E', 'C']
['A', 'C']

สุดท้าย เราจะดูวิธีหา shortest path จาก source ไป destination vertex โค้ดที่ให้เป็นส่วนหนึ่งของการดำเนินการนี้ เพื่อรัน ต้องสร้างกราฟด้วยวิธีก่อนหน้า

ตัวอย่างโค้ด

# ฟังก์ชันหา shortest path จาก source ไป destination
def get_shortest_path(graph, src, dest, path=[]):
    path = path + [src]
    if src == dest:
        return path
    short = None
    for vertex in graph[src]:
        if vertex not in path:
            new_path_list = get_shortest_path(graph, vertex, dest, path)
            if new_path_list:
                if not short or len(new_path_list) < len(short):
                    short = new_path_list
    return short

my_graph = create_graph('Graph_Input.txt')
path = get_shortest_path(my_graph, 'A', 'C')
print('Shortest Paths From Node A to C: ' + str(path))

ผลลัพธ์

Shortest Paths From Node A to C: ['A', 'C']