c语言图算法
//思路:先把邻接表转换成逆邻接表，这样问题简单多了。
//数组out，保存各节点的入度
void countindegree(AdjList gin, AdjList gout)
{
//设有向图有n个顶点，建逆邻接表的顶点向量。
for (int i=1;i<=n;i++)
{
gin[i].vertex=gout[i].vertex;
gin.firstarc=null;
}
//邻接表转为逆邻接表。
for (i=1;i<=n;i++)
{
p=gout[i].firstarc;//取指向邻接表的指针。
while (p!=null)
{
j=p->adjvex;
s=(ArcNode *)malloc(sizeof(ArcNode));//申请结点空间。
s->adjvex=i;
s->next=gin[j].firstarc;
gin[j].firstarc=s;
p=p->next;//下一个邻接点。
}//while
}//endof for
//统计各节点的入度
for (i=0; i<n; i++)
{
p = gin[i].firstarc;
while(p ! = null)
{
out[i]++;
p = p->next;
} //endof while
} //endof for
}//endof function
‘贰’ 用C语言编程实现图的遍历算法
图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，最近阿杰做了关于图的遍历的算法，下面是图的遍历深度优先的算法（C语言程序）：
#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=0;i<G->n;i++)
{
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<=m1;j++)
{
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=0;i<G->n;i++)
visited[i]=0;
for(i=0;i<G->n;i++)
if(!visited[i])
DFS(G,i);
}
int main()
{
ALGRAPH *G;
printf("下面以临接表存储一个图；\n");
creat(G);
printf("下面以深度优先遍历该图 \n");
DFSTraverse(G);
getchar();
}
‘叁’ 求c语言图的深度优先遍历算法
#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=0;i<G->n;i++) /* 建立有n个顶点的顶点表*/
{
printf("请输入第%d个顶点字符信息(共%d个)：",i+1,G->n);
scanf("%c",&(G->adjlist[i].vertex)); /* 读入顶点信息*/
getchar();
G->adjlist[i].firstedge=NULL; /* 顶点的边表头指针设为空*/
}
for(k=0;k<2*G->e;k++) /* 建立边表*/
{
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=0;i<G->n;i++)
{
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);w;w=NextAdjVertex(G,v,w))
if (!visited[w]) DFS(G,w); /* 对v尚未访问的邻接顶点w递归调用DFS */
}
void DFStraverse(ALGraph *G)
/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/
{ int i,v;
for(v=0;v<G->n;v++)
visited[v]=False;/*标志向量初始化*/
//for(i=0;i<G->n;i++)
if(!visited[0]) DFS(G,0);
}/*DFS*/
void main()
{
ALGraph G;
CreateALGraph(&G);
printf("该无向图的深度优先搜索序列为：");
DFStraverse(&G);
printf("\nSuccess!\n");
}
‘肆’ 怎么用c语言和数据结构来编写一个判断有向图是否为强连通图的算法
强连通图表明任意两点之间可以互相到达。
方案1：判断结点A可以到达的点的方法如下：
首先SA = {A}；
while 1
取SA中任意没有被去过的点x，根据以x为起点的有向线段，判断x可以直接到达的点，然后这些点加入SA；
如此循环，直到SA中的点的个数没有变化了
end
这样得到的集合SA是所有A可以到达的点的一个集合。
判断SA 是否等于S，若不等于S，表明不是强连通。
如此循环，求出所有S中的点的能够到达的点集。如果所有的点集都等于S表明强连通图。
方案2：可以优化1
‘伍’ C语言实现图的广度优先搜索遍历算法
先写个大题思路，楼主先自己想想，想不出来的话，2天后给代码。
queue<node> q;
q.push(start);
bool canVisit[][];
node cur;
while(!q.empty()){
cur = q.top();
q.pop();
foreach(node is connected by cur){
if(canVisit[node.x][node.y])
{
printf("访问结点(%d,%d)",node.x,node.y);
canVisit[node.x][node.y]=false;
q.push(node);
}
}
}
‘陆’ 用C语言编写以下算法： 一个5个节点的有向图，有向线段上有权重即T[i][j]，它表示节点i对节点j的信任度。
写C程序，随机给出n*n的邻接矩阵，并打印输出邻接矩阵，以及有向图的边的个数，每个顶点的度，并判断该图中是否存在Euler回路： （1）如果为n阶，则随机产生一个n*n的邻接矩阵； （2）输出漏乱模邻接矩阵，边的个数，每个顶点的度以及图中是否存在Euler回路。 这个题目涉及到了两个主要的知识点，一个是数据结构中的有向图的邻接矩阵的创建，还有就是离散数学中的Euler回路的判定定理。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#define n 5 //定义矩阵的阶数n
typedef int ver;
typedef int edg; //定义有向图的顶点和边值为整形
typedef struct{
ver v[n]; //顶点
edg e[n][n]; //边权
}graph; //定义邻接矩阵的数据结构
void printgraph (graph G) //打印输出邻接矩阵
{
int i,j;
printf("顶点");
for(i=0;i<n;i++)
printf("%3d",i);
printf("\n");
for(i=0;i<n;i++)
{
printf("%4d",i);
for(j=0;j<n;j++)
printf("%3d",G.e[i][j]);
printf("\n");
}
}
void countD (graph G) //判断有向图的顶点的度，并判断Euler回路
{
int i,j,l;
int e=0,count=0;
int k; //计数器赋0
int c[n],d[n];
for (i=0;i<n;i++){
c[i]=0;
for (j=0;j<n;j++){
if (G.e[i][j]!=0)
c[i]=c[i]+1;
}
printf("顶点 %d 的出度为: %d \n",i,c[i]); //有向图的任意顶点i的出度为邻接矩阵中第i行不为0的数的个数
}
printf("\n");
for (j=0;j<n;j++){
d[j]=0;
for (i=0;i<n;i++){
if (G.e[i][j]!=0)
d[j]=d[j]+1;
}
printf("顶点 %d 的入度为: %d \n",j,d[j]); //有向图的任意顶点j的入度为邻接矩阵中第j列不为0的数的个陪氏数
}
for (l=0;l<n;l++){
if (c[l]==d[l])
count++;
else {
if (c[l]-d[l]==1)
e++;
else{
if (d[l]-c[l]==1)
e++;
}
}
}
k=0;
if (count==n) //判断Euler回路： 1：所有顶点的出度等于入度；
//2：有且仅有两个点度数为奇数，返缓且一个出度比入度大一
k=1; //另一个入度比出度大一，其他的顶点出度等于入度
else {
if (e==2 && count==n-2)
k=1;
}
if (k==1)
printf("有向图中存在Euler回路\n");
else
printf("有向图中不存在Euler回路\n");
}
void main() //主函数
{
int i,j,temp;
graph G;
srand(time (NULL)); //随机种子
for (i=0;i<n;i++){
for (j=0;j<n;j++)
G.e[i][j]=0;
}
for (i=0;i<n;i++)
G.v[i]=0;
for (i=0;i<n;i++){
for (j=0;j<n;j++){
do
{
temp = rand()%n; //随机建造邻接矩阵
if (G.v[i]<n)
{
G.e[i][j] = temp;
G.v[i]++;
break;
}
}
while (1);
}
}
printf("生成的有向图邻接矩阵为: \n");
printgraph(G);
countD (G); //调用子函数
printf("有向图的边数为：%d\n",n*(n-1)/2);
}
另外,团IDC网上有许多产品团购,便宜有口碑
‘柒’ C语言广度优先搜索遍历图的算法
visited[v]=_________; FAULT
EnQueue(Q,w);
‘捌’ 求常用的图算法（C语言描述）
/*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=0;i<=degree;i++)
coeffa[i]=coeff[i];
for(r=1;r<degree;r++)
for(i=0;i<=degree-r;i++)
{
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+1;j<=i+1;j++)
coeffa[j]=coeff[j-i+degree-1];
for(k=1;i<=degree;k++)
forj=i+1;j>=i-degree+k+1;j--)
{
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-t;fact=1.0;n=1;
aux=coeff[0]*t1;
for(i=1;i<degree;i++)
{
face=fact*t;
n=n*(degree-i+1)/i;
aux=(aux+fact*n*coeff[i])*t1;
}
aux=aux+fact*t*codff[degree];
return aux;
}
‘玖’ 用C语言编写求有向图有多少连通图的算法（数据结构题目）
深度优先搜索。
http://www.cnblogs.com/dzkang2011/p/bfs_dfs.html
#include<iostream>
#include<cstdio>
usingnamespacestd;
#definemaxn100//最大顶点个数
intn,m;//顶点数，边数
structarcnode//边结点
{
intvertex;//与表头结点相邻的顶点编号
intweight=0;//连接两顶点的边的权值
arcnode*next;//指向下一相邻接点
arcnode(){}
arcnode(intv,intw):vertex(v),weight(w),next(NULL){}
arcnode(intv):vertex(v),next(NULL){}
};
structvernode//顶点结点，为每一条邻接表的表头结点
{
intvex;//当前定点编号
arcnode*firarc;//与该顶点相连的第一个顶点组成的边
}Ver[maxn];
voidInit()//建立图的邻接表需要先初始化，建立顶点结点
{
for(inti=1;i<=n;i++)
{
Ver[i].vex=i;
Ver[i].firarc=NULL;
}
}
voidInsert(inta,intb,intw)//尾插法，插入以a为起点，b为终点，权为w的边，效率不如头插，但是可以去重边
{
arcnode*q=newarcnode(b,w);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
if(p->vertex==b)//如果不要去重边，去掉这一段
{
if(p->weight<w)
p->weight=w;
return;
}
while(p->next!=NULL)
{
if(p->next->vertex==b)//如果不要去重边，去掉这一段
{
if(p->next->weight<w);
p->next->weight=w;
return;
}
p=p->next;
}
p->next=q;
}
}
voidInsert2(inta,intb,intw)//头插法，效率更高，但不能去重边
{
arcnode*q=newarcnode(b,w);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
q->next=p;
Ver[a].firarc=q;
}
}
voidInsert(inta,intb)//尾插法，插入以a为起点，b为终点，无权的边，效率不如头插，但是可以去重边
{
arcnode*q=newarcnode(b);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
if(p->vertex==b)return;//去重边，如果不要去重边，去掉这一句
while(p->next!=NULL)
{
if(p->next->vertex==b)//去重边，如果不要去重边，去掉这一句
return;
p=p->next;
}
p->next=q;
}
}
voidInsert2(inta,intb)//头插法，效率跟高，但不能去重边
{
arcnode*q=newarcnode(b);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
q->next=p;
Ver[a].firarc=q;
}
}
voidShow()//打印图的邻接表（有权值）
{
for(inti=1;i<=n;i++)
{
cout<<Ver[i].vex;
arcnode*p=Ver[i].firarc;
while(p!=NULL)
{
cout<<"->("<<p->vertex<<","<<p->weight<<")";
p=p->next;
}
cout<<"->NULL"<<endl;
}
}
voidShow2()//打印图的邻接表(无权值）
{
for(inti=1;i<=n;i++)
{
cout<<Ver[i].vex;
arcnode*p=Ver[i].firarc;
while(p!=NULL)
{
cout<<"->"<<p->vertex;
p=p->next;
}
cout<<"->NULL"<<endl;
}
}
#defineINF999999
boolvisited[maxn];//标记顶点是否被考察，初始值为false
intparent[maxn];//parent[]记录某结点的父亲结点，生成树，初始化为-1
intd[maxn],time,f[maxn];//时间time初始化为0，d[]记录第一次被发现时，f[]记录结束检查时
voiddfs(ints)//深度优先搜索（邻接表实现），记录时间戳，寻找最短路径
{
cout<<s<<"";
visited[s]=true;
time++;
d[s]=time;
arcnode*p=Ver[s].firarc;
while(p!=NULL)
{
if(!visited[p->vertex])
{
parent[p->vertex]=s;
dfs(p->vertex);
}
p=p->next;
}
time++;
f[s]=time;
}
voiddfs_travel()//遍历所有顶点，找出所有深度优先生成树，组成森林
{
for(inti=1;i<=n;i++)//初始化
{
parent[i]=-1;
visited[i]=false;
}
time=0;
for(inti=1;i<=n;i++)//遍历
if(!visited[i])
dfs(i);
cout<<endl;
}
intmain()
{
inta,b;
cout<<"Enternandm：";
cin>>n>>m;
Init();
while(m--)
{
cin>>a>>b;//输入起点、终点
Insert2(a,b);//插入操作
}
Show2();//邻接表
dfs_travel();//遍历
intcnt=0;//连通图个数
for(inti=1;i<=n;i++)
if(parent[i]==-1)
cnt++;
printf("%d ",cnt);
return0;
}
‘拾’ N-S图表示c语言算法
算法一：
用的是等差数列的求和公式，现在简单推宽悉导一李郑下：
S
=
1
+
2
+
3
+
……
+
n
S
=
n
+（n-1）+
（n-2）+
……
+
1
相加得：
2*S
=
(n+1)+(n+1)+(n+1)+……
+(n+1)
得
s
=
（慎扰乎n+1）*
n/
2
算法二和算法三
都差不多，C语言实现如下
void
sum(int
N)
{
int
S
=
0;
int
i;
for(i=1;i<N;i++)
S
+=
i;
printf("%d",N);
}