무방 향도 의 연통 성 판단

무방 향도 의 연결 성에 대한 판단 에 있어 서 우 리 는 읽 은 변 대 를 통 해 인접 행렬 을 얻어 낼 수 있다. 그리고 Warshall 알고리즘 을 사용 하여 행렬 에 도달 할 수 있다. 그러면 그림 의 연결 성 을 간단하게 판단 할 수 있다. 모든 점 간 에 서로 도달 할 수 있다 면 그 그림 은 연결 되 고 그렇지 않 으 면 연결 되 지 않 는 다.
        그러나 본 고 에서 소개 하고 자 하 는 것 은 이 방법 이 아니 라 유 니 온 - find 알고리즘 으로 그림 의 연관 성 을 판단 하 겠 습 니 다.이 알고리즘 의 수학 기초 사상 은:
우 리 는 읽 은 변 대 에 따라 집합 을 구분 하고 읽 은 변 대 증명 이 서로 연결 되 어 있다 는 것 을 증명 한다. 그러면 우 리 는 하나의 집합 으로 나 눈 다음 에 새로운 변 대 를 읽 으 면 새로운 집합 으로 나 뉜 다. 일단 읽 은 변 대 (두 정점) 가 모두 같은 집합 에 나타 나 면 서로 연결 되 어 있다 는 것 을 증명 한다. 만약 에 읽 은 변 대 (두 정점) 가 서로 연결 되 어 있다 면두 개의 정점 은 두 개의 집합 에 나타 나 는 것 이다. 그러면 이 두 집합 은 적어도 이 변 을 통 해 연결 할 수 있다 는 것 을 의미한다. 그러면 집합 을 통 해 합병 할 수 있다.순서대로 유추 하 다.
그러면 남 은 것 은 데이터 구조의 선택 이다. 우 리 는 매번 가장자리 의 정점 을 읽 은 다음 에 십자 링크 를 설정 할 수 있다. head - > [0] - > [9] - > [7]              |          |              \|/        \|/             [5]       [8]              |             \|/            [1] 이 링크 의 작업 은 우리 가 읽 으 면서 만 드 는 방법 에 따라 읽 는 사 이 드 입 니 다. 읽 을 때마다 우 리 는 연결 로 간주 합 니 다. 그러면 하나의 집합 (세로 로 된 링크 로 표시) 을 넣 은 다음 에 새로운 정점 을 읽 을 때마다 링크 를 비교 합 니 다. 예 를 들 어 과 정점 이 각각 두 세로 로 된 링크 에 나타 나 면 두 개의 링크 를 합 친 것 입 니 다.링크 에 하나만 나타 나 면 다른 점 은 세로 로 되 어 있 는 링크 를 넣 습 니 다.
위의 사고방식 은 정확 하지만 데이터 구조 에 매우 큰 최적화 공간 이 존재 한다. 우 리 는 하나의 배열 로 이 십자 체인 표를 대체 하여 배열 이 정점 에 대응 하도록 할 수 있다. 배열 의 수 는 바로 정점 의 식별 자 이 고 연 결 된 정점 은 똑 같은 식별 자 를 기록 할 수 있다.그리고 현재 읽 고 있 는 두 개의 연결 분량 이 연결 되 어 있 는 상황 을 만나면 배열 을 업데이트 하면 됩 니 다.
우 리 는 위의 배열 의 상황 에서 계속 최적화 할 수 있다. 우 리 는 숲 의 방법 으로 연결 분량 을 기록 할 수 있다. 연 결 된 것 은 바로 나무 이다. 전체 그림 은 하나의 숲 을 구성 할 수 있다. 물론 우 리 는 배열 로 숲 을 모 의 할 수 있다. 그러면 모든 배열 의 공간 은 그의 아버지 노드 의 번 호 를 기록 하고 뿌리 노드 는 자신의 번 호 를 기록 하 는 것 이다.이런 점 은 두 개의 연결 분량 이 연 결 될 때 우 리 는 배열 의 이 연결 분량 의 모든 수 를 새로 고 칠 필요 가 없다 는 것 이다.

#include 
#include 

typedef struct list{
	int number;           //    
	struct list *next;
}ListNode;

struct adjNode{
	int VMess;            //    
	ListNode *head;       //    
};

//     
typedef struct A{
	int V;                //    
	int E;                //   
    struct adjNode *graphMess;  //    
}Graph;

void addEdge(Graph graph,int V1,int V2);

//     (     )
void Add(ListNode **head,int num)
{
	if(!(*head))
	{
		(*head) = (ListNode *)malloc(sizeof(ListNode));
		(*head)->number = num;
		(*head)->next = NULL;
	}
	else
	{
		ListNode *temp = *head;
		while(temp->next)
			temp = temp->next;
		ListNode *T = (ListNode *)malloc(sizeof(ListNode));
		T->number = num;
		T->next = NULL;
		temp->next = T;
	}
}

//      
void Delete()
{

}

//    ：
//   
void InitGraph(Graph *graph,int VSize)
{
	graph->V = VSize;
	graph->E = 0;
	graph->graphMess = (struct adjNode *)malloc(sizeof(struct adjNode)*VSize);
	// 0      
	for(int i = 0;i < VSize;i++)
	{
		graph->graphMess[i].VMess = i;
		//         
		graph->graphMess[i].head = NULL;
	}
}

//    
Graph CreateGraph()
{
	Graph graph;
	int VSize;
	scanf("%d",&VSize);
	InitGraph(&graph,VSize);
	//     
	scanf("%d",&graph.E);
	int V1,V2;
	for(int i = 0;i < graph.E;i++)
	{
		scanf("%d%d",&V1,&V2);
		addEdge(graph,V1,V2);
	}
	return graph;
}


//   ,        
void addEdge(Graph graph,int V1,int V2)
{
	Add(&(graph.graphMess[V1].head),V2);
	Add(&(graph.graphMess[V2].head),V1);
	graph.E++;
}

//    
void Display(Graph graph)
{
	ListNode *temp;
	for(int i = 0;i < graph.V;i++)
	{
		temp = graph.graphMess[i].head;
		printf("%d:  ",i);
		while(temp->next)
		{
			printf("%d-->",temp->number);
			temp = temp->next;
		}
		printf("%d
",temp->number);
	}//end of for
}


void main()
{
	Graph graph = CreateGraph();
	Display(graph);
}