図の相関アルゴリズム
- #ifndef _PIC_H
- #define _PIC_H
-
- #define MAXV 50
-
- typedef int InfoType;
- typedef char ElemType;
- int visited[MAXV];
- //
- typedef struct
- {
- int no; //
- ElemType info; //
- }VertexType; //
-
- typedef struct
- {
- int edge[MAXV][MAXV]; //
- int n,e; // ，
- VertexType vexs[MAXV];
- }MGraph; //
-
- //
- typedef struct ANode //
- {
- int adjvex; //
- struct ANode *nextarc; //
- InfoType info; //
- }ArcNode;
-
- typedef struct Vnode //
- {
- ElemType data; //
- ArcNode *firstarc; //
- }VNode;
-
- typedef VNode *AdjList[MAXV];
- typedef struct //
- {
- AdjList adjlist;
- int n,e;
- }AGraph;
-
- #endif
-
- #include <stdio.h>
- #include "stdlib.h"
- #include "pic.h"
-
- void CreateMat(MGraph *g, int A[][MAXV], int n) //
- {
- int i=0,j=0;
- g->n = n;
- g->e = 0;
-
- for(i=0; i<n; i++)
- for(j=0; j<n; j++)
- {
- g->edge[i][j] = A[i][j];
- if(A[i][j] != 0)
- g->e ++;
- }
- }
-
- void DispMat(MGraph *g) //
- {
- int i,j;
- for(i=0; i<g->n; i++)
- {
- for(j=0; j<g->n; j++)
- {
- printf("%c ",g->edge[i][j]);
- }
- printf("
");
- }
- }
-
- void CreateAdj(AGraph *g, int A[][MAXV], int n) //
- {
- int i=0, j=0;
- ArcNode *p = NULL;
- g = (AGraph *)malloc(sizeof(AGraph));
- g->n = n;
- g->e = 0;
-
- for(i=0; i<n; i++) g->adjlist[i]->firstarc = NULL;
-
- for(i=0; i<n; i++)
- for(j=0; j<n; j++)
- if(A[i][j] != 0)
- {
- p = (ArcNode *)malloc(sizeof(ArcNode));
- p->adjvex = j;
- p->nextarc = g->adjlist[j]->firstarc; //
- g->adjlist[j]->firstarc = p;
- g->e++;
- }
- }
-
- void DispAdj(AGraph *g) //
- {
- int i=0;
- ArcNode *p = NULL;
-
- for(i=0; i<g->n; i++)
- {
- printf("%d ",i);
- p = g->adjlist[i]->firstarc; // p
- while(p != NULL)
- {
- printf("%c ",p->adjvex);
- p = p->nextarc; //
- }
- printf("
");
- }
- }
-
-
-
-
-
-
-
-
- void InDs(AGraph *g) //ru du
- {
- ArcNode *p;
- int A[MAXV],i; // store ru du
-
- for(i=0; i<g->n; i++) A[i] = 0;
-
- for(i=0; i<g->n; i++)
- {
- p = (g->adjlist[i]->firstarc);
- while(p != NULL)
- {
- A[i]++;
- p = p->nextarc;
- }
- }
-
- for(i=0; i<g->n; i++)
- printf("%d ",A[i]);
- }
-
- void OutDs(AGraph *g) //chu du
- {
- int i,n;
- ArcNode *p;
- for(i=0; i<g->n; i++)
- {
- n=0;
- p = g->adjlist[i]->firstarc;
- while(p != NULL)
- {
- n ++;
- p = p->nextarc;
- printf("%d ",n);
- }
- }
- }
-
- void Arc(AGraph *g, int i, int j) //if there is line between i and j
- {
- ArcNode *p = NULL;
- p = g->adjlist[i]->firstarc;
-
- while(p->adjvex != j && p != NULL)
- p = p->nextarc;
- if(p == NULL) printf(" ");
- else printf(" ");
- }
-
-
-
-
- void InDs1(MGraph *g) // ， j， j
- {
- int i,j,n;
-
- for(j=0; j<g->n; j++)
- {
- n = 0;
- for(i=0; i<g->n; i++)
- {
- if(g->edge[i][j] != 0)
- n++;
- }
- printf("%d ",n);
- }
- }
-
- void OutDs2(MGraph *g) //
- {
- int i=0,j=0,n=0;
-
- for(i=0; i<g->n; i++)
- { n=0;
- for(j=0; j<g->n; j++)
- if(g->edge[i][j] != 0)
- n++;
- printf("%d ",n);
- }
- }
-
- void ListToMat(AGraph *g1, MGraph *g2) //
- {
- int i=0, j=0;
- ArcNode *p = NULL;
- g2 = (MGraph *)malloc(sizeof(MGraph));
- g2->n = g1->n;
-
- for(i=0; i<g1->n; i++)
- for(j=0; j<g1->n; j++)
- g2->edge[i][j] = 0;
-
- for(i=0; i<g1->n; i++)
- {
- p = g1->adjlist[i]->firstarc;
- while(p != NULL)
- {
- g2->edge[i][p->adjvex] = 1; // p->adjvex
- p = p->nextaec;
- }
- }
-
- }
-
- //
- void DFS(AGraph *g, int v) //v
- {
- ArcNode *p = NULL;
- visited[v] = 1;
- p = g->adjlist[v]->firstarc; //p v
- while(p != NULL)
- {
- if(visited[p->adjvex] == 0) //
- DFS(g,p->adjvex);
- p = p->nextarc ;
- }
- }
- /*
- * * * *
- * * * *
- * * * *
- * * * *
-
-
- */
-
- //
- void BFS(AGraph *g,int v)
- {
- ArcNode *p = NULL;
- int w,i,front =0, rear = 0;
- int queue[MAXV];
- rear = (rear + 1) % MAXV;
- queue[rear] = v;
- for(i=0; i<g->n ; i++) visited[i] = 0;
- visited[v] = 1;
-
- while(front != rear)
- {
- front = (front + 1) % MAXV;
- w = queue[front];
- p = g->adjlist[w]->firstarc;
-
- while(p != NULL) //
- {
- if(visited[p->adjvex] == 0)
- {
- visited[p->adjvex] = 1;
- rear = (rear + 1) % MAXV;
- queue[rear] = p->adjvex;
- }
- p = p->nextarc ; // ， ， ，
- }
- }
- }
-
- //
- void DFS1(AGraph *g)
- {
- int i=0;
- for(i=0; i<g->n; i++)
- if(visited[i] == 0)
- DFS(g,i);
- }
-
- void BFS1(AGraph *g)
- {
- int i=0;
- for(i=0; i<g->n; i++)
- if(visited[i] == 0)
- BFS(g,i);
- }
-
- //
- // di yi ge ， while ， ，
- void DFS2(AGraph *g, int v)
- {
- ArcNode *p = NULL;
- ArcNode *st[MAXV] ;
-
- int i ,top = -1;
-
- for(i=0; i<g->n; i++) visited[i] = 0;
-
- top++;
- st[top] = g->adjlist[v]->firstarc;
- i = st[top]->adjvex;
-
- while(top > -1)
- {
- p = st[top]; top--;
- while(p != NULL)
- {
- i = st[top]->adjvex;
- if(visited[i] == 0)
- {
- visited[i] = 1;
- top++;
- st[top] = g->adjlist[i]->firstarc;
- break; // ，
- }
- p = p->nextarc;
- }
- }
- }
-
-
- // i j
- int DFSTrave(AGraph *g, int i,int j)
- {
- int k=0;
- for(k=0; k>g->n; k++) visited[k] = 0;
- DFS(g,i); // DFS visited
- if(visited[j] == 0) return 0;
- else return 1;
- }
-
- int BFSTrave(AGraph *g, int i,int j)
- {
- int k=0;
- for(k=0; k>g->n; k++) visited[k] = 0;
- BFS(g,i);
- if(visited[j] == 0) return 0;
- else return 1;
- }
-
- // ， ， n-1 ， ，
- void DFS3(AGraph *g, int v)
- {
- ArcNode *p;
- int vn=0;
- visited[v] = 1;
-
- }
-
-
- #include <stdio.h>
-
- typedef struct
- {
- int u; //
- int v; //
- int w; //
- }EdgeType;
-
- void Prim(MGraph g, int v0)
- {
- int lowcost[MAXV], vset[MAXV],v; // vset ,lowcost
- int i,j,k,min;
- v =v0;
- vset[v0] = 1;
-
- for(i=0; i<g.n; i++) // vset ， lowcost
- if(i != v0)
- {
- lowcost[i] = g.edge[v0][i];
- vset[i] = 0;
- }
-
- for(j=1; j<g.n; j++) // n-1
- {
- min = INF;
- for(k=0; k<g.n; k++) // v0
- {
- if(vset[k] != 0 && lowcost[k] < min)
- {
- min = lowcost[k];
- k = j;
- }
- }
- printf(" (%d, %d) : %d
", v,k,min);
- v=k; //v v0 ， v
- vset[k] = 1;
-
- for(j=0; j<g.n; j++) //
- if(vset[v][j] == 0 && g.edge[v][j] < lowcost[j])
- lowcost[j] = g.edge[v][j];
-
- }
- }
-
-
- void InsetSort(EdgeType E[], int n)
- {
- int i,j;
- EdgeType temp;
- for(i=0; i<n; i++)
- {
- temp = E[i];
- j = i-1; //
-
- while(j>=0 && E[j].w > temp.w) // E[i]
- {
- E[j+1] = E[j];
- j--;
- }
- E[j+1] = temp;
- }
- }
-
- void Kruskal(MGraph g)
- {
- EdgeType E[MAXV];
- int i,j,m1,m2,sn1,sn2,k;
- int vset[MAXV];
- k=0;
- for(i=0; i<g.n; i++) // E[]
- for(j=0; j<g.n; j++)
- if(g.edge[i][j] != 0 && g.edge[i][j] != INF)
- {
- E[k].u = i; E[k].v = j; E[k].w = g.edge[i][j];
- k++;
- }
- InseSort(E,g.e);
-
- for(i=0; i<g.n; i++) vset[i] = i;
- k=1; j=0; //k n-1 ，j
- while(k<g.n)
- {
- m1= E[j].u; m2 = E[j].v;
- sn1 = vset[m1]; sn2 = vset[m2];
- if(sn1 != sn2) // vset
- {
- printf(" (%d, %d) :%d",m1,m2,E[j].w);
- k++;
- for(i=0; i<g.n; i++)
- if(vset[i] == sn2)
- vset[i] = sn1;
- }
- j++;
- }
- }
-
- //
- #include <stdio.h>
-
- int path[MAXV];
- int v1[MAXV],v2[MAXV];
- int vn,vm; //vn ，v1 ，vm
-
- int cond(int path[],int d) //d path
- {
- int i,j;
- int flag1=0, f1, flag2=0, f2;
-
- for(i=0; i<vn; i++)
- {
- f1=1;
- for(j=0; j<=d; j++)
- if(path[j] == v1[i])
- {
- f1=0;
- break;
- }
- flag1 += f1;
- }
-
- for(i=0; i<vm; i++)
- {
- f2=0;
- for(j=0; j<=d; j++)
- if(path[j] == vm[i])
- {
- f2=1;
- break;
- }
- flag2 += f2;
- }
-
- if(flag1 == 0 && flag2 == 0) return 1;
- else return 0;
- }
-
-
- // vi vj
-
- void TravPath(AGraph *g, int vi, int vj, int d)
- {
- int v,i;
- ArcNode *p;
- d++;
- visited[vi] = 1;
- path[d] = vi; // visited
-
- if(vi == vj && Cond(path,d) == 1)
- {
- for(i=0; i<=d; i++) printf("%d ",path[i]);
- printf("
");
- }
-
- p = g->adjlist[vi]->firstarc;
- while(p != NULL)
- {
- v = p->adjvex;
- if(visited[v] == 0)
- TravPath(g,v,vj,d);
- p = p->nextarc ;
- }
- visited[vi] = 0; // ，
- d--;
- }
-
-
-
-
-
- // ，
- // ， visited 1
-
- void MDFS(MGraph g, int v)
- {
- int j;
- visited[v] = 1; // visited
- for(j=0; j<g.n; j++)
- if(g.edge[v][j] != 0 && g.edge[v][j] != INF && visited[j] == 0)
- MDFS(g,j);
- }
-
- int DGRoot1(MGraph g)
- {
- int i,j,k,n;
- for(i=0; i<g.n; i++)
- {
- for(j=0; j<g.n; j++) visited[j] = 0;
- MDFS(g,i);
- n = 0;
- for(k=0; k<g.n; k++)
- if(visited[k] == 1) n++;
- if(n == g.n) return i;
- }
- }
-
- void MBFS(MGraph g, int v)
- {
- int qu[MAXV], front =0, rear = 0;
- int i,j;
-
- visited[v] = 1;
- rear = (rear + 1) % MAXV;
- qu[rear] = v;
-
- while(front != rear)
- {
- front = (front + 1) % MAXV;
- i = qu[front];
-
- for(j=0; j<g.n; j++) // ， i
- {
- if(g.edge[i][j] != 0 && g.edge[i][j] != INF)
- {
- if(visited[j] == 0)
- {
- visited[j] = 1;
- rear = (rear + 1) % MAXV;
- qu[rear] = j;
- }
- }
- }
- }
- }
-
- int DGRoot2(MGraph g)
- {
- int i,j,k,n;
- for(i=0; i<g.n; i++)
- {
- for(j=0; j<g.n; j++) visited[j] = 0;
- BDFS(g,i);
- n=0;
- for(k=0; k<g.n; k++)
- if(visited[k] == 1) n++;
- if(n == g.n) return 1;
- else return 0;
- }
- }