『壹』 c語言 圖 鄰接矩陣 深度優先遍歷 DFS搜索
DFS(g,j);
DFSL(ga,p->adjvex);
除了上面兩句話，其他沒什麼問題，首先如果圖不連通，當你用從某一點遍歷的方法，本身就沒辦法遍歷整個圖
『貳』 用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語言 鄰接矩陣和鄰接表
/**********************鄰接矩陣*****************/
#include<bits/stdc++.h>//鄰接矩陣
using namespace std;
const int N=300;
int Map[N][N]={0};//鄰接矩陣
int book[N]={0};//結點標記數組(1表示該點訪問過了;0未訪問過)
int n,m;
void dfs(int x)//深度遍歷
{
for(int i=1;i<=n;i++)
{//book[i]==0:i未被訪問過
// Map[x][i]==1：x到i有邊連接
if(book[i]==0&&Map[x][i]==1)
{
book[i]=1;//訪問標記
printf("->[%d]",i);
dfs(i);//前往下一個結點i
}
}
}
void bfs(int x)
{
int q[N]={0};
int fornt=0;
int rear=0;
q[rear++]=x;//源點入隊
while(fornt<rear)
{
int k=q[fornt++];//出隊
for(int i=1;i<=n;i++)
{//擴展一個點周圍可以訪問的點
if(book[i]==0&&Map[k][i]==1)
{
printf("->[%d]",i);
book[i]=1;//訪問標記
q[rear++]=i;//入隊
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);//n個結點，m條邊
for(int i=0;i<m;i++)
{//構造無向圖
int x,y;//輸入2個結點;x->y;y->x;
scanf("%d%d",&x,&y);
Map[x][y]=1;//1代表x，y鄰接
Map[y][x]=1;
}
book[1]=1;//標記結點1
printf("深度遍歷路徑 [%d]",1);
dfs(1);//從結點1深度遍歷 (起始點可以隨便選,1~n)
printf(" ");
memset(book,0,sizeof(book));//標記數組置0，用於廣度遍歷標記
printf("廣度遍歷路徑 [%d]",1);
book[1]=1;//標記結點1
bfs(1);//從結點1廣度遍歷 (起始點可以隨便選,1~n)
return 0;
}
/*5個結點,7條邊
5 7
1 3
1 2
1 4
2 4
2 5
3 5
4 5
*/
/*************************鄰接表*************************************/
#include<bits/stdc++.h>//萬能頭文件，C/C++都能用,包含了所有的頭文件
using namespace std;//鄰接表
const int N=300;
typedef struct st{
int v;//表頭能到達的結點
struct st *next;//指向下一個結點的指針域
}*link,AK;//定義結點類型
struct sx{
AK *next;//表頭指針域
}s[N];//n個結點,n個表頭
int book[N]={0};//結點標記數組(1表示該點訪問過了;0未訪問過)
int n,m;
void create(int x,int y)
{//前插法構建鄰接表
link p;
p=new AK;//開辟新結點
p->v=y;
p->next=s[x].next;
s[x].next=p;
}
void fun()
{//表頭指針賦空(這一步至關重要,沒有這一步無法建表)
for(int i=1;i<=n;i++)
s[i].next=NULL;
}
void dfs(int x)//深度遍歷鄰接表
{
link p=s[x].next;
while(p)
{
if(book[p->v]==0)
{
printf("->[%d]",p->v);
book[p->v]=1;
dfs(p->v);
}
p=p->next;
}
}
void bfs(int x)//廣度遍歷鄰接表
{
int q[N]={0};//隊列
int fornt=0;
int rear=0;
q[rear++]=x;
while(fornt<rear)
{
int k=q[fornt++];
link p=s[k].next;
while(p)
{
if(book[p->v]==0)
{
printf("->[%d]",p->v);
book[p->v]=1;
q[rear++]=p->v;
}
p=p->next;
}
}
}
void input()//列印鄰接表
{//首列是表頭(其後尾隨的是與其鄰接的結點)
//n個表頭
link p;
for(int i=1;i<=n;i++)
{
p=s[i].next;
printf("[%d]",i);
while(p)
{
printf("->[%d]",p->v);
p=p->next;
}
cout<<endl;
}
}
int main()
{
fun();//調用表頭置空
scanf("%d%d",&n,&m);//n個結點，m條邊
for(int i=0;i<m;i++)
{//構造無向鄰接表
int x,y;//輸入2個結點;x->y;y->x;
scanf("%d%d",&x,&y);
create(x,y);//構建有向鄰接表，只調用一個;
create(y,x);//構建無向鄰接表，只調用兩個;
}
book[1]=1;//標記結點1
printf("深度遍歷路徑 [%d]",1);
dfs(1);//從結點1深度遍歷 (起始點可以隨便選,1~n)
printf(" ");
memset(book,0,sizeof(book));//標記數組置0，用於廣度遍歷標記
printf("廣度遍歷路徑 [%d]",1);
book[1]=1;//標記結點1
bfs(1);//從結點1廣度遍歷 (起始點可以隨便選,1~n)
printf(" ");
printf("列印鄰接表結構 ");
input();//列印鄰接表
return 0;
}
/*5個結點,7條邊
5 7
1 3
1 2
1 4
2 4
2 5
3 5
4 5
*/
『伍』 數據結構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語言運用鄰接矩陣求最短路徑中的最長路徑問題
同問、
『柒』 計算機C語言題目，已知賦權無向圖，畫鄰接矩陣和鄰接表。還有最小支撐樹
所要求賦權無向圖的鄰接矩陣和鄰接表，還有最小支撐樹見下圖：
『捌』 怎麼用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語言中圖鄰接矩陣0 和1 是咋弄的 我沒看懂
1表示想通，0表示不相通。
這里是讓你理解。無向圖有對稱性。有向圖則沒有。
以後你做題題目會直接給你矩陣不是給你圖讓你生成。
後面你會學到>1的 ，那種要求最短路的就是有權值的了。