① 用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;
}
② 數據結構-圖的鄰接矩陣表示(C語言)
#include<stdio.h>
int min(int a,int b)
{
return a>b?b:a;
}
int fun(int **a,int n,int begin,int end)
{
int m=~(1<<31),i;
if(begin==end)
return 0;
else
{
for(i=0;i<n;i++)
if(a[begin][i]!=-1&&a[begin][i]!=0)
m=min(fun(a,n,i,end),m);
return m;
}
}
int main()
{
int n,i,js=0;
char begin,end;
int a[26][26],b[26]={0};
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d,&a[i][j]");
if(i>j&&a[i][j]!=-1)
b[i]++;
}
getchar();
scanf("%c %c",&begin,&end);
for(i=0;i<n;i++)
s=s+b[i];
printf("%d\n",s);
for(i=0;i<n;i++)
printf("%d\n",b[i]);
fun(a,n,begin-'A',end-'A');
return 0;
}
③ c語言運用鄰接矩陣求最短路徑中的最長路徑問題
同問、
④ 數據結構c語言版 鄰接矩陣
#include<stdio.h>
#include<stdlib.h>
typedefintVertexType;
typedefintEdgetype;
#defineMaxVertexNum30
typedefstructGraph{
VertexTypevertexs[MaxVertexNum];
Edgetypearcs[MaxVertexNum][MaxVertexNum];
intvextexNum,edgeNum;
}MGraph;
voidCreatGraph(MGraph*G)
{
inti,j,k;
scanf("%d,%d",&(G->vextexNum),&(G->edgeNum));//vertexNum是頂點數edgeNum是邊數
for(i=0;i<G->vextexNum;i++)//輸入頂點信息，建立頂點表
scanf("%c",&(G->vertexs[i]));
for(i=0;i<G->vextexNum;i++)
{
for(j=0;j<G->vextexNum;j++)
G->arcs[i][j]=0;
}
for(k=0;k<G->edgeNum;k++)
{
scanf("%d,%d",&i,&j);
G->arcs[i][j]=1;//若加入G->arcs[j][i]=1;則為無向圖
}
}
voidPrintGraph(MGraph*G)
{
inti,j;
for(i=0;i<G->vextexNum;i++)
{
printf("%c",G->vertexs[i]);
}
for(i=0;i<G->vextexNum;i++)
{
for(j=0;j<G->vextexNum;j++)
printf("%d",G->arcs[i][j]);
printf(" ");
}
}
voidmain()
{
MGraph*G;
G=(MGraph*)malloc(sizeof(MGraph));
CreatGraph(G);
PrintGraph(G);
}
⑤ 數據結構 用C語言編程:求鄰接矩陣存儲結構的有向圖G中各結點的出度
對每個結點所對應的那一列，中的所有1加起來，就是出度。(鄰接矩陣中存的是0, 1)
入度的計算也是類似的。
V : 結點集合。v_i (i = 0, n-1), n = |V|.
E : 邊集合。表示為n*n的鄰接矩陣。
E[i, j] = { if v_i -> v_j 存在有向邊，1。else 0 }
求結點v_i的出度（偽碼）：
for (i = 0; i < n-1; i++) {
degree_sum = 0;
for (j = 0; j < n-1; j++) {
if (E[i][j] == 1)
degree_sum++;
}
}
⑥ c語言鄰接矩陣建造一個無向圖並深度優先遍歷 請問我寫的程序為啥只能輸出部分節點。。高手幫幫忙
你的DFS函數，就是深度優先的遞歸函數貌似沒有遞歸好
struct MGraph
{
int vertex[maxvertex]; //存頂點
int arc[maxvertex][maxvertex]; //存邊（鄰接矩陣）
int vertexnum,arcnum; //頂點數和邊數
};
其次是對圖的初始化：
void CreatMGraph(MGraph *&G)
{
int i,j;
cin1>>G->vertexnum>>G->arcnum; //輸入頂點數和邊數
for(i=0;i<G->vertexnum;i++) //輸入每個頂點的值
cin1>>G->vertex[i];
for(i=0;i<G->vertexnum;i++) //初始化鄰接矩陣
for(j=0;j<G->vertexnum;j++)
G->arc[i][j]=0;
for(i=0;i<G->arcnum;i++)
{
int n,m,w;
cin1>>n>>m>>w; //修改鄰接矩陣中的值
G->arc[n][m]=w;
G->arc[m][n]=w;
}
}
在此之前需要定義一個全局變數的visited數組：
int visited[maxvertex]; //標記已被訪問過的頂點(全局變數)
//廣度優先遍歷
void BFS(MGraph *&G,int v)
{
queue<int> q;
int x,j;
if(!visited[v]) //即為visited[v]==0，也就是未被訪問過
{
cout<<G->vertex[v]<<" ";
visited[v]=1;
q.push(v); //被訪問的頂點入隊
}
while(!q.empty()) //隊不空進循環
{
x=q.front(); //取隊頭元素
q.pop(); //隊頭出隊
for(j=0;j<G->vertexnum;j++)
if (G->arc[x][j]&&!visited[j])
{
cout<<G->vertex[j]<<" ";
visited[j]=1; //標記為訪問過
q.push(j); //被訪問的頂點繼續入隊
}
}
}
//深度優先遍歷
void DFS(MGraph *&G,int v)
{
nt j;
if(!visited[v])
{
cout<<G->vertex[v]<<" ";
visited[v]=1; //標記為訪問過
}
for(j=0;j<G->vertexnum;j++)
if (G->arc[v][j]&&!visited[j])//鄰接矩陣的第(v,j)元素不為0
{ //且未被訪問過則遞歸
DFS(G,j);
}
}
此為圖的鄰接矩陣的輸出函數：
void Print(MGraph *G)
{
int i,j;
for(i=0;i<G->vertexnum;i++)
{
for(j=0;j<G->vertexnum;j++)
cout<<G->arc[i][j]<<" ";
cout<<endl;
}
}
main函數調用上面函數：
int main()
{
MGraph *G=new MGraph;
CreatMGraph(G);
cout<<"輸出鄰接矩陣:"<<endl;
Print(G);
cout<<"深度優先搜索:";
DFS(G,0);
cout<<endl;
memset(visited,0,sizeof(visited));//非常重要！！在下一個搜索之前一定要將標志位全部重新賦值為0
cout<<"廣度優先搜索:";
BFS(G,0);
cout<<endl;
return 0;
}
⑦ 怎麼用C語言將鄰接矩陣轉化為可達矩陣 （急）
第一步，二重循環：鄰接矩陣+單位矩陣
for i=0 to shangxian (i++)
for j=0 to shangxian (j++)
if i=j then a[i,j]=a[i,j]+1(單位矩陣對角線上的值為1)
nextj,i
第二步，所得矩陣和自身相乘（二重循環）。矩陣乘法需要些好多字，就不寫了，相信你知道，至少也應該能查到。
第三步，相乘後得到的矩陣和為相乘前的矩陣比較，（也是二重循環）。如相等則完事，否則重復執行第二、三步。
如果自動執行二、三的相乘和比較過程，則需要在外面加一層條件循環。
⑧ 用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;
}