c语言图的广度优先遍历
⑴ 用c语言实现 图的邻接表和邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍历。
/*
程序1：邻接表的dfs,bfs
其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。
*/
#include<stdio.h>
#include<string.h>
#defineMAXM100000
#defineMAXN10000
intnext[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;
voidinput_data()
{
scanf("%d%d",&n,&m);
inti,x,y;
for(i=1;i<=m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
next[i]=first[x];
first[x]=i;
en[i]=y;
}
}
voidpre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
voiddfs(intx)
{
flag[x]=1;
if(!pd)
{
pd=1;
printf("%d",x);
}else
printf("%d",x);
intp=first[x];
while(p!=0)
{
inty=en[p];
if(!flag[y])dfs(y);
p=next[p];
}
}
voidbfs(intk)
{
head=0;tail=1;
flag[k]=1;dl[1]=k;
while(head<tail)
{
intx=dl[++head];
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
intp=first[x];
while(p!=0)
{
inty=en[p];
if(!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
p=next[p];
}
}
}
intmain()
{
input_data();//读入图信息。
pre();//初始化
printf("图的深度优先遍历结果:");
inti;
for(i=1;i<=n;i++)//对整张图进行dfs;加这个for主要是为了防止不多个子图的情况
if(!flag[i])
dfs(i);
printf(" ------------------------------------------------------------- ");
pre();//初始化
printf("图的广度优先遍历结果为:");
for(i=1;i<=n;i++)
if(!flag[i])
bfs(i);
printf(" ----------------------end------------------------------------ ");
return0;
}
/*
程序2:邻接矩阵
图的广度优先遍历和深度优先遍历
*/
#include<stdio.h>
#include<string.h>
#defineMAXN1000
intn,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];
voidinput_data()
{
scanf("%d%d",&n,&m);
inti;
for(i=1;i<=m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
w[x][0]++;
w[x][w[x][0]]=y;
}
}
voidpre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
voiddfs(intx)
{
flag[x]=1;
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
inti;
for(i=1;i<=w[x][0];i++)
{
inty=w[x][i];
if(!flag[y])dfs(y);
}
}
voidbfs(intt)
{
inthead=0,tail=1;
dl[1]=t;flag[t]=1;
while(head<tail)
{
intx=dl[++head];
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
inti;
for(i=1;i<=w[x][0];i++)
{
inty=w[x][i];
if(!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
}
}
}
intmain()
{
input_data();
printf("图的深度优先遍历结果:");
pre();
inti;
for(i=1;i<=n;i++)
if(!flag[i])
dfs(i);
printf(" --------------------------------------------------------------- ");
printf("图的广度优先遍历结果:");
pre();
for(i=1;i<=n;i++)
if(!flag[i])
bfs(i);
printf(" -----------------------------end-------------------------------- ");
return0;
}
⑵ 求一个C语言编程，图的遍历，深度优先和广度优先搜索的程序。要浅显易懂的~~~~
给你一个作为参考吧
#include <iostream>
#define INFINITY 32767
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
//图的邻接矩阵存储结构
typedef struct{
char *vexs; //顶点向量
int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}Graph;
//队列类
class Queue{
public:
void InitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;
}
void EnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e){
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
public:
int *base;
int front;
int rear;
};
//图G中查找元素c的位置
int Locate(Graph G,char c){
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i;
return -1;
}
//创建无向网
void CreateUDN(Graph &G){
int i,j,w,s1,s2;
char a,b,temp;
printf("输入顶点数和弧数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点.\n",G.vexnum);
for(i=0;i<G.vexnum;i++){ //初始化顶点
printf("输入顶点%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回车
}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条弧.\n",G.arcnum);
for(i=0;i<G.arcnum;i++){ //初始化弧
printf("输入弧%d:",i);
scanf("%c %c %d",&a,&b,&w); //输入一条边依附的顶点和权值
temp=getchar(); //接收回车
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
//图G中顶点k的第一个邻接顶点
int FirstVex(Graph G,int k){
if(k>=0 && k<G.vexnum){ //k合理
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i;
}
return -1;
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(Graph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
//深度优先遍历
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次执行DFS时,k为-1
for(i=0;i<G.vexnum;i++)
if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS
}
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //访问第k个顶点
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS
}
}
//广度优先遍历
void BFS(Graph G){
int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]){ //i尚未访问
visited[i]=true;
printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear){
Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w为k的尚未访问的邻接顶点
visited[w]=true;
printf("%c ",G.vexs[w]);
Q.EnQueue(w);
}
}
}
}
//主函数
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n广度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n深度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G);
printf("\n程序结束.\n");
}
⑶ c语言图的遍历，邻接表存储，深度，广度优先遍历
（1） 图的建立，按采用邻接表作为存储结构。
（2） 从指定顶点出发进行深度优先搜索遍历。
（3） 从指定顶点出发进行广度优先搜索遍历。
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"
#define MAX_INT 1000
#define MAX_VERTEX_NUM 20
#define MAX_QUEUE_NUMBER 20
typedef struct ArcNode
{
int adjvex;
double adj;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode
{
char szName[40];
ArcNode *firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vexs;
int vexnum,arcnum;
}Net;
//定义队列
typedef struct{
int *elem;
int front, rear;
}Queue;
void InitQueue(Queue &Q)
{
Q.elem = new int[MAX_QUEUE_NUMBER];
Q.front = Q.rear = 0;
}
int EmptyQueue(Queue Q)
{
if(Q.front==Q.rear)
return 0;
else
return 1;
}
void DestroyQueue(Queue &Q){
delete []Q.elem;
Q.front = Q.rear = 0;
}
void EnterQueue(Queue &Q, int e)
{
if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)
Q.elem[Q.rear ] = e;
else
printf("队列满!\n");
Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;
}
void LeaveQueue(Queue &Q, int &e)
{
if(Q.rear != Q.front)
e = Q.elem[Q.front];
else
printf("队列空!\n");
Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;
}
int LocateVex(Net ga,char *name)
{
int i;
for(i=0;i<ga.vexnum;i++)
if(strcmp(name,ga.vexs[i].szName)==0)
return i;
return -1;
}
void crt_net(Net &ga)
{
ArcNode *p;
char name1[40],name2[40];
int i,j,k;
double w;
printf("请输入顶点数和弧数：");
scanf("%d%d",&ga.vexnum,&ga.arcnum);
printf("请依次输入顶点名：\n");
for(i=0;i<ga.vexnum;i++)
{
scanf("%s",ga.vexs[i].szName);
ga.vexs[i].firstarc=NULL;
}
for(k=0;k<ga.arcnum;k++)
{
printf("请输入相邻的两个定点和权值：");
scanf("%s%s%lf",name1,name2,&w);
i=LocateVex(ga,name1);
j=LocateVex(ga,name2);
p=new ArcNode;
p->adjvex=j;
p->adj=w;
p->nextarc=ga.vexs[i].firstarc;
ga.vexs[i].firstarc=p;
}
}
void DFS(Net ga,char *name,int *visited)
{
int v,w;
ArcNode *p;
v=LocateVex(ga,name);
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
p=ga.vexs[v].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(ga,ga.vexs[w].szName,visited);
p=p->nextarc;
}
}
void DFSTravel(Net ga,char *name)
{
int v,k=0;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
DFS(ga,ga.vexs[v].szName,visited);
}
}
void BFSTravel(Net ga,char *name)
{
ArcNode *p;
int v,w,u,k=0;
Queue Q;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
{
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
EnterQueue(Q,v);
while(EmptyQueue(Q)!=0)
{
LeaveQueue(Q,u);
p=ga.vexs[u].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%s ",ga.vexs[w].szName);
visited[w]=1;
EnterQueue(Q,w);
}
p=p->nextarc;
}
}
}
}
}
void main()
{
char name[40];
Net ga;
crt_net(ga);
printf("请输入深度优先遍历开始点的名：");
scanf("%s",name);
printf("深度优先遍历：");
DFSTravel(ga,name);
printf("\n");
printf("请输入广度优先遍历开始点的名：");
scanf("%s",name);
printf("广度优先遍历：");
BFSTravel(ga,name);
printf("\n");
}
⑷ 图的深度/广度优先遍历C语言程序
这是我们老师给我们上数据结构课的课件
#include "stdio.h"
typedef int datatype; /*假定线性表元素的类型为整型*/
#define maxsize 1024 /*假定线性表的最大长度为1024*/
# define n 100 /* 图的顶点最大个数 */
typedef char VEXTYPE; /* 顶点的数据类型 */
typedef float ADJTYPE; /* 权值类型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 顶点信息数组 */
ADJTYPE arcs[n][n] ; /* 边权数组 */
int num ; /* 顶点的实际个数 */
}GRAPH;
/***********************1。置空图**********************/
void GraphInit(GRAPH *L)
{
L->num=0;
}
/***********************2。求结点数**********************/
int GraphVexs(GRAPH *L)
{
return(L->num);
}
/***********************3。创建图**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf("请输入顶点数目：");
scanf("%d",&L->num);
printf("请输入各顶点的信息(单个符号）：");
for(i=0;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf("请输入边权矩阵的信息：");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;j++)
{
scanf("%f",&L->arcs[i][j]);
}
}
printf("图已经创建完毕！");
}
/***********************4。图的输出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf("\n图的顶点数目为：%d",L.num);
printf("\n图的各顶点的信息为：\n");
for(i=0;i<L.num;i++)
printf("%c ",L.vexs[i]);
printf("\n图的边权矩阵的信息为：\n");
for(i=0;i<L.num;i++)
{
for(j=0;j<L.num;j++)
{
printf("%6.2f ",L.arcs[i][j]);
}
printf("\n");
}
printf("图已经输出完毕！");
}
/***********************5。图的深度周游**********************/
void DFS(GRAPH g,int qidian,int mark[])
//从第qidian个点出发深度优先周游图g中能访问的各个顶点
{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。图的深度周游**********************/
void GraphDFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf("\n深度周游：");
printf("\n请输入起点的下标：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
//printf("v=%d ",v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //队列元素的数据类型
typedef struct
{
DATATYPE data[maxsize]; //队中元素
int front,rear; //队头元素下标、队尾元素后面位置的下标
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//将顺序循环队列sq置空（初始化）
{
sq->front=0;
sq->rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果顺序循环队列sq为空，成功返回1，否则返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0
{
if (QueueIsEmpty(sq))
{ printf("queue is empty!\n");return 0;}
else
{ *e=sq.data[(sq.front)]; return 1;}
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//将元素x入队列sq的队尾，成功返回1，失败返回0
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!\n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//将队列sq队首元素出队列，成功返回1,失败返回0
{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!\n");
return 0;
}
else
{
sq->front=(sq->front+1)%maxsize;
return 1;
}
}
/***********************7。图的广度周游**********************/
void BFS(GRAPH g,int v,int mark[])
//从v出发广度优先周游图g中能访问的各个顶点
{
int v1,v2;
SEQQUEUE q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}
/***********************8。图的广度周游**********************/
void GraphBFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf("\n广度周游：");
printf("\n请输入起点的下标：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}
/***********************主函数**********************/
void main()
{
GRAPH tu;
GraphCreate(&tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}
⑸ 用c语言编程 1创建图的邻接矩阵和邻接表 2验证图的深度优先、广度优先遍历算法 3验证最短路径
这些是c++的代码不知是否满足你的要求。
1、邻接表表示的图中分别用DFS和BFS遍历
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 图的邻接表的结点
struct Edge
{
int dest; // 目标结点下标
// int value; // 路径长度
Edge *link; // 下一个结点
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 为图添加一条边
// Input: edge - 欲加边的结点; dest - 目的结点
// Output: edge - 加边后的结点
// Tags:
void AddEdge(Edge *&edge, int dest)
{
// 简单的链表操作
if (!edge)
{
edge = new Edge;
edge->dest = dest;
edge->link = 0;
}
else
{
Edge *tail = edge;
while (tail->link) tail = tail->link;
tail->link = new Edge;
tail = tail->link;
tail->dest = dest;
tail->link = 0;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: Console下输入图的边
// Input: Graph - 图; n - 图的结点的个数; EdgeNumber - 添加边的个数;
// Output: Graph - 添加边后的图
// Tags: 用户输入点对(a, b), 表示添加a->b的路径
void Input(Edge **&graph, int n, int EdgeNumber)
{
int i = 0, a, b;
for (i = 0; i < EdgeNumber; i++)
{
scanf("%d %d", &a, &b); // 用户输入起点终点
AddEdge(graph[a], b); // 添加a->b的边
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 深度优先搜索并输出
// Input: Graph - 图; n - 图的结点的个数; StartEdge — 开始的结点;
// Output: Console下输出遍历的顺序
// Tags: 递归调用 _dfs过程、回溯算法
void _dfs(Edge **&graph, bool *visited, int n, int index);
void DFS(Edge **&graph, int n, int StartEdge)
{
bool *visited = new bool[n]; // 标记每个结点是否已访问
memset(visited, (int)false, sizeof(bool) * n);
visited[StartEdge] = true;
printf("start edge: %d\n", StartEdge);
_dfs(graph, visited, n, StartEdge);
visited[StartEdge] = false;
}
// _dfs过程：
// Input: Graph - 图; n - 图的结点的个数; index - 当前的下标, visited - 记录结点是否已访问
// Output: Console下输出遍历的顺序
void _dfs(Edge **&graph, bool *visited, int n, int index)
{
int nIndex; // 下一个结点下标
Edge *edge = graph[index]; // 遍历用结点
while (edge) // 遍历所有的邻接结点
{
nIndex = edge->dest;
if (!visited[nIndex])
{
visited[nIndex] = true;
printf("%d\t", nIndex);
_dfs(graph, visited, n, nIndex);
}
edge = edge->link;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 广度优先搜索并输出
// Input: Graph - 图; n - 图的结点的个数; StartEdge - 开始的结点
// Output: Console下输出遍历的顺序
// Tags: 需要一个队列记录所有的灰色结点
void BFS(Edge **&graph, int n, int StartEdge)
{
bool *visited = new bool[n]; // 记录结点是否已访问
memset(visited, (int)false, sizeof(bool) * n);
queue<int> Q; // 记录准备访问的结点
Edge *edge; // 记录当前遍历的结点
int nIndex; // 记录下标
visited[StartEdge] = true;
printf("start edge:%d\n", StartEdge);
Q.push(StartEdge);
while (!Q.empty())
{
edge = graph[Q.front()];
while (edge)
{
nIndex = edge->dest;
if (!visited[nIndex])
{
visited[nIndex] = true;
printf("%d\t", nIndex);
Q.push(nIndex);
}
edge = edge->link;
}
Q.pop();
}
}
int main()
{
const int NODE_NUMBER = 7; // 10结点
const int EDGE_NUMBER = 11; // 10边
Edge **graph = new Edge *[NODE_NUMBER]; // 图
memset(graph, 0, sizeof(Edge *) * NODE_NUMBER); // 一开始没边
Input(graph, NODE_NUMBER, EDGE_NUMBER); // 输入边
printf("DFS:\n");
DFS(graph, NODE_NUMBER, 0); // 深度优先
printf("\n");
printf("BFS:\n");
BFS(graph, NODE_NUMBER, 0); // 广度优先
printf("\n");
return 0;
}
2、邻接矩阵表示的图中利用bellman-ford算法获得单点最短路
#include <cstdio>
#include <cstring>
using namespace std;
#define INTEGER_INF 0xffff // 表示无穷大路径
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 邻接矩阵表示的图
struct Graph
{
int **value; // 权值
int number; // 结点个数
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化图
// Input: number - 结点个数
// Output: graph - 图
void InitGraph(Graph &graph, int number)
{
int i, j;
graph.value = new int *[number];
for (i = 0; i < number; i++)
graph.value[i] = new int[number];
for (i = 0; i < number; i++)
{
for (j = 0; j < number; j++)
{
if (i == j)
graph.value[i][j] = 0;
else
graph.value[i][j] = INTEGER_INF;
}
}
graph.number = number;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 析构图
// Input: graph - 图
// Output: graph - 析构后的图的壳子
void FreeGraph(Graph &graph)
{
int i;
for (i = 0; i < graph.number; i++)
delete []graph.value[i];
delete []graph.value;
graph.number = 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用户在Console下输入图的边
// Input: n - 边的数量
// Output: graph - 加边后的图
void AddEdge(Graph &graph, int n)
{
int i, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d%d%d", &a, &b, &v);
graph.value[a][b] = v;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: BellmanFord 算法计算单源最短路
// Input: graph - 图, index - 起点
// Output: true - 存在最短路 且 Console 下输出起点到各个顶点的最短路
// false - 不存在最短路(存在边权和为负的环路)
bool BellmanFord(Graph &graph, int index)
{
int num = graph.number; // 结点个数
int *v = new int[num]; // 记录最短路
int i, j, t;
// 设定初值
for (t = 1; t < num; t++)
v[t] = INTEGER_INF;
v[index] = 0;
// 松弛
for (t = 0; t < num - 1; t++) // 循环i-1次
for (i = 0; i < num; i++)
for(j = 0; j < num; j++)
if (i != j && graph.value[i][j] != INTEGER_INF) // 如果两顶点间有路
if (v[j] > v[i] + graph.value[i][j]) // 松弛
v[j] = v[i] + graph.value[i][j];
// 判断是否存在边权和为负的环路
for (i = 0; i < num; i++)
for (j = 0; j < num; j++)
if (graph.value[i][j] != INTEGER_INF &&
v[j] > v[i] + graph.value[i][j])
return false;
// 输出
for (t = 1; t < num; t++)
printf("%d\t", v[t]);
return true;
}
int main()
{
Graph graph;
InitGraph(graph, 5);
AddEdge(graph, 10);
if (!BellmanFord(graph, 0))
printf("该图中存在边权和为负的环路!\n");
FreeGraph(graph);
return 0;
}
⑹ 广度优先 算法，各位帮帮。。急
个人对广度优先算法的理解是每次优先遍历父结点下的直接子结点，遍历完这些直接子结点之后再从这些子结点开始遍历他们的直接子结点，以此类推下去，直到找到终点。所以，此处肯定是需要使用到迭代了。在此我想写出我的思路来与楼主交流下。
1.确定startway点和endway点以后，找到startway点，并对该点下的子结点进行遍历。如你此处选择的startway是牧野草原04 即位置在ab(04)，endway是牧野草原15，那么ab(04)下的直接子结点可认为是牧野草原06、牧野草原08和牧野草原10。我们开始按照广度优先算法遍历到牧野草原15。
2.首先我们遍历完04的子结点（06，08，10），发现没有15。
3.接下来我们遍历结点06的子结点（04，05，03），发现没有15.
4.然后，我们开始遍历结点08的子结点（4，15，16），发现15，于是整个遍历结束。
PS:对于回路的子结点不应该考虑遍历，比如06中04的回路。
⑺ 谁教我：深度优先遍历和广度优先遍历
回去认真看书吧。书上已经讲得非常清楚了。最好是有本习题集，效果会好得多。我当时要考试了，花了不短的时间才把这个搞清楚。
你所要求的东西我想教材上比网上任何一个教程都要准确而细致。你在这儿问最多会有人给你贴点C语言实现的代码,那有什么用？
学习当以书本为主，其它为辅。
如果不明白的可以PM我。