c語言帶權圖,c語言帶權圖的深度優先遍歷

本文目錄一覽：

• 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;

}