c鄰接矩陣存儲
⑴ 數據結構C語言版 圖的遍歷 DFS和BFS演算法，用鄰接矩陣儲存 急阿在線等 求大神指點
#include <iostream>
#include<string.h>
#include<stack>
#include<queue>
const int Max=100;
const int VISITED=101010;
const int UNVISITED=111111;
const int AFFINITY=101010;
const int INFINITY=111111;
using namespace std;
class Edge
{
public:
int start;
int end;
int weight;
Edge(int st=0,int en=0,int w=0):start(st),end(en),weight(w){}
bool operator>(Edge oneEdge){return weight>oneEdge.weight?true:false;}
bool operator<(Edge oneEdge){return weight<oneEdge.weight?true:false;}
bool operator!=(Edge oneEdge)
{
if(weight!=oneEdge.weight||start!=oneEdge.start||end!=oneEdge.end)
return true;
return false;
}
};
class AdjGraf
{
private:
int verticesNum;
int edgeNum;
int **matrix;
int *Mark;
public:
AdjGraf(int vert)
{
int i=0,j=0;
verticesNum=vert;
matrix=(int**)new int*[vert];
for(i=0;i<vert;i++)
matrix[i]=new int[vert];
Mark=new int[vert];
for(i=0;i<vert;i++)
for(j=0;j<vert;j++)
{
matrix[i][j]=0;
}
for( int m=0;m<verticesNum;m++)
Mark[m]=UNVISITED;
}
~AdjGraf();
//返回與頂點oneVertex相關聯的第一條邊
Edge FirstEdge(int oneVertex);
//返回與邊PreEdge有相同關聯頂點oneVertex的下一條邊
Edge NextEdge( Edge preEdge);
//添加一條邊
void setEdge(int fromVertex,int toVertex,int weight);
//刪一條邊
void delEdge(int fromVertex,int toVertex);
//如果oneEdge是邊則返回TRUE，否則返回FALSE
bool IsEdge( Edge oneEdge)
{
if(oneEdge.start>=0&&oneEdge.start<verticesNum&&
oneEdge.end>=0&&oneEdge.end<verticesNum)
return true;
else return false;
}
//返回邊oneEdge的始點
int FromVertex(Edge oneEdge){return oneEdge.start;}
//返回邊oneEdge的終點
int ToVertex(Edge oneEdge){return oneEdge.end;}
//返回邊oneEdge的權
int Weight(Edge oneEdge){return oneEdge.weight;}
void visit(int i){cout<<i+1<<" ";}
void BFS(int i=1);
void DFS(int i);
void DFSTraverse(int v);
void DFSNoReverse(int f=1);
Edge UNVISITEDEdge(int f);
};
AdjGraf::~AdjGraf()
{
for(int i=0;i<verticesNum;i++)
delete[]matrix[i];
delete[]matrix;
}
Edge AdjGraf::FirstEdge(int oneVertex)
{ int i;
Edge tempEdge;
tempEdge.start=oneVertex;
for( i=0;i<verticesNum;i++)
if(matrix[oneVertex][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[oneVertex][i];
return tempEdge;
}
Edge AdjGraf ::NextEdge( Edge preEdge)
{
Edge tempEdge;
tempEdge.start=preEdge.start;
int i=0;
for(i=preEdge.end+1;i<verticesNum;i++)
if(matrix[preEdge.start][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[preEdge.start][i];
return tempEdge;
}
void AdjGraf::setEdge(int fromVertex,int toVertex,int weight)
{
if(matrix[fromVertex-1][toVertex-1]==0)
edgeNum++;
matrix[fromVertex-1][toVertex-1]=weight;
}
void AdjGraf::delEdge(int fromVertex,int toVertex)
{
if(matrix[fromVertex][toVertex]==0)
edgeNum--;
matrix[fromVertex][toVertex]=0;
}
/*************遞歸實現深度優先****************/
void AdjGraf::DFS(int i)
{
visit(i);
Mark[i]=VISITED;
for(Edge e=FirstEdge(i);IsEdge(e);e=NextEdge(e))
if(Mark[ToVertex(e)] == UNVISITED)
DFS(ToVertex(e));
}
void AdjGraf::DFSTraverse(int v)
{
v--;
int i;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
for(i=v;i<v+verticesNum;i++)
if (Mark[i]== UNVISITED)
DFS(i);
}
Edge AdjGraf::UNVISITEDEdge(int f)
{ int i;
for( Edge e=FirstEdge(f);IsEdge(e);e=NextEdge(e))
if(Mark[e.end]==UNVISITED)
return e;
return Edge(verticesNum,verticesNum,0) ;
}
/*************非遞歸實現深度優先**************/
void AdjGraf::DFSNoReverse(int f)
{
f--;
int i,counter=0,j,flag;
stack<int>Temp;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
flag=f;
while(counter<12)
{
while(flag!=verticesNum&&IsEdge(UNVISITEDEdge(flag))||!Temp.empty())
{
// Edge tempEdge=UNVISITEDEdge(j);
while(flag!=verticesNum&&Mark[flag]==UNVISITED)
{
visit(flag);
Mark[flag]=VISITED;
Temp.push(flag);
flag=UNVISITEDEdge(flag).end;
}
if(!Temp.empty())
{
flag=UNVISITEDEdge(Temp.top()).end;
Temp.pop();
}
}
if(Mark[counter]==UNVISITED) flag=counter;
else counter++;
}
}
/*************非遞歸實現廣度優先**************/
void AdjGraf::BFS(int v)
{
int i;
v--;
for( i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
queue<int>tempqueue;
i=0;
/*********v先從指定位置開始，然後從v=0,1,2......
依次檢查是否有孤立結點*****************/
while(i<verticesNum)
{
tempqueue.push(v);
while(!tempqueue.empty())
{
v=tempqueue.front();
tempqueue.pop();
if(Mark[v]==UNVISITED)
{
visit(v);
Mark[v]=VISITED;
for(Edge e=FirstEdge(v);IsEdge(e);e=NextEdge(e))
{
v=ToVertex(e);
tempqueue.push(v);
}
}
}
/***********防止出現孤立點****************/
if(Mark[i]==VISITED) i++;
else v=i;
}
}
int main()
{
AdjGraf Graph(12);
Graph.setEdge(1,2,1);
Graph.setEdge(2,1,1);
Graph.setEdge(1,3,5);
Graph.setEdge(3,1,5);/** V1 V12 V11 */
Graph.setEdge(2,4,3);/** / \ / \ */
Graph.setEdge(4,2,3);/** v2 v3 V10 V9 */
Graph.setEdge(2,5,7);/** / \ / \ */
Graph.setEdge(5,2,7);/** v4 v5 v6-v7 */
Graph.setEdge(4,8,4);/** \ / */
Graph.setEdge(8,4,4);/** v8 */
Graph.setEdge(5,8,3);
Graph.setEdge(8,5,3);
Graph.setEdge(3,6,2);
Graph.setEdge(6,3,2);
Graph.setEdge(3,7,1);
Graph.setEdge(7,3,1);
Graph.setEdge(6,7,6);
Graph.setEdge(7,6,6);
Graph.setEdge(12,9,6);
Graph.setEdge(9,12,6);
Graph.setEdge(12,10,6);
Graph.setEdge(10,12,6);
Graph.setEdge(11,11,6);
cout<<"DFSTraverse:"<<endl;
Graph.DFSTraverse(3);
cout<<endl;
cout<<"DFSNoReverse:"<<endl;
Graph.DFSNoReverse(3);
cout<<endl;
cout<<"BFS:"<<endl;
Graph.BFS(3);
cout<<endl;
return 0;
}
以上代碼運行環境codeblocks 程序採用DFS遞歸演算法 DFS非遞歸演算法 BFS非遞歸演算法
望採納~
⑵ C語言數據結構演算法，連通圖的深度優先搜索，存儲結構是鄰接矩陣，空怎麼填啊
voiddfs(inta[][],intv,intn)
{
access(v);
visited[v]=1;
w=0;
while(w<=n&&a[v][w]==0)w++;
while(w<=n)
{
if(visited[w]==0)dfs(a,w,n);
w++;
while((w<=n)&&a[v][w]==0)w++;
}
}
第一空：visited[w]==0
第二空：dfs(a,w,n)
⑶ C語言數據結構實現1.有向圖的圖的鄰接矩陣存儲、深度和廣度優先搜索遍歷、拓撲排序求解。
#include"iostream.h"
const int n=8;
const int e=15;
typedef int elemtype ;
bool visited[n+1];
class link
{
public:
elemtype data;
link *next;
};
class graph
{
public:
link a[n+1];
void creatlink()
{
int i,j,k;
link *s;
for(i=1;i<=n;i++)
{
a[i].data=i;
a[i].next=NULL;
}
for(k=1;k<=e;k++)
{
cout<<"請輸入一條邊";
cin>>i>>j;
cout<<endl;
s=new link;
s->data=j;
s->next=a[i].next;
a[j].next=s;
}
}
void dfs1(int i)
{
link *p;
cout<<a[i].data<<" ";
visited[i]=true;
p=a[i].next;
while(p!=NULL)
{
if(!visited[p->data])
dfs1(p->data);
p=p->next;
}
}
void bfs1(int i)
{
int q[n+1];
int f,r;
link *p;
f=r=0;
cout<<a[i].data<<" ";
visited[i]=true;
r++;q[r]=i;
while(f<r)
{
f++;i=q[r];
p=a[i].next;
while(p!=NULL)
{
if(!visited[p->data])
{
cout<<a[p->data].data<<" ";
visited[p->data]=true;
r++;q[r]=p->data;
}
p=p->next;
}
}
}
};
void main()
{
link *p;int yn=1;
graph g;
g.creatlink();
while(yn){
for(int i=1;i<=n;i++)
{
p=g.a[i].next;
cout<<g.a[i].data<<"->";
while(p->next!=NULL)
{
cout<<p->data<<"->";
p=p->next;
}
cout<<p->data<<endl;
}
for(i=1;i<=n;i++)
visited[i]=false;
cout<<"輸入深度優先搜索開始訪問的頂點";
cin>>i;
cout<<endl;
cout<<"從"<<i<<"出發的深度優先搜索遍歷序列為"<<endl;
g.dfs1(i);
cout<<endl;
for(i=1;i<=n;i++)
visited[i]=false;
cout<<"請輸入廣度優先搜索開始訪問的頂點";
cin>>i;
cout<<endl;
cout<<"從"<<i<<"出發的廣度優先搜索遍歷序列為"<<endl;
g.bfs1(i);
cout<<endl;
cout<<"繼續遍歷嗎(1/0)?";
cin>>yn;
}
}
/*圖為：
1 2 3
5 4
6 7 8*/
⑷ 用鄰接矩陣儲存圖，所佔用的儲存空間大小
圖的鄰接矩陣存儲所佔用空間大小隻與頂點個數有關，更准確地說，設頂點n個，則與n^2成正比（n的平方）
⑸ 存儲圖時，哪些情況用鄰接矩陣方便
如果邊比較少的情況下，用鄰接矩陣節省存儲空間。邊比較多就可以選擇鄰接矩陣
⑹ c++利用鄰接矩陣存儲方法實現圖的存儲與輸出。
復制粘貼即可
#include <iostream>
using namespace std;
//*****stack.h
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
template<class QElemType>
class stack
{
public:
void InitStack();
void DestroyStack();
void ClearStack();
Status StackEmpty();
Status StackLength();
void GetTop(QElemType & e);
void Push(QElemType e);
void Pop(QElemType & e);
private:
struct SqStack{
QElemType *base;
QElemType *top;
int stacksize;
}S;
};
//******stack.cpp------
template<class QElemType>
void stack<QElemType>::InitStack()
{
S.base = (QElemType *)malloc(STACK_INIT_SIZE * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
template <class QElemType>
void stack<QElemType>::DestroyStack()
{
free(S.base);
}
template <class QElemType>
void stack<QElemType>::ClearStack()
{
S.top = S.base;
}
template <class QElemType>
Status stack<QElemType>::StackEmpty()
{
if(S.top == S.base) return 1;
else return 0;
}
template <class QElemType>
Status stack<QElemType>::StackLength()
{
return (S.top - S.base);
}
template <class QElemType>
void stack<QElemType>::GetTop(QElemType & e)
{
if(S.top != S.base)
e = *(S.top - 1);
else cout << "ERROR" << endl;
}
template <class QElemType>
void stack<QElemType>::Push(QElemType e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (QElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
}
template <class QElemType>
void stack<QElemType>::Pop(QElemType & e)
{
if(S.top == S.base) cout << "ERROR" << endl;
else
e = * --S.top;
}
//**********stack.cpp End
template <class TElemType>
class Graph
{
public:
void CreateUDN();
void DestroyUDN();
void CreateAlgraph();
void DestroyAlgraph();
void DFS(int v,bool *visited);
void DFSTraverse();
void Minispantree_prim(); //PRIM演算法求最小生成樹
void Shortestpath_DIJ(TElemType data1,TElemType data2); //對環不適用，如從V1到V1就不適用
void Shortestpath_FLOYD(TElemType data1,TElemType data2);
private:
template <class TElemType>
struct Mgraph{
int vexnum;
int arcnum;
TElemType *vertex;
int **AdjMatrix;
};
Mgraph<TElemType> gph; //鄰接矩陣存儲
struct Arcnode
{
int adjvex;
Arcnode *nextarc;
float weight;
};
template <class TElemType>
struct Vexnode
{
TElemType data;
Arcnode *firarc;
};
struct ALgraph
{
int vexnum;
int arcnum;
bool kind;
Vexnode<TElemType> *vex;
};
ALgraph algraph; //鄰接表存儲
};
//*********Graph.cpp
template <class TElemType>
void Graph<TElemType>::CreateUDN()
{
cout << "輸入無向網的頂點數和邊數:" << endl;
cin >> gph.vexnum >> gph.arcnum;
gph.vertex = (TElemType *)malloc(gph.vexnum * sizeof(TElemType));
int i,j,m,n; //m,n表示頂點信息對應的序號，w是權值
int w;
TElemType v1,v2;
cout << "輸入頂點信息:" << endl;
for(i = 0;i < gph.vexnum;i++)
cin >> gph.vertex[i];
gph.AdjMatrix = (int **)malloc(gph.vexnum * sizeof(int *));
for(i = 0;i < gph.vexnum;i++)
gph.AdjMatrix[i] = (int *)malloc(gph.vexnum * sizeof(int));
for(i = 0;i < gph.vexnum;i++)
for(j = 0;j < gph.vexnum;j++)
gph.AdjMatrix[i][j] = INT_MAX; //INT_MAX
cout << "輸入一條邊依附的兩點及權值:" << endl;
for(int k = 0;k < gph.arcnum;k++)
{
cin >> v1 >> v2 >> w;
for(i = 0;i < gph.vexnum;i++)
{
if(v1 == gph.vertex[i]) m = i;
if(v2 == gph.vertex[i]) n = i;
}
gph.AdjMatrix[m][n] = gph.AdjMatrix[n][m] = w;
}
}
template <class TElemType>
void Graph<TElemType>::DestroyUDN()
{
free(gph.vertex);
for(int i = 0;i < gph.vexnum;i++)
free(gph.AdjMatrix[i]);
free(gph.AdjMatrix);
}
template <class TElemType>
void Graph<TElemType>::CreateAlgraph()
{
int i,j,m,n;
float w;
TElemType v1,v2;
Arcnode *p;
cout << "輸入圖類型（1是無向圖，0是有向圖):" << endl;
cin >> algraph.kind;
cout << "輸入頂點數和邊數:" << endl;
cin >> algraph.vexnum >> algraph.arcnum;
algraph.vex = (Vexnode<TElemType> *)malloc(algraph.vexnum * sizeof(Vexnode<TElemType>));
cout << "輸入頂點信息:" << endl;
for(i = 0;i < algraph.vexnum;i++)
{
cin >> algraph.vex[i].data;
algraph.vex[i].firarc = NULL;
}
if(algraph.kind)
{
cout << "輸入各邊依附的兩點和權值:" << endl;
for(i = 0;i < algraph.arcnum;i++)
{
cin >> v1 >> v2 >>w;
for(j = 0;j < algraph.vexnum;j++)
{
if(v1 == algraph.vex[j].data) m = j;
if(v2 == algraph.vex[j].data) n = j;
}
p = (Arcnode *)malloc(2*sizeof(Arcnode));
p[0].adjvex = n;p[0].weight = w;
p[1].adjvex = m;p[1].weight = w;
p[0].nextarc = algraph.vex[m].firarc;algraph.vex[m].firarc = p;
p[1].nextarc = algraph.vex[n].firarc;algraph.vex[n].firarc = ++p;
}
}
else
{
cout << "輸入各邊的弧尾與弧頭結點及有向邊的權值:" << endl;
for(i = 0;i < algraph.arcnum;i++)
{
cin >> v1 >> v2 >> w;
for(j = 0;j < algraph.vexnum;j++)
{
if(v1 == algraph.vex[j].data) m = j;
if(v2 == algraph.vex[j].data) n = j;
}
p = (Arcnode *)malloc(sizeof(Arcnode));
p->adjvex = n;p->weight = w;
p->nextarc = algraph.vex[m].firarc;algraph.vex[m].firarc = p;
}
}
} //構造完成
template <class TElemType>
void Graph<TElemType>::DestroyAlgraph()
{
int i;
Arcnode *p,*q;
for(i = 0;i < algraph.vexnum;i++)
{
p = algraph.vex[i].firarc;
if(p)
{
q = p->nextarc;
while(q)
{
free(p);
p = q;
q = q->nextarc;
}
free(p);
}
}
free(algraph.vex);
}
template <class TElemType>
void Graph<TElemType>::DFS(int v,bool *visited)
{
cout << algraph.vex[v].data << endl;
visited[v] = true;
Arcnode *p;
int v1;
for(p = algraph.vex[v].firarc;p;p = p->nextarc)
{
v1 = p->adjvex;
if(!visited[v1]) DFS(v1,visited);
}
}
template <class TElemType>
void Graph<TElemType>::DFSTraverse()
{
int i,v;
bool *visited = (bool *)malloc(algraph.vexnum * sizeof(bool));
for(i = 0;i < algraph.vexnum;i++)
visited[i] = false;
for(v = 0;v < algraph.vexnum;v++)
if(!visited[v]) DFS(v,visited);
free(visited);
} //EndDFSTraverse
template <class TElemType>
void Graph<TElemType>::Minispantree_prim()
{
struct closedge
{
int adjvex;
int lowcost;
};
closedge *edge = (closedge *)malloc(gph.vexnum * sizeof(closedge));
int i,j,k = 0,u;
int min;
for(i = 0;i < gph.vexnum;i++)
{
if(i != k)
{
edge[i].adjvex = 0;
edge[i].lowcost = gph.AdjMatrix[k][i];
}
}
edge[k].lowcost = 0;
cout << "最小生成樹的邊如下:" << endl;
for(i = 1;i < gph.vexnum;i++)
{
min = INT_MAX;
for(j = 0;j < gph.vexnum;j++)
if(edge[j].lowcost != INT_MAX &&edge[j].lowcost != 0 && edge[j].lowcost < min)
{
min = edge[j].lowcost;
k = j;
}
u = edge[k].adjvex;
edge[k].lowcost = 0;
cout << "(" << gph.vertex[u] << "," << gph.vertex[k] << ")" << " ";
for(j = 0;j < gph.vexnum;j++)
if(gph.AdjMatrix[j][k] < edge[j].lowcost)
{
edge[j].lowcost = gph.AdjMatrix[j][k];
edge[j].adjvex = k;
}
}
free(edge);
cout << endl;
}
template <class TElemType>
void Graph<TElemType>::Shortestpath_DIJ(TElemType data1,TElemType data2)
{
int i,j,v,u,k,min;
stack<int> S;
S.InitStack();
int *spath = (int *)malloc(gph.vexnum * sizeof(int));
int *pathrecord = (int *)malloc(gph.vexnum * sizeof(int));
bool *visited = (bool *)malloc(gph.vexnum * sizeof(bool));
for(i = 0;i < gph.vexnum;i++) visited[i] = false;
for(i = 0;i < gph.vexnum;i++)
{
if(data1 == gph.vertex[i]) v = i;
if(data2 == gph.vertex[i]) u = i;
}
for(i = 0;i < gph.vexnum;i++)
{
spath[i] = gph.AdjMatrix[v][i];
pathrecord[i] = v;
}
spath[v] = 0;visited[v] = true;pathrecord[v] = -1;
for(i = 1;i < gph.vexnum;i++)
{
min = INT_MAX;
for(j = 0;j < gph.vexnum;j++)
{
if(!visited[j])
{
if(spath[j] < min) {min = spath[j];k = j;}
}
}
visited[k] = true;
for(j = 0;j < gph.vexnum;j++)
if(!visited[j] && gph.AdjMatrix[k][j] < INT_MAX && spath[k]+gph.AdjMatrix[k][j] < spath[j])
{
spath[j] = spath[k]+gph.AdjMatrix[k][j];
pathrecord[j] = k;
}
}
free(visited);
cout << spath[u] << endl;
S.Push(u);
for(v = pathrecord[u];v != -1;v = pathrecord[v])
S.Push(v);
while(!S.StackEmpty())
{
S.Pop(i);
cout << gph.vertex[i] << " ";
}
cout << endl;
S.DestroyStack();
free(spath);
free(pathrecord);
}
template <class TElemType>
void Graph<TElemType>::Shortestpath_FLOYD(TElemType data1,TElemType data2)
{
int i,j,k,v,u,m;
int **D = (int **)malloc(gph.vexnum * sizeof(int *));
bool ***path = (bool ***)malloc(gph.vexnum * sizeof(bool **));
for(i = 0;i < gph.vexnum;i++)
{
D[i] = (int *)malloc(gph.vexnum * sizeof(int));
path[i] = (bool **)malloc(gph.vexnum * sizeof(bool *));
if(data1 == gph.vertex[i]) v = i;
if(data2 == gph.vertex[i]) u = i;
}
for(i = 0;i < gph.vexnum;i++)
for(j = 0;j < gph.vexnum;j++)
path[i][j] = (bool *)malloc(gph.vexnum *sizeof(bool));
for(i = 0;i < gph.vexnum;i++)
for(j = 0;j < gph.vexnum;j++)
{
D[i][j] = gph.AdjMatrix[i][j];
for(k = 0;k < gph.vexnum;k++)
path[i][j][k] = false;
if(D[i][j] < INT_MAX)
{
path[i][j][i] = true;path[i][j][j] = true;
}
}
for(k = 0;k < gph.vexnum;k++)
for(i = 0;i < gph.vexnum;i++)
for(j = 0;j < gph.vexnum;j++)
if(D[i][k] != INT_MAX && D[k][j] != INT_MAX && D[i][k]+D[k][j] < D[i][j])
{
D[i][j] = D[i][k] + D[k][j];
for(m = 0;m < gph.vexnum;m++)
path[i][j][m] = path[i][k][m] || path[k][j][m];
}
cout << "從" << gph.vertex[v] << "到" << gph.vertex[u] << "的最短路徑及經過的點如下:" << endl;
cout << D[v][u] << endl;
for(i = 0;i < gph.vexnum;i++)
if(path[v][u][i] == true) cout << i << " ";
cout << endl;
for(i = 0;i < gph.vexnum;i++)
{
free(D[i]);
free(path[i]);
}
free(D);
free(path);
}
//***********end Graph
int main()
{
Graph<int> gph;
gph.CreateUDN();
gph.Minispantree_prim();
int data1,data2;
cout << "輸入起點和終點:" << endl;
cin >> data1 >> data2;
gph.Shortestpath_DIJ(data1,data2);
//gph.Shortestpath_FLOYD(data1,data2);
gph.DestroyUDN();
return 0;
}
功能函數都實現了，可以自己在源程序中調用函數實現各種功能。
⑺ C語言。如果兩個頂點之間有多條邊，還可以用鄰接矩陣存儲嗎
可以，如果a到b有1條邊就在矩陣ab位置置1；如果a到b有2條邊就在矩陣ab位置置2；如果a到b有0條邊就在矩陣ab位置置0；
⑻ 數據結構 用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語言 鄰接矩陣和鄰接表
/**********************鄰接矩陣*****************/
#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/c++圖的鄰接矩陣存儲結構
關於圖的深度優先遍歷代碼如下：
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TURE 1
#define OK 1
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20 //最大頂點個數
typedef struct ArcCell{
int adj; //頂點關系類型。用1或0表示相鄰與否
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //二維數組
typedef struct {
char vexs[MAX_VERTEX_NUM]; //頂點向量
AdjMatrix arcs; //鄰接矩陣
int vexnum,arcnum; //頂點數和弧數
}MGraph;
int LocateVex(MGraph G,char u)
{ //若圖G中存在頂點u，則返回該頂點在圖中的位置；否則返回-1
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==u)
return i;
else return -1;
}
int CreateDG(MGraph G){ //構造有向圖G
int i,j,k;
char va,vb;
printf("請輸入有向圖G的頂點數 弧數：");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("請輸入%d個頂點的值(<5個字元)：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) scanf("%s",&G.vexs[i]); //構造頂點向量
for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=0;
}
printf("請輸入%d條弧的弧尾 弧頭：\n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
scanf("%s%s%*c",&va,&vb);
i=LocateVex(G,va);
j=LocateVex(G,vb);
G.arcs[i][j].adj=1;
}
return OK;
}
int FirstAdjVex(MGraph G,char v)
{ //返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點，則返回-1
int i,k;
k=LocateVex(G,v); //k為頂點v在圖G中的序號
for(i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=0)
return i;
else return -1;
return OK;
}
int NextAdjVex(MGraph G,char v,char w)
{ //返回v的相對於（w）的下一個鄰接頂點的序號，若w是v的最後一個鄰接頂點，則返回-1
int i,k1,k2;
k1=LocateVex(G,v); //k1為頂點v在圖G中的序號
k2=LocateVex(G,w); //k2為頂點w在圖G中的序號
for(i=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=0)
return i;
else return -1;
return OK;
}
int visited[MAX_VERTEX_NUM];
int DFS(MGraph G,int v)
{ //從第v個頂點出發遞歸的深度優先遍歷圖G
int w;
visited[v]=TURE; //設置訪問標志為TURE
printf("%s",G.vexs[v]);
for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
if(!visited[w])
DFS(G,w); //對尚未訪問的序號為w的鄰接頂點遞歸的調用DFS
return OK;
}
int DFSTraverse(MGraph G)
{ //從第一個頂點起，深度優先遍歷圖G
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; //訪問標志數組初始化
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); //對尚未訪問的頂點v調用DFS
printf("\n");
return OK;
}
int main()
{
MGraph G;
CreateDG(G);
DFSTraverse(G);
system("pause");
return OK;
}
廣度可以自己參照改寫。。