/*
Author:Albert Tesla Wizard
Time:2020/10/26 20:22
*/
#include<bits/stdc++.h>
#define OK 1
#define Infinity INT_MAX
#define Error -1
const int MAXSIZE=20;
using namespace std;
typedef enum{DG,UDG,DN,UDN}Graphtype;
typedef int TypeElement;
struct Graph
{
int vertexnum;
int arcnum;
TypeElement arc[MAXSIZE][MAXSIZE];
char vertex[MAXSIZE];
Graphtype type;
};
//找到顶点v在图中的位置
int Locate(char v,Graph&G)
{
for(int i=1;i<=G.vertexnum;i++)
{
if(v==G.vertex[i])return i;
}
return -1;
}
//创建图G
void create(Graph&G)
{
cout<<"请输入图的类型:0.有向图 1.无向图 2.有向网 3.无向网"<<endl;
int type,v1,v2;
char c1,c2;
cin>>type;
if(type==DG)
{
G.type=DG;
}
else if(type==UDG)
{
G.type=UDG;
}
else if(type==DN)
{
G.type=DN;
}
else if(type==UDN)
{
G.type=UDN;
}
cout<<"请输入图的顶点数目:"<<endl;
cin>>G.vertexnum;
cout<<"请输入图的弧的数目:"<<endl;
cin>>G.arcnum;
cout<<"请输入各个顶点的值:"<<endl;
for(int i=1;i<=G.vertexnum;i++)cin>>G.vertex[i];
if(G.type==DG||G.type==UDG)
{
for(int i=1;i<=G.vertexnum;i++)
for(int j=1;j<=G.vertexnum;j++)G.arc[i][j]=0;
}
else if(G.type==DN||G.type==UDN)
{
for(int i=1;i<=G.vertexnum;i++)
for(int j=1;j<=G.vertexnum;j++)G.arc[i][j]=INT_MAX;
}
for(int i=1;i<=G.arcnum;i++)
{
cout<<"请输入各条弧的两个节点v1,v2:"<<endl;
cin>>c1>>c2;
v1=Locate(c1,G);
v2=Locate(c2,G);
if(G.type==DG)
{
G.arc[v1][v2]=1;
}
else if(G.type==UDG)
{
G.arc[v1][v2]=G.arc[v2][v1]=1;
}
else if(G.type==DN)
{
cout<<"请输入该边的权值:"<<endl;
int weight;
cin>>weight;
G.arc[v1][v2]=weight;
}
else if(G.type==UDN)
{
cout<<"请输入该边的权值:"<<endl;
int weight;
cin>>weight;
G.arc[v1][v2]=weight;
G.arc[v2][v1]=G.arc[v1][v2];
}
}
}
void print(Graph&G)
{
if(G.type==DG)cout<<"图的类型:有向图"<<endl;
else if(G.type==UDG)cout<<"图的类型:无向图"<<endl;
else if(G.type==DN)cout<<"图的类型:有向网"<<endl;
else if(G.type==UDN)cout<<"图的类型:无向网"<<endl;
cout<<"图的顶点数目:"<<G.vertexnum<<endl;
cout<<"图的弧的数目:"<<G.arcnum<<endl;
cout<<"图的顶点集合:";
for(int i=1;i<=G.vertexnum;i++)cout<<G.vertex[i]<<" ";
cout<<endl;
cout<<"图的邻接矩阵:"<<endl;
bool flag=true;
for(int i=1;i<=G.vertexnum;i++)
{
for(int j=1;j<=G.vertexnum;j++)
{
if(flag){flag=false;cout<<G.arc[i][j];}
else {cout<<setw(4)<<G.arc[i][j]<<" ";}
}
flag=true;
cout<<endl;
}
}
//根据顶点在图中的相对位置返回顶点的值
char GetVertex(int index,Graph&G)
{
if(index<=G.vertexnum)return G.vertex[index];
}
//对顶点v重新赋值
int putVertex(char v,char v1,Graph&G)//v为图中原有的顶点值,v1为新的顶点值
{
int k=Locate(v,G);
if(k!=-1)
{
G.vertex[k]=v1;
}
return OK;
}
//找到顶点v的第一个邻接点
int firstadjacent(char v,Graph&G)
{
if(G.type==DG||G.type==UDG)
{
int k=Locate(v,G);
for(int j=1;j<=G.vertexnum;j++)
if(G.arc[k][j]!=0)return j;
}
else if(G.type==DN||G.type==UDN)
{
int k=Locate(v,G);
for(int j=1;j<=G.vertexnum;j++)
if(G.arc[k][j]!=Infinity)return j;
}
return -1;
}
//w是v的邻接顶点,找到v相对于w的下一个邻接顶点
int nextadjacent(char v,char w,Graph&G)
{
int k1=Locate(v,G);
int k2=Locate(w,G);
if(G.type==DG||G.type==UDG)
{
for(int j=k2+1;j<=G.vertexnum;j++)
{
if(G.arc[k1][j]!=0)return j;
}
}
else if(G.type==DN||G.type==UDN)
{
for(int j=k2+1;j<=G.vertexnum;j++)
{
if(G.arc[k1][j]!=Infinity)return j;
}
}
return -1;
}
//在图中插入一个新的顶点
int Insert(char v,Graph&G)
{
G.vertex[G.vertexnum+1]=v;
if(G.type==DG||G.type==UDG)
{
for(int i=1;i<=G.vertexnum+1;i++)
{
G.arc[i][G.vertexnum+1]=G.arc[G.vertexnum+1][i]=0;
}
}
else if(G.type==DN||G.type==UDN)
{
for(int i=1;i<=G.vertexnum+1;i++)
{
G.arc[i][G.vertexnum+1]=G.arc[G.vertexnum+1][i]=Infinity;
}
}
G.vertexnum+=1;
}
//在图中删除一个顶点及与它相关联的边
int Delete(char v,Graph&G)
{
int k=Locate(v,G);
if(k==-1)return Error;
for(int i=1;i<=G.vertexnum-1;i++)G.vertex[i]=G.vertex[i+1];
for(int i=1;i<=G.vertexnum;i++)
for(int j=1;j<=G.vertexnum-1;j++)
G.arc[i][j]=G.arc[i][j+1];
for(int i=1;i<=G.vertexnum-1;i++)
for(int j=1;j<=G.vertexnum;j++)
G.arc[i][j]=G.arc[i+1][j];
G.vertexnum--;
}
//在图中插入一条弧
int Insertarc(char v,char w,Graph&G)
{
int k1=Locate(v,G);
int k2=Locate(w,G);
if(k1<0||k2<0)return Error;
if(G.type==DG)
{
G.arc[k1][k2]=1;
}
else if(G.type==UDG)
{
G.arc[k1][k2]=G.arc[k2][k1]=1;
}
else if(G.type==DN)
{
int weight;
cout<<"请输入该边的权值:"<<endl;
cin>>weight;
G.arc[k1][k2]=weight;
}
else if(G.type==UDN)
{
int weight;
cout<<"请输入该边的权值:"<<endl;
cin>>weight;
G.arc[k1][k2]=G.arc[k2][k1]=weight;
}
G.arcnum++;
}
//在图中删除一条弧
int Deletearc(char v,char w,Graph&G)
{
int k1=Locate(v,G);
int k2=Locate(w,G);
if(k1<0||k2<0)return Error;
if(G.type==DG)
{
G.arc[k1][k2]=0;
}
else if(G.type==UDG)
{
G.arc[k1][k2]=G.arc[k2][k1]=0;
}
else if(G.type==DN)
{
G.arc[k1][k2]=Infinity;
}
else if(G.type==UDN)
{
G.arc[k1][k2]=G.arc[k2][k1]=Infinity;
}
G.arcnum--;
}
bool visited[MAXSIZE];
int DFS(int index,Graph&G)
{
visited[index]=true;
cout<<G.vertex[index]<<" ";
char v=GetVertex(index,G);
for(index=firstadjacent(v,G);index!=-1;index=nextadjacent(v,GetVertex(index,G),G))
if(!visited[index])DFS(index,G);
return OK;
}
int DFS1(int index,Graph&G)
{
visited[index]=true;
cout<<G.vertex[index]<<" ";
for(int i=1;i<=index;i++)
{
if(G.arc[index][i]!=0&&!visited[i])DFS1(i,G);
}
}
//深度优先遍历图中顶点
int DFStraverse(Graph&G)
{
for(int i=1;i<=G.vertexnum;i++)visited[i]=false;
for(int i=1;i<=G.vertexnum;i++)
if(!visited[i])DFS1(i,G);
cout<<endl;
return OK;
}
//广度优先遍历图中顶点
int BFStraverse(Graph&G)
{
char v;
queue<char>Q;
for(int i=1;i<=G.vertexnum;i++)visited[i]=false;
for(int i=1;i<=G.vertexnum;i++)
if(!visited[i])
{
visited[i]=true;
cout<<G.vertex[i]<<" ";
v=G.vertex[i];
Q.push(v);
while(!Q.empty())
{
v=Q.front();
Q.pop();
for(int index=firstadjacent(v,G);index!=-1;index=nextadjacent(v,GetVertex(index,G),G))
if(!visited[index])
{
visited[index]=true;
cout<<G.vertex[index]<<" ";
Q.push(G.vertex[index]);
}
}
}
cout<<endl;
}
int main()
{
Graph G;
create(G);
print(G);
cout<<"深度遍历:"<<endl;
DFStraverse(G);
cout<<"广度遍历:"<<endl;
BFStraverse(G);
return 0;
}以上就是 直播短视频源码，邻接矩阵实现图的相关代码，更多内容欢迎关注之后的文章
