#include <stdio.h>
#include <stdlib.h>
#define MaxV 100
typedef struct graph *Graph;
struct graph
{
int V;
int E;
int deg[MaxV];
int **adj;
};
typedef struct
{
int v;
int w;
}Edge;
Edge Get_Edge(int v, int w)
{
Edge e;
e.v = v;
e.w = w;
return e;
}
int** Init_Matrix(int r, int c, int val)
{
int i,j;
int **t = (int**)malloc(r*sizeof(int*));
for(i = 0; i < r; ++i)
t[i] = (int *)malloc(c*sizeof(int));
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j)
t[i][j] = 0;
return t;
}
Graph Init_Graph(int v)
{
int i;
Graph G = (Graph)malloc(sizeof *G);
G->V = v;
G->E = 0;
for(i = 0; i < v; ++i)
G->deg[i] = 0;
G->adj = Init_Matrix(v,v,0);
return G;
}
int Ins_Edge(Graph G, Edge e)
{
int v = e.v, w = e.w;
if( v == w || G->adj[v][w] == 1)
return 0;
G->E++;
G->deg[v]++;
G->deg[w]++;
G->adj[v][w] = 1;
G->adj[w][v] = 1;
return 1;
}
void Rem_Edge(Graph G, Edge e)
{
int v = e.v, w = e.w;
if( G->adj[v][w] == 1)
G->E--;
G->deg[v]--;
G->deg[w]--;
G->adj[v][w] = 0;
G->adj[w][v] = 0;
}
int DegV(Graph G, int v)
{
return G->deg[v];
}
//欧拉路径的存在性
int PathE(Graph G, int v, int w)
{
int t;
t = DegV(G,v) + DegV(G,w); //一个图含有欧拉路径，当且仅当他是连通的，并且其中只有两个顶点的度数 为奇数
if(t%2 != 0)
return 0;
for(t = 0 ;t <G->V ; ++t)
if( t != v && t != w)
if( DegV(G,t) % 2 != 0)
return 0;
return 1;
}
/*
int main()
{
int v, i;
Edge e;
scanf("%d",&v);
Graph G = Init_Graph(v);
for(i = 0; i < 9; ++i)
{
scanf("%d %d",&e.v,&e.w);
Ins_Edge(G,e);
}
printf("Input Edge \n");
scanf("%d %d",&e.v, &e.w);
if(PathE(G,e.v, e.w))
printf("YES\n");
else
printf("NO\n");
return 0;
}
*/
static int visited[MaxV];
int pathR(Graph G,int v, int w, int layer)
{
int t;
for(t = 0; t < layer; ++t)
printf(" ");
if(v == w)
return 1;
visited[v] = 1;
for(t = 0; t < G->V; ++t)
if(G->adj[v][t] == 1)
if( visited[t] == 0)
{
printf("%d-%d pathR(G,%d,%d)\n",v,t,t,w);
if(pathR(G,t,w,layer+1))
return 1;
}
else
printf("%d-%d\n",v,t);
return 0;
}
int main()
{
int v, i;
Edge e;
scanf("%d",&v);
Graph G = Init_Graph(v);
for(i = 0; i < 10; ++i)
{
scanf("%d %d",&e.v,&e.w);
Ins_Edge(G,e);
}
printf("Input Edge \n");
scanf("%d %d",&e.v, &e.w);
pathR(G,e.v, e.w,0);
return 0;
}
打赏
微信扫一扫，打赏作者吧～
