蟻本をpythonで: Sec. 2-5 グラフ

page93: 二部グラフ判定

from Graph import join_dic  # 中身は下準備の記事参照
from Graph import d_to_ud  # 中身は下準備の記事参照

#############　有向グラフを作る ###########
N = int(input())
graph = {}
while 1:
    edge = input()
    if edge == "":
        break

    edge = list(map(int, edge.split()))
    dic = {edge[0]: edge[1]}
    graph = join_dic(graph, dic)
##########################################

graph = d_to_ud(graph)   ###再帰で処理したいので、無向グラフに

for i in graph:
    if isinstance(graph[i], list):
        continue
    else:
        graph[i] = [graph[i]]   #### for i in graph[hoge]で処理を統一できるように, 

# 追記) if not isinstance(graph[i],list) とすればよかった。

color = (N) * [0]

def coloring(start, col):  ## node start が属する連結成分を塗れるか

    color[start] = col

    for i in graph[start]:
        if color[i] == col:  ##隣接サイトが同じ色だったらアウト
            return False
        if color[i] == 0 and (not coloring(i, -col)):　 ##隣接サイトが無色だったらそこからstartと逆の色で塗り始める
            return False

    return True


def solve():
    for i in graph:
        if color[i] == 0:
            if not coloring(i, 1):    ## iからスタートしてその連結成分を塗れるか
                print("No")
                return 0

    print("Yes")
    return 0


solve()

入力:

4  
0 1
1 2
2 3
0 3

出力:

Yes

入力:

3
0 1
1 2
2 0

出力:

No

グラフが連結とは限らないので全てのnodeについて見ていく必要がある。

page95: ベルマンフォード法

入力:

3

0 1 1
1 2 1
0 2 3

0

2

出力:

2

import mygraph

print("number of nodes")
N = int(input())

print("input graph")
graph = mygraph.WeightedGraph()

while 1:

    inputline = input()

    if inputline == "":
        break

    inputline = list(map(int, inputline.split()))

    graph.join(inputline[0], inputline[1], inputline[2])

graph = graph.undirected()


for node in graph:
    if not isinstance(graph[node][0], list):
        graph[node] = [graph[node]]

print("Start?")
startpos = int(input())
print("Goal?")
goalpos = int(input())


dp = N * [float("INF")]


while 1:

    update = False

    dp[startpos] = 0

    for from_node in graph:

        neighbors = graph[from_node]

        for [to_node, weight] in neighbors:

            if dp[from_node] != float("INF") and dp[to_node] > dp[from_node] + weight:

                dp[to_node] = dp[from_node] + weight

                update = True

    if not update:
        break

print(dp[goalpos])

mygraph.py は下準備の記事のコメントで@sishiracamusさんに書いて頂いたクラス化したもの。