當前位置:首頁 » 編程語言 » 圖的鄰接表基本操作c語言
擴展閱讀
webinf下怎麼引入js 2023-08-31 21:54:13
堡壘機怎麼打開web 2023-08-31 21:54:11

圖的鄰接表基本操作c語言

發布時間: 2023-05-29 00:52:28

『壹』 用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語言圖的遍歷,鄰接表存儲,深度,廣度優先遍歷

(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語言中編程實現建立無向圖的鄰接表,輸出某個點的鄰接點~!

用矩陣表示無向圖的,設有M個節點,則建立一個MXM矩陣,對每個頂點添加它的鄰接點,即每行中對於有標記的列為該行頂點的鄰接點。

『肆』 數據結構-圖的鄰接表表示(C語言)

//grap_theory.cpp:定義控制台應用程序的入口點。

//


//#include"stdafx.h"//VS2010頭文件

#include<stdio.h>

#defineNTOTAL(26*4)//最大路徑數目

#defineMAX_DISTANCE10000.0

structpiont{

intline_adjacency_list;

intnum_piont;

inttest_num[2];

charfrom[NTOTAL];

charto[NTOTAL];

charall_piont[NTOTAL];

intall_piont_num[NTOTAL];

floatdistance[NTOTAL];

floatdistance_all[NTOTAL][NTOTAL];

};//結構體定義

voidread(piont*test){

inti;

chartemp[100];

scanf("%d",&test->line_adjacency_list);//讀取行數

gets(temp);//讀取回車字元

for(i=0;i<test->line_adjacency_list;i++){//讀取列表

scanf("%c%c%f",&test->from[i],&test->to[i],&test->distance[i]);

gets(temp);//讀取回車字元

}

scanf("%c%c",&test->from[i],&test->to[i]);//讀取短短路徑名稱

}

voidcal_num_piont(piont*test){

inti,j;

intfrom_num,to_num;

test->num_piont=0;

for(i=0;i<NTOTAL;i++){

test->all_piont_num[i]=0;//點的度數清零

test->distance_all[i][i]=0.0;

for(j=i+1;j<NTOTAL;j++){

test->distance_all[i][j]=MAX_DISTANCE;

test->distance_all[j][i]=MAX_DISTANCE;

}

}

for(i=0;i<test->line_adjacency_list;i++){

//判斷from

for(j=0;j<test->num_piont;j++){

if(test->from[i]==test->all_piont[j]){

from_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->from[i];

from_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

//判斷end

for(j=0;j<test->num_piont;j++){

if(test->to[i]==test->all_piont[j]){

to_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->to[i];

to_num=j;

test->all_piont_num[j]++;

test->num_piont++;


}

test->distance_all[from_num][to_num]=test->distance[i];

test->distance_all[to_num][from_num]=test->distance[i];

}

//判斷所求點的位置

for(i=0;i<test->num_piont;i++){

if(test->from[test->line_adjacency_list]==test->all_piont[i])

test->test_num[0]=i;

if(test->to[test->line_adjacency_list]==test->all_piont[i])

test->test_num[1]=i;

}

}

floatmin_distance(piont*test){

inti,j,k,n;

floatmin_dis;

floatdis_i_k_add_k_j;

n=test->num_piont;

//Floyd-Warshall演算法

for(k=0;k<n;k++){

for(i=0;i<n;i++){

for(j=0;j<n;j++){

dis_i_k_add_k_j=(test->distance_all[i][k]+test->distance_all[k][j]);

if(test->distance_all[i][j]>dis_i_k_add_k_j)

test->distance_all[i][j]=dis_i_k_add_k_j;

}

}

}

min_dis=test->distance_all[test->test_num[0]][test->test_num[1]];

returnmin_dis;

}

voidtest_printf(piont*test,floatmin_dis){

inti;

printf("%d ",test->num_piont);

for(i=0;i<test->num_piont;i++){

printf("%d ",test->all_piont_num[i]);

}

printf("%-8.0f ",min_dis);

}

voidmain()

{

floatmin_dis;

pionttest1;//結構體聲明

read(&test1);

cal_num_piont(&test1);

min_dis=min_distance(&test1);

test_printf(&test1,min_dis);


}



『伍』 用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;
}