本文目录一览：
- 1、怎样用C语言实现已知起点 将完全带权图利用深度遍历求出所有路径 比较长度 输出最短路径的算法
- 2、C语言数据结构
- 3、c语言编写请简单点。用带权邻接矩阵输入一幅无向图，使用两种不同的算法计算出最短路径长度并输出路径。
怎样用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;iG.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;iG.vexnum;i++){ //初始化顶点
printf("输入顶点%d:",i);
scanf("%c",G.vexs[i]);
temp=getchar(); //接收回车
}
for(i=0;iG.vexnum;i++) //初始化邻接矩阵
for(j=0;jG.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条弧.\n",G.arcnum);
for(i=0;iG.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 kG.vexnum){ //k合理
for(int i=0;iG.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 iG.vexnum j=0 jG.vexnum){ //i,j合理
for(int k=j+1;kG.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;iG.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;iG.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;iG.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n深度优先遍历: ");
for(i=0;iG.vexnum;i++)
visited[i]=false;
BFS(G);
printf("\n程序结束.\n");
}
C语言数据结构
#include iostream.h
#include stdlib.h
#define INFINITY 0
#define MAX_VERTEX_NUM 10 //最大顶点数
#define MAX_EDGE_NUM 40 //最大边数
typedef enum {DG,DN,UDG,UDN}Graphkind;
typedef char VertexType; //顶点数据类型
typedef struct ArcCell
{
int adj; //无权图，1或0表示相邻否；带权图则是权值。
//int *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数。
Graphkind kind;
}MGraph;
int LocateVex(MGraph G,VertexType v1)
{
int i;
for(i=0;iG.vexnum;i++)
if(G.vexs[i]==v1)
return i;
return -1;
}
int CreatUDN(MGraph G)
// 采用数组表示法，构造无向网 G
{
VertexType v1,v2;
int w,j;
cout"输入图的顶点数"endl;
cinG.vexnum;
cout"输入图的弧数"endl;
cinG.arcnum;
for(int i=0;iG.vexnum;i++)
{
cout"输入顶点向量"endl;
cinG.vexs[i];
}
for(i=0;iG.vexnum;i++)
for(j=0;jG.vexnum;j++)
{
G.arcs[i][j].adj=INFINITY;
}
for(int k=0;kG.arcnum;++k) //构造邻接矩阵
{
cout"输入边依附的两个顶点"endl;
cinv1v2;
cout"输入此边的权值"endl;
cinw;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
return 1;
}
void dispMGraph(MGraph G)
{
cout"图的邻接矩阵图是："endl;
for(int i=0;iG.vexnum;i++)
{
for(int j=0;jG.vexnum;j++)
cout" "G.arcs[i][j].adj;
coutendl;
}
}
void main()
{
MGraph G;
CreatUDN(G);
dispMGraph(G);
}
// 邻接表 表示:
#include iostream.h
#include stdlib.h
#define MAX_VERTEX_NUM 20 //最大顶点数
#define MAX_EDGE_NUM 40 //最大边数
int visited[ MAX_VERTEX_NUM];
typedef int VertexType ; //顶点数据类型
typedef struct ArcNode
{
int adjvex;
int weight;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
void CreateDG(ALGraph G)
{
int i,j,k;
ArcNode *p;
cout"创建一个图:"endl;
cout"顶点数:"; cinG.vexnum;coutendl;
cout"边数:"; cinG.arcnum; coutendl;
for(i=0;iG.vexnum;i++)
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for(k=0;kG.arcnum;k++)
{
cout"请输入第"k+1"条边:";
cinij;
p=(ArcNode*)malloc(sizeof(ArcNode));
p-adjvex=j;
p-nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}
}
void Disp(ALGraph G)
{
int i,j;
ArcNode *p;
cout"输出图为:"endl;
for(i=0;iG.vexnum;i++)
{
p=G.vertices[i].firstarc;
j=0;
while(p!=NULL)
{
cout"("i","p-adjvex")";
p=p-nextarc;
j=1;
}
if(j==1)
coutendl;
}
}
void dfs(ALGraph G,int v) //深度优先遍历
{
ArcNode *p;
coutv" ";
visited[v]=1;
p=G.vertices[v].firstarc;
while(p!=NULL)
{ if(!visited[p-adjvex])
dfs(G,p-adjvex);
p=p-nextarc;
}
return ;
}
void dfs1(ALGraph G)
{
int i;
for(i=0;iG.vexnum;i++)
if(visited[i]==0)
dfs(G,i);
}
void main()
{
ALGraph G;
CreateDG(G);
int v;
Disp(G);
cout"输入顶点:";
cinv;
cout"深度优先序列:";
dfs1(G);
coutendl;
}
c语言编写请简单点。用带权邻接矩阵输入一幅无向图，使用两种不同的算法计算出最短路径长度并输出路径。
//Floyed 实现赋权无向图定点对间的最短路径，时间复杂度O(n^3)
1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
#includestdio.h
int main()
{
int c[20][20],parth[20][20],i,j,k,t1,t2,t3,n,x,y,re;
printf("输入图的顶点数:");
scanf("%d",n);
for(i=1;i=n;i++)
{
for(j=i+1;j=n;j++)
{
printf("输入边(%d,%d)的权值,若不存在输入10000:",i,j);
scanf("%d",c[i][j]);
}
}
如果是有向图就删掉这里"//for(i=1;i=n;i++)
//{
///////////////////////////////////////for(j=1;j=i;j++)
////////////////////////////////////////c[i][j]=c[j][i];
/////////////////////////////////////////}"
for(i=1;i=n;i++)
c[i][i]=0;//自己到自己的权值为0
for(i=1;i=n;i++) //初始化路径
{
for(j=1;j=n;j++)
parth[i][j]=0;
}
for(k=1;k=n;k++)//k是中间节点，i是起点j是中点。其实就是枚举中间节点，来求i j 的最短路径
{
for(i=1;i=n;i++)
{
for(j=1;j=n;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=10000t2!=10000(t3==10000||t1+t2t3)) //松弛 覆盖原来的最短路
{c[i][j]=t1+t2,parth[i][j]=k;}//记录i j的中间点是k
}
}
}
while(1)//也可以用递归的形式输出parth
{
printf("输入2点:");
scanf("%d%d",x,y);
printf("最短距离为%d\n",c[x][y]);
printf("%d ",x);
re=y;
while(parth[x][y]!=0)
{
printf("%d ",parth[x][y]);
y=parth[x][y];
}
printf("%d\n",re);
}
return 0;
}
