U E D R , A S I H C RSS

자료구족발보쌈/1124

그래프를 들어가기 시작하였습니다.


1. 참여자 명단


함장 장용운 11학번 출석
선원 천준현 15학번 고행
박인서 출석
이원준 출석
남헌 취침

2. 수업

2.1. 진행

1. 장소 : 6층 학회실
2. 시간 : 15시 ~ 17시

2.2. 내용

수심 10540m. 그래프갑자기 후욱 내려감
  • 그래프 구현(인접 리스트, 인접 행렬)

3. 코드

3.1. 예제1


4. 숙제

1. 고통받기
2. 고통받기
3. 고통받기




5. 숙제 제출

5.1. 천준현


5.2. 박인서

  • Minimum Spanning Tree
    • 입력 예

1 2 2
1 3 2
2 4 4
3 4 1
2 7 1
3 7 5
3 6 2
6 7 4
3 5 3
5 6 3
  • 출력 예 : 11
  • 소스

#include <stdio.h>
#define LEN 11

int a[LEN][3],ver[LEN];

int oper(int a,int b)
{
	if(a==0 && b==1) return 1;
	if(a==1 && b==0) return 1;
	return 0;
}

int main()
{
	int i,min[3]={0,0,100},res=0;
	for(i=0;i<10;i++) scanf("%d %d %d",&a[i][0],&a[i][1],&a[i][2]);
	ver[1]=1;
	while(1)
	{
		min[2]=100;
		for(i=0;i<10;i++)
		{
			if(oper(ver[a[i][0]], ver[a[i][1]]) && a[i][2]<min[2]) min[0]=a[i][0],min[1]=a[i][1],min[2]=a[i][2];
		}
		if(min[2]==100) break;
		ver[min[0]]=1,ver[min[1]]=1;
		res+=min[2];
	}
	printf("%d",res);
	return 0;
}

5.3. 이원준


#include<stdio.h>

void MST(int S[], int E[], int N[]){
	int temp[7];
	int ntemp[6] = { 0 };
	int i, j, k, m;
	int mini = 0;
	int mnum;
	int flag = 0;
	int f = 0;
	temp[0] = 5;
	for (i = 0; i < 7; i++){
		mini = 0;
		for (j = 0; j < 10; j++){
			
			for (k = 0; k < i; k++){

				if (S[j] == temp[k]){
					for (m = 0; m < i; m++){
						if (E[j] == temp[m]){
							flag = 1;
							break;
						}
					}
					if (flag == 0){
						if (mini == 0){
							temp[i] = E[j];
							ntemp[i-1] = j;
							mini = N[j];
						}
						else if (mini > N[j]){
							temp[i] = E[j];
							ntemp[i-1] = j;
							mini = N[j];
						}
					}
					flag = 0;

				}

				if (E[j] == temp[k]){
					for (m = 0; m < i; m++){
						if (S[j] == temp[m]){
							flag = 1;
							break;
						}
					}
					if (flag == 0){
						if (mini == 0){
							temp[i] = S[j];
							ntemp[i-1] = j;
							mini = N[j];
						}
						else if (mini > N[j]){
							temp[i] = S[j];
							ntemp[i-1] = j;
							mini = N[j];
						}
					}
					flag = 0;
				}
			}

		}
	}
	k = 1;
	for (i = 0; i < 6; i++){
		f += N[ntemp[i]];
	}
	printf("%d", f);
}
	



void main(){
	int S[10];
	int E[10];
	int N[10];
	S[0] = 1;
	E[0] = 3;
	N[0] = 2;

	S[1] = 1;
	E[1] = 2;
	N[1] = 2;

	S[2] = 2;
	E[2] = 4;
	N[2] = 4;

	S[3] = 2;
	E[3] = 7;
	N[3] = 6;

	S[4] = 3;
	E[4] = 4;
	N[4] = 1;

	S[5] = 3;
	E[5] = 7;
	N[5] = 7;

	S[6] = 3;
	E[6] = 5;
	N[6] = 3;

	S[7] = 3;
	E[7] = 6;
	N[7] = 2;

	S[8] = 5;
	E[8] = 6;
	N[8] = 3;

	S[9] = 6;
	E[9] = 7;
	N[9] = 8;


	MST(S, E, N);



}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2015-11-24 08:16:57
Processing time 0.0955 sec