#include<stdio.h>
#include<malloc.h>
#define MaxVertexNum 5
#define m 5
#define TRUE 1
#define NULL 0
typedef struct node
{
int adjvex
struct node *next
}JD
typedef struct EdgeNode
{
int vexdata
JD *firstarc
}TD
typedef struct
{
TD ag[m]
int n
}ALGRAPH
void DFS(ALGRAPH *G,int i)
{
JD *p
int visited[80]
printf("visit vertex:%d->",G->ag[i].vexdata)
visited[i]=1
p=G->ag[i].firstarc
while(p)
{
if (!visited[p->adjvex])
DFS(G,p->adjvex)
p=p->next
}
}
void creat(ALGRAPH *G)
{
int i,m1,j
JD *p,*p1
printf("please input the number of graph\n")
scanf("%d",&G->n)
for(i=0i<G->ni++)
{
printf("please input the info of node %d",i)
scanf("%d",&G->ag[i].vexdata)
printf("please input the number of arcs which adj to %d",i)
scanf("%d",&m1)
printf("please input the adjvex position of the first arc\n")
p=(JD *)malloc(sizeof(JD))
scanf("%d",&p->adjvex)
p->next=NULL
G->ag[i].firstarc=p
p1=p
for(j=2 j<=m1j++)
{
printf("please input the position of the next arc vexdata\n")
p=(JD *)malloc(sizeof(JD))
scanf("%d",&p->adjvex)
p->next=NULL
p1->next=p
p1=p
}
}
}
int visited[MaxVertexNum]
void DFSTraverse(ALGRAPH *G)
{
int i
for(i=0i<G->ni++)
visited[i]=0
for(i=0i<G->ni++)
if(!visited[i])
DFS(G,i)
}
int main()
{
ALGRAPH *G
printf("下面以临接表存储一个图；\n")
creat(G)
printf("下面以深度优先遍历该图 \n")
DFSTraverse(G)
getchar()
}
/*Bezier曲线的Casteljau算法*/float decas(degree,codff,t)
float coeff[]
float t
int degree
{
int r,i
float t1
float codffa[10]
t1=1.0-t
for(i=0i<=degreei++)
coeffa[i]=coeff[i]
for(r=1r<degreer++)
for(i=0i<=degree-ri++)
{
coeffa[i]=t1*coeffa[i]+t*coeffa[i+1]
}
return (coeffa[0])
}
/*B样条曲线—deBoor分割算法*/
float deboor(degree,coeff,knot,u,i)
float coeff[],knot[]
float u
int degree,i
{
int k,j
float t1,t2
float coeffa[30]
for(j=i-degree+1j<=i+1j++)
coeffa[j]=coeff[j-i+degree-1]
for(k=1i<=degreek++)
forj=i+1j>=i-degree+k+1j--)
{
t1=(knot[j+degree-k]-u)/(knot[j+degree-k]-knot[j-1])
t2=1.0-t1
coeffa[j]=t1*coeffa[j-1]+t2*coeffa[j]
}
return (coeffa[i+1])
}
/*Bezier曲线的Horner算法*/
float hornbez(degree,coeff,t)
int degree
float coff[]
float t
{
int i,n
float fact,t1,aux
t1=1.0-tfact=1.0n=1
aux=coeff[0]*t1
for(i=1i<degreei++)
{
face=fact*t
n=n*(degree-i+1)/i
aux=(aux+fact*n*coeff[i])*t1
}
aux=aux+fact*t*codff[degree]
return aux
}
#define MaxVerNum 100 /* 最大顶点数为*/typedef enum {False,True} boolean
#include "stdio.h"
#include "stdlib.h"
boolean visited[MaxVerNum]
typedef struct node /* 表结点*/
{
int adjvex/* 邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/
char Info/*与边(或弧)相关的信息*/
struct node * next /* 指向下一个邻接点的指针域*/
} EdgeNode
typedef struct vnode /* 顶点结点*/
{
char vertex/* 顶点域*/
EdgeNode * firstedge /* 边表头指针*/
} VertexNode
typedef struct
{
VertexNode adjlist[MaxVerNum] /* 邻接表*/
int n,e/* 顶点数和边数*/
} ALGraph/* ALGraph是以邻接表方式存储的图类型*/
//建立一个无向图的邻接表存储的算法如下：
void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/
{
int i,j,k
int N,E
EdgeNode *p
printf("请输入顶点数和边数：")
scanf("%d %d",&G->n,&G->e)
printf("n=%d,e=%d\n\n",G->n,G->e)
getchar()
for(i=0i<G->ni++) /* 建立有n个顶点的顶点表*/
{
printf("请输入第%d个顶点字符信息(共%d个)：",i+1,G->n)
scanf("%c",&(G->adjlist[i].vertex)) /* 读入顶点信息*/
getchar()
G->adjlist[i].firstedge=NULL /* 顶点的边表头指针设为空*/
}
for(k=0k<2*G->ek++) /* 建立边表*/
{
printf("请输入边<Vi,Vj>对应的顶点序号(共%d个)：",2*G->e)
scanf("%d %d",&i,&j)/* 读入边<Vi,Vj>的顶点对应序号*/
p=(EdgeNode *)malloc(sizeof(EdgeNode))// 生成新边表结点p
p->adjvex=j /* 邻接点序号为j */
p->next=G->adjlist[i].firstedge/* 将结点p插入到顶点Vi的链表头部*/
G->adjlist[i].firstedge=p
}
printf("\n图已成功创建!对应的邻接表如下：\n")
for(i=0i<G->ni++)
{
p=G->adjlist[i].firstedge
printf("%c->",G->adjlist[i].vertex)
while(p!=NULL)
{
printf("[ %c ]",G->adjlist[p->adjvex].vertex)
p=p->next
}
printf("\n")
}
printf("\n")
} /*CreateALGraph*/
int FirstAdjVertex(ALGraph *g,int v)//找图g中与顶点v相邻的第一个顶点
{
if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex
else return 0
}
int NextAdjVertex(ALGraph *g ,int vi,int vj )//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点
{
EdgeNode *p
p=g->adjlist[vi].firstedge
while( p!=NULL &&p->adjvex!=vj) p=p->next
if(p!=NULL &&p->next!=NULL) return p->next->adjvex
else return 0
}
void DFS(ALGraph *G,int v) /* 从第v个顶点出发深度优先遍历图G */
{
int w
printf("%c ",G->adjlist[v].vertex)
visited[v]=True /* 访问第v个顶点，并把访问标志置True */
for(w=FirstAdjVertex(G,v)ww=NextAdjVertex(G,v,w))
if (!visited[w]) DFS(G,w) /* 对v尚未访问的邻接顶点w递归调用DFS */
}
void DFStraverse(ALGraph *G)
/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/
{ int i,v
for(v=0v<G->nv++)
visited[v]=False/*标志向量初始化*/
//for(i=0i<G->ni++)
if(!visited[0]) DFS(G,0)
}/*DFS*/
void main()
{
ALGraph G
CreateALGraph(&G)
printf("该无向图的深度优先搜索序列为：")
DFStraverse(&G)
printf("\nSuccess!\n")
}
