Графи

графічне представлення сукупності елементів та зв'язків між ними

графічне представлення сукупності об'єктів

 графічне представлення залежності однієї величини від іншої

графічне представлення зв'язків

 ребрами 

 вказівниками 

 вершинами

шляхом

не мають з’єднань 

представлені на графі

з’єднані ребром 

мають петлю

 граф немає ізольованих вершин

 дві будь-які вершини з’єднані ребрами 

всі вершини мають дуги 

будь-яка пара вершин має тільки одне ребро

кількість вершин і ребр у графі 

кількість ребр, що виходять з вершини графа 

 кількість ребр, що входять у цей шлях 

кількість ребр у графі 

у графі є ребра і дуги 

ребра мають вагу

у графі є дуги 

більше половини ребр мають напрям 

матрицями суміжності 

списками суміжних вершин 

номерами вершин

рисунком

чисел від 0 до 9 

чисел від 1 до 9 

номерів вершин

чисел 0 і 1 

вибирається найближня до неї вершина 

вибираються усі суміжні вершини

вибирається одна суміжна вершина 

вибираються усі суміжні вершини  

 вибирається випадкова вершина 

вибирається найближня до неї вершина 

вибираються всі суміжні з нею вершини  

вибирається одна суміжна вершина 

шлях з мінімальною кількістю вершин і ребр

шлях з мінімальною кількістю ребр

 шлях з мінімальною кількістю вершин 

шлях із мінімальною сумою ваг ребр 

 від першої вершини до останньої 

від кожної вершини до всіх інших 

від одної вершини до заданої

від одної вершини до всіх інших 

A=[[2,5],[2,3],[2,4],[3,5,6],[1,4],[4]]

A=[[2,5],[3],[2,4],[3,5,6],[1,4],[4]]

A=[[2,5],[3],[2,4],[3,5,6],[1,4]]

A=[[2,5],[3],[2,4],[3,5,6],[1,4],[4,1]]

def search(v):

  print(v)

  stan[v]=1

  for ver in g[v]:

    if stan[ver] == -1:

      search(ver)

g = [[4,5], [5], [3,4], [2,4], [0,2,3], [0,1]]

stan = [-1, -1, -1, -1, -1, -1]

for i in range (len(g)):

  if stan[i] == -1:

    search(i)

def search(v):

  vert=[]

  vert.append(v)

  stan[v]=0

  while vert:

    s=vert.pop(0)

    for i in g[s]:

      if stan[i] == -1:

        vert.append(i)

        print(vert)

        stan[i]=stan[s]+1

        print(stan)

g = [[1,3], [0,3,4,5], [4,5], [0,1,5], [1,2], [1,2,3]]

stan = [-1, -1, -1, -1, -1, -1]

for i in range (len(g)):

  if stan[i] == -1:

    search(i)

print(stan)

a=[0,1,3,4,7,9]

m=int(input())

l=1

r=len(a)

if a[0]==m:

print(0)

else:

while l<r-1:

mid=(l+r)//2

if m<a[mid]:

r=mid

else:

l=mid

print(l)

def func(graph,start,p={},u=[]):

  if len(p)==0:

    p[start]=0

  for x in graph[start]:

    if (x not in u and x!=start):

      if(x not in p.keys() or (graph[start][x]+p[start]<p[x])):

        p[x]=graph[start][x]+p[start]

  u.append(start)

  min_v=0

  for x in p:

    if (p[x]<min_v or min_v==0) and x not in u:

      min_x=x

      min_v=p[x]

  if (len(u)<len(graph) and min_x):

    return func(graph,min_x,p,u)

  else:

    return p

N=[

  {1:7,2:9,5:14},

  {0:7,2:10,3:15},

  {0:9,1:10,3:11,5:2},

  {1:15,2:11,4:6},

  {3:6,5:9},

  {0:14,2:2,4:9}

  ]

print (func(N,0))

def search(v):

  print(v)

  stan[v]=1

  for ver in g[v]:

    if stan[ver] == -1:

      search(ver)

g = [[4,5], [5], [3,4], [2,4], [0,2,3], [0,1]]

