理解图形基础：邻接矩阵与邻接表的储存与操作方法详解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define maxSize 100
using namespace std;

int Count=0;
const int Max=50;
typedef char type;
bool visited[100] = { false };

typedef struct ///定义数据结构：栈
{
int *top;
int *base;
int Size;
}Stack;

typedef struct ///定义数据结构：队列
{
int *Front;
int *Rear;
int Size;
} Queue;

typedef struct ///定义数据结构：图
{
type vexs[Max];
bool arcs[Max][Max];
int vexnum,arcnum;
} graph;

void InitStack(Stack &s) ///对栈进行初始化
{
if(!(s.top=s.base=(int *)malloc(maxSize*sizeof(int))))
return ;
s.Size=maxSize;
}

void push(Stack &s,int e) ///入栈：将元素e压入栈
{
*s.top=e;
s.top++;
}

void pop(Stack &s) ///出栈：栈顶指针减一
{
if(s.base==s.top)
return ;
s.top--;
}

int top(Stack s) ///返回栈顶元素
{
s.top--;
return *s.top;
}

void InitQueue(Queue &q) ///初始化队列
{
if(!(q.Front=q.Rear=(int *)malloc(maxSize*sizeof(int))))
return ;
q.Size=maxSize;
}

void Q_push(Queue &q,int e) ///入队列：将元素e入队列
{
*q.Rear=e;
q.Rear++;
}

int Q_pop(Queue &q) ///出队列：返回队头元素，队头指针加一
{
int e;
if(q.Front==q.Rear)
return 0;
e=*q.Front;
q.Front++;
return e;
}

void Create(graph *g) ///建立邻接矩阵并输出
{
int i,j;
memset(g->arcs,0,sizeof(g->arcs));
for(i=0; i<g->arcnum; ++i)
{
int x,y;
cin>>x>>y;
g->arcs[x][y]=1;
g->arcs[y][x]=1;
}
cout<<"无向邻接表矩阵为:"<<endl;
for(i=0; i<g->vexnum; i++)
{
for(j=0; j<g->vexnum; j++)
cout<<g->arcs[i][j]<<" ";
cout<<endl;
}
}

void Du(graph *g) ///统计每个顶点的度
{
int i,j;
for(i=0; i<g->vexnum; i++)
{
int amount=0;
for(j=0; j<g->vexnum; ++j)
if(g->arcs[i][j])
++amount;
cout<<"顶点"<<g->vexs[i]<<"的度为"<<amount<<endl;
}
}

void DFS(graph *g,int k) ///DFS深度优先搜索
{
int t,i;
Stack s;
InitStack(s);
cout<<g->vexs[k]<<" ";
visited[k]=true;
push(s,k);
while(s.base!=s.top)
{
t=top(s);
if(i==g->vexnum) ///如果內层循环未找到没被访问的元素，则出栈
pop(s);
for(i=0; i<g->vexnum; i++)
{
if(g->arcs[t][i]==1&&visited[i]==false) ///找出邻接矩阵第t+1行中第一个未被访问的元素
{
visited[i]=true; ///找到后标志为1，并输出，入栈
cout<<g->vexs[i]<<" ";
push(s,i);
break; ///找到之后跳出內层循环，返回外层循环起始处，重复之前操作
}
}
}
}

void BFS(graph *g, int k) ///BFS广度优先搜索
{
Queue q;
InitQueue(q);
visited[k]=true;
cout<<g->vexs[

上一篇： 众智科学揭示：友谊中的悖论现象实证研究

下一篇： 连理工大学数据结构实践课程第四章：Floyd算法实战指南