// main.c
// yuvuhu
//
// Created by 尘落 on 2021/11/26.
//
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int data;
struct Node* Next;
int flag;
}LNode,*Link_Node;
typedef struct Edge_Node{
Link_Node Node;
struct Edge_Node *next;
int len;
}E_Node,*E_link_Node;
typedef struct Head_Node{
Link_Node L_Node;
E_Node* Edge_Node;
int id;
}H_Node,*Hlink_Node;
typedef struct Chart_Graphy{
Hlink_Node head_Node[100];
int n,e;
}Graphy,*Graph_link;
typedef struct Queue_Node{
Link_Node front;
Link_Node rear;
int Count;
}QNode,*Link_QNode;
Link_QNode init_Queue(){
Link_QNode Q;
Q = (Link_QNode)malloc(sizeof(QNode));
Q->Count = 0;
Q->rear = Q->front = NULL;
return Q;
}
Graph_link Create_UD_Graphy(){
Graph_link A = (Graph_link)malloc(sizeof(Graphy));
E_Node *q;
int m,n,i,f,k;
int c;
printf("请输入顶点数和边数: ");
scanf("%d,%d",&m,&n);
A->n = m;
A->e = n;
printf("请输入顶点:（输入后回车）\n");
for(i = 0;i<m;i++){ //为每个结点分配空间，并数组分别指向对应空间
scanf("%d",&c);
A->head_Node[i] = (Hlink_Node)malloc(sizeof(H_Node));
A->head_Node[i]->L_Node = (Link_Node)malloc(sizeof(LNode));
A->head_Node[i]->L_Node->data=c;
A->head_Node[i]->L_Node->flag=0;
A->head_Node[i]->Edge_Node=NULL;
A->head_Node[i]->id = 0;
}
for(int i=0;i<m;i++){
printf("%d(%d)",A->head_Node[i]->L_Node->data,i+1);
}
c = getchar();
printf("请输入边的信息: \n");
for(k = 0;k<n;k++){
int a,b;
scanf("%d,%d",&a,&b);
for(i = 0;i<m;i++){
if(A->head_Node[i]->L_Node->data==a){
break;
}else if(i == m-1){
printf("没有找到节点1～～～");
exit(1);
}
}
for(f = 0;f<m;f++){
if(A->head_Node[f]->L_Node->data==b){
break;
}else if(f == m-1){
printf("没有找到节点2～～～");
}
}
q = (E_Node*)malloc(sizeof(E_Node));
q->Node = A->head_Node[i]->L_Node;
q->next = A->head_Node[f]->Edge_Node;
A->head_Node[f]->Edge_Node = q;
q = (E_Node*)malloc(sizeof(E_Node));
q->Node = A->head_Node[f]->L_Node;
q->next = A->head_Node[i]->Edge_Node;
A->head_Node[i]->Edge_Node = q;
}
return A;
}
void flag_1(Graph_link G){
void Print_Graphy(Graph_link );
int i;
for(i=0;i<G->n;i++){
G->head_Node[i]->L_Node->flag = 1;
printf("%d的flag已被设置为1\n",i+1);
}
Print_Graphy(G);
}
void Print_Graphy(Graph_link G){
int i;
E_Node *p;
for(i = 0;i<G->n;i++){
printf("[%d]-|%d|-(%d)-----",G->head_Node[i]->L_Node->data,G->head_Node[i]->id,G->head_Node[i]->L_Node->flag);
p=G->head_Node[i]->Edge_Node;
while(p){
printf("%d(%d)----",p->Node->data,p->Node->flag);
p = p->next;
}
printf("\n");
}
}
void ENQUEU(Link_QNode Q,Link_Node S){
S->Next = NULL;
Link_Node H;
H = S;
if(!Q->front){
Q->front = Q->rear = S;
Q->Count++;
}else{
Q->rear->Next = S;
Q->rear =S;
Q->Count++;
}
}
Link_Node DeQUEU(Link_QNode Q){
Link_Node p;
p = Q->front;
Q->front = Q->front->Next;
Q->Count--;
p->Next = NULL;
return p;
}
//广度优先搜索
void BFS(Graphy *A,int t){
Link_QNode Q;
Link_Node P;
E_Node *q;
int i ;
Q = init_Queue();
for(i = 0;i<A->n;i++){
if(A->head_Node[i]->L_Node->data==t){
break;
}
}
P = A->head_Node[i]->L_Node;
ENQUEU(Q, P);
while(Q->Count){
P = DeQUEU(Q);
for(i = 0;i<A->n;i++){
if(A->head_Node[i]->L_Node->data==P->data){
break;
}
}
q = A->head_Node[i]->Edge_Node;
while(q){
if(q->Node->flag==0){
int h;
for(h = 0;h<A->n;h++){
if(A->head_Node[h]->L_Node->data == q->Node->data){
A->head_Node[h]->L_Node->flag=1;
break;
}
}
ENQUEU(Q,q->Node);
}
q = q->next;
}
printf("[%d]-------",P->data);
P->flag =1;
}
printf("\n");
}
void DFS(Graph_link A,int n){
int i,h;
Link_Node u;
void DFS_VISIT(Graph_link ,Link_Node );
for(i = 0;i<A->n;i++){
A->head_Node[i]->L_Node->flag = 0;
}
for(i = 0;i<A->n;i++){
if(A->head_Node[i]->L_Node->data == n){
u = A->head_Node[i]->L_Node;
if(A->head_Node[i]->L_Node->flag == 0){
DFS_VISIT(A,u);
}
}
}
for(h = 0;h<A->n;h++){
if(h!=i){
u = A->head_Node[h]->L_Node;
if(A->head_Node[h]->L_Node->flag == 0){
DFS_VISIT(A,u);
}
}
}
}
void DFS_VISIT(Graph_link G,Link_Node u){
int i;
E_link_Node p;
Hlink_Node q;
q = (H_Node*)malloc(sizeof(H_Node));
printf("[%d]-----",u->data);
u->flag = 1;
for(i = 0;i<G->n;i++){
if(G->head_Node[i]->L_Node->data == u->data){
q =G->head_Node[i];
break;
}
}
p = q->Edge_Node;
while(p){
if(p->Node->flag == 0){
DFS_VISIT(G,p->Node);
}
p = p->next;
}
}
Graph_link Create_Di_Graphy(){
Graph_link A = (Graph_link)malloc(sizeof(Graphy));
E_Node *q;
int m,n,i,f,k;
int c;
printf("请输入有向图的顶点数和边数: ");
scanf("%d,%d",&m,&n);
A->n = m;
A->e = n;
printf("请输入顶点:（输入后回车）\n");
for(i = 0;i<m;i++){ //为每个结点分配空间，并数组分别指向对应空间
scanf("%d",&c);
A->head_Node[i] = (Hlink_Node)malloc(sizeof(H_Node));
A->head_Node[i]->L_Node = (Link_Node)malloc(sizeof(LNode));
A->head_Node[i]->L_Node->data=c;
A->head_Node[i]->L_Node->flag=0;
A->head_Node[i]->Edge_Node=NULL;
A->head_Node[i]->id = 0;
}
for(int i=0;i<m;i++){
printf("%d(%d)",A->head_Node[i]->L_Node->data,i+1);
}
c = getchar();
printf("请输入边的信息: \n");
for(k = 0;k<n;k++){
int a,b;
scanf("%d,%d",&a,&b);
for(i = 0;i<m;i++){
if(A->head_Node[i]->L_Node->data==a){
break;
}else if(i == m-1){
printf("没有找到节点1～～～");
exit(1);
}
}
for(f = 0;f<m;f++){
if(A->head_Node[f]->L_Node->data==b){
break;
}else if(f == m-1){
printf("没有找到节点2～～～");
exit(2);
}
}
q = (E_Node*)malloc(sizeof(E_Node));
q->Node = A->head_Node[f]->L_Node;
q->next = A->head_Node[i]->Edge_Node;
A->head_Node[i]->Edge_Node = q;
A->head_Node[f]->id++;
}
return A;
}
void Topo_Sorting(Graph_link A){
int k = 0,i,j,v,flag[20];
int queue[20];
int front,rear;
E_Node* p;
front=rear=0;
for(i=0;i<A->n;i++){
flag[i] = 0;
}
for(i =0 ;i<A->n;i++){
if(A->head_Node[i]->id ==0 && flag[i] ==0){
queue[rear++] = i;
flag[i] = 1;
}
}
printf("\nAOV网的序列是: \n");
while(front<rear){
v = queue[front++];//出队列
printf("%d",A->head_Node[v]->L_Node->data);
k++;
p = A->head_Node[v]->Edge_Node;
while(p){
j = p->Node->data;
if(--(A->head_Node[j]->id)==0&&flag[j]==0){
queue[rear++] = j;
flag[j] = 1;
}
p = p->next;
}
}
}
void Shortest_path(){
}
int main(){
Graph_link A,A_D;
int n,m;
printf("--------------------无向图--------------\n");
A = Create_UD_Graphy();
printf("请输入广度搜索时开始的顶点值： ");
scanf("%d",&n);
BFS(A,n);
printf("请输入深度搜索时开始的顶点值： ");
scanf("%d",&m);
DFS(A,m);
printf("------------------有向图----------------\n");
A_D =Create_Di_Graphy();
Print_Graphy(A_D);
Topo_Sorting(A_D);
return 0;
}
