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语言算法
#include <stdio.h>
int m,n;
bool w[100][100],visited[100];
void dfs(int i){
visited[i] = true;
printf("%d ",i);
for(int j = 0;j<n;j++)
if(w[i][j] && !visited[j])
dfs(j);
}
int main(){
scanf("%d%d",&m,&n);
int a,b;
for(int i = 0;i<m;i++){
scanf("%d%d,&a,&b);
w[a][b] = w[b][a] = true;
}
for(int i = 0;i<n;i++)
if(!visited[i])
dfs(i);
return 0;
}
‘叁’ C语言广度优先搜索遍历图的算法
visited[v]=_________; FAULT
EnQueue(Q,w);
‘肆’ C语言 图的问题，请使用图的算法解决，没学过图的数据结构，不太会用（最好有注释）
在查询一个点是否循环时,有可能先陷入另一个循环,所以不能简单检测是否返回自身.
比如:
1->2->3->2->3.....
提供一个方案
其中还有一个问题,将图化为树进行遍历,用最小生成树方法.
接下来,建立一个用来路径记录的数组,将每一个被遍历的点存入其中,每一次存入都查找之前是否访问过该点,如果有,则判定为循环.
另外又想到一个直接的方法:
借鉴最小生成树方法,以一点作为根,生成一颗树,每一次生成新节点时,检测生成节点数是否大于mi.这样可以简单编码解决问题.
若遇到循环,则一定会生成mi+n个叶子,那么超过即判定存在循环.
‘伍’ 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语言实现图的广度优先搜索遍历算法
先写个大题思路，楼主先自己想想，想不出来的话，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语言算法流程图
开始->定义3个变量->输入3个数->判断3个数的大小->输出中间数
‘捌’ 求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语言编写求有向图有多少连通图的算法（数据结构题目）
深度优先搜索。
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;
}