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);
}