[자료구조] 인접행렬 기초 정점 연결관계 Python

인접행렬

*간선의 개수는 정점의 개수 제곱과 같거나 작다. 4c2 -> n(n-1)/2   
*모든 정점의 차수의 합은 간선의 2배와 같다.

 

인접행렬에서 자주 나오는 문제

Q1. x는 y와 인접하는가 O(1)

Q2. x와 인접한 리스트를 구하라 


장점 
- 바로 접근해서 확인가능



단점
- 실제 인접한 정점 수와 관계없이 인접한 정점을 찾는데 O(n)이 걸림.     ex) 정점이 5개라면 자신을 제외한 나머지 간선들과의 관계 확인 필요

 

- 간선의 개수와 관계없이 n2개의 칸을 사용해야 함. (n=정점의 개수)

 

 

 

정점과 간선을 입력받고 연결이 되는 정점끼리의 값을 1, 정점이 연결되어 있지 않다면 0으로 표현하는 코드를 작성

 

ex) 정점의 개수 5, 간선의 개수 6

1 2

1 3

1 4

2 4

4 5

3 5

 

 

   1 2 3 4 5

1 0 1 1 1 0    -> 1은 2,3,4와의 간선으로 연결

2 1 0 0 1 0    -> 2는 1과 4와의 간선으로 연결

3 1 0 0 0 1    -> 3은 1과 5와 간선으로 연결

4 1 1 0 0 1    -> 4는 1,2,5와 간선으로 연결 

5 0 0 1 1 0    -> 5는 4와5와 간선으로 연결

 

 

 
lists = []
 
m, e = map(int, input().strip().split())
 
for i in range(m):
    temp = []
    for j in range(m):
        temp.append(0)
    lists.append(temp)
 
for i in range(e):
    a, b = map(int, input().strip().split())
    lists[a - 1][b - 1] = 1
    lists[b - 1][a - 1] = 1
#
for i in range(m):
    for j in range(m):
        print(lists[i][j], end=" ")
    print("")
 
 
a, b = map(int, input("A와 B와 연결이 되는지 확인:").strip().split())
 
if lists[a-1][b-1] and lists[b-1][a-1]:
    print("연결됨")
else:
    print("연결안됨")
 
 
a = int(input("입력 A와 연결된 정점 리스트 확인하기 입력:"))
temp = []
for i in range(len(lists[a-1])):
    if lists[a-1][i] == 1:
        print(i+1, end =" ")