stan = [-1, -1, -1, -1, -1, -1]

for i in range (len(g)):

  if stan[i] == -1:

    search(i)

def search(v):

  vert=[]

  vert.append(v)

  stan[v]=0

  while vert:

    s=vert.pop(0)

    for i in g[s]:

      if stan[i] == -1:

        vert.append(i)

        print(vert)

        stan[i]=stan[s]+1

        print(stan)

g = [[1,3], [0,3,4,5], [4,5], [0,1,5], [1,2], [1,2,3]]

stan = [-1, -1, -1, -1, -1, -1]

for i in range (len(g)):

  if stan[i] == -1:

    search(i)

print(stan)

a=[0,1,3,4,7,9]

m=int(input())

l=1

r=len(a)

if a[0]==m:

print(0)

else:

while l<r-1:

mid=(l+r)//2

if m<a[mid]:

r=mid

else:

l=mid

print(l)

def func(graph,start,p={},u=[]):

  if len(p)==0:

    p[start]=0

  for x in graph[start]:

    if (x not in u and x!=start):

      if(x not in p.keys() or (graph[start][x]+p[start]<p[x])):

        p[x]=graph[start][x]+p[start]

  u.append(start)

  min_v=0

  for x in p:

    if (p[x]<min_v or min_v==0) and x not in u:

      min_x=x

      min_v=p[x]

  if (len(u)<len(graph) and min_x):

    return func(graph,min_x,p,u)

  else:

    return p

N=[

  {1:7,2:9,5:14},

  {0:7,2:10,3:15},

  {0:9,1:10,3:11,5:2},

  {1:15,2:11,4:6},

  {3:6,5:9},

  {0:14,2:2,4:9}

  ]

print (func(N,0))

1 2 5 3 4 6

0 1 2 3 1 3

0 1 2 3 1 4

1 2 3 4 6 5

1 2 5 3 4 6

1 2 3 4 5 6

1 2 5 4 6 3

1 2 3 4 6 5

9

8

0

3

0 5 9 7 8

0 5 8 7 8

0 1 2 3 4

0 1 9 8 8

def search(v):

  print(v)

  stan[v]=1

  for ver in g[v]:

    if stan[ver] == -1:

      search(ver)

g = [[4,5], [5], [3,4], [2,4], [0,2,3], [0,1]]

stan = [-1, -1, -1, -1, -1, -1]

for i in range (len(g)):

  if stan[i] == -1:

    search(i)

def search(v):

  vert=[]

  vert.append(v)

  stan[v]=0

  while vert:

    s=vert.pop(0)

    for i in g[s]:

      if stan[i] == -1:

        vert.append(i)

        print(vert)

        stan[i]=stan[s]+1

        print(stan)

g = [[1,3], [0,3,4,5], [4,5], [0,1,5], [1,2], [1,2,3]]

stan = [-1, -1, -1, -1, -1, -1]

for i in range (len(g)):

  if stan[i] == -1:

    search(i)

print(stan)

a=[0,1,3,4,7,9]

m=int(input())

l=1

r=len(a)

if a[0]==m:

print(0)

else:

while l<r-1:

mid=(l+r)//2

if m<a[mid]:

r=mid

else:

l=mid

print(l)

def func(graph,start,p={},u=[]):

  if len(p)==0:

    p[start]=0

  for x in graph[start]:

    if (x not in u and x!=start):

      if(x not in p.keys() or (graph[start][x]+p[start]<p[x])):

        p[x]=graph[start][x]+p[start]

  u.append(start)

  min_v=0

  for x in p:

    if (p[x]<min_v or min_v==0) and x not in u:

      min_x=x

      min_v=p[x]

  if (len(u)<len(graph) and min_x):

    return func(graph,min_x,p,u)

  else:

    return p

N=[

  {1:7,2:9,5:14},

  {0:7,2:10,3:15},

  {0:9,1:10,3:11,5:2},

  {1:15,2:11,4:6},

  {3:6,5:9},

  {0:14,2:2,4:9}

  ]

print (func(N,0))