本文目录一览：
- 1、用python实现邻接矩阵转换为邻接表，python语言实现
- 2、请编写一个完整的程序，建立有向图的邻接表存储结构，要求：
- 3、邻接表 判断有向图是否有环 python
- 4、如何用邻接表存储图结构
用python实现邻接矩阵转换为邻接表，python语言实现
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C','G','H'],
'E': ['F'],
'F': ['C']}
#从图中找出任意一条从起始顶点到终止顶点的路径
def find_path(graph, start, end, path=[]):
if start == end:
print "path", path
return True
if not graph.get(start):
path.pop()
return False
for v in graph:
if v not in path:
path.append(v)
if find_path(graph,v,end,path):
return True
return False
path = []
if find_path(graph, 'A', 'C', path=path):
print(path)
else:
print(1)
#从图中找出从起始顶点到终止顶点的所有路径
import copy
def find_path_all(curr, end, path):
'''
:param curr: 当前顶点
:param end: 要到达的顶点
:param path: 当前顶点的一条父路径
:return:
'''
if curr == end:
path_tmp = copy.deepcopy(path)
path_all.append(path_tmp)
return
if not graph.get(curr):
return
for v in graph[curr]:
#一个顶点在当前递归路径中只能出现一次，否则会陷入死循环。
if v in path:
print("v %s in path %s" %(v, path))
continue
#构造下次递归的父路径
path.append(v)
find_path_all(v,end,path)
path.pop()
path_all = []
find_path_all('A', 'G',path=['A'])
print path_all
#遍历图中所有顶点，按照遍历顺序将顶点添加到列表中
vertex = []
def dfs(v):
if v not in graph:
return
for vv in graph[v]:
if vv not in vertex:
vertex.append(vv)
dfs(vv)
for v in graph:
if v not in vertex:
vertex.append(v)
dfs(v)
print(vertex)
请编写一个完整的程序，建立有向图的邻接表存储结构，要求：
给你一个邻接表的完整程序：
#include iostream.h
struct node
{
int data;
node *next;
};
class list
{
public:
list(){head=NULL;};
void MakeEmpty();
int Length();
void Insert(int x,int i);//将x插入到第i个结点（不含头结点）的之后
void Insertlist(int a,int b);//将节点b插入a之前
int Delete(int x);
int Remove(int i);
int Find(int x);
void Display();
private:
node *head;
};
void list::Display()
{
node *current=head;
while (current!=NULL)
{
coutcurrent-data" ";
current=current-next;
}
coutendl;
}
void list::MakeEmpty()
{
head=NULL;
}
int list::Length()
{int n=1;
node *q=head;
if(q==NULL)
n=1;
else
while(q!=NULL)
{
n++;
q=q-next;
}
return n;
}
int list::Find(int x)//在链表中查找数值为x的结点，成功返回1，否则返回0
{
node *p=head;
while(p!=NULLp-data!=x)
p=p-next;
if(p-data==x)
return 1;
else
return 0;
}
void list::Insert (int x,int i)//将x插入到第i个结点（不含头结点）的之后；
{
node *p;//p中放第i个结点
node *q;//q中放i后的结点
node *h;//h中存要插入的结点
h=new node;
h-data =x;
p=head;
if(p-next !=NULL) //链表不是只有一个结点或者空链表时候
{
int n=1;
while(p-next !=NULL)
{
n++;
p=p-next ;
}// 得到链表的结点的个数
p=head;//使p重新等于链首
if(i==n)//i=n时，直接加在最后面就行了
{
while(p-next !=NULL)
p=p-next;
p-next=h;
h-next =NULL;
}
else if(ini1)//先找到第i个结点，用p存第i个结点，用q存i后的结点，用h存要插入的结点
{
for(int j=1;ji;j++)
p=p-next;//找到第i个结点，用p存第i个结点
q=p-next;//q存i后的结点
p-next=h;
h-next=q;
}
else
cout"超出链表结点个数的范围"endl;
}
else
cout"这个链表是空链表或者结点位置在首位"endl;
}
void list::Insertlist(int a,int b)//将b插入到结点为a之前
{
node *p,*q,*s;//p所指向的结点为a,s所指为要插入的数b,q所指向的是a前的结点
s=new node;
s-data=b;
p=head;
if(head==NULL)//空链表的时候
{
head=s;
s-next=NULL;
}
else
if(p-data==a)//a在链首时候
{
s-next=p;
head=s;
}
else
{
while(p-data!=ap-next!=NULL)//使p指向结点a,q指向a之前的结点
{
q=p;
p=p-next;
}
if(p-data==a)//若有结点a时候
{
q-next=s;
s-next=p;
}
else//没有a的时候
{
p-next=s;
s-next=NULL;
}
}
}
int list::Delete(int x)//删除链表中值为x的结点，成功返回1，否则返回0；
{
node *p,*q;
p=head;
if(p==NULL)
return 0;
if(p-data==x)
{
head=p-next;
delete p;
return 1;
}
else
{
while(p-data!=xp-next!=NULL)
{ q=p;
p=p-next;
}
if(p-data==x)
{
q-next =p-next;
delete p;
return 1;
}
else
return 0;
}
}
int list::Remove(int i)
{
node *p,*q;
p=head;
if(p!=NULL)
{ int n=1;
while(p-next !=NULL)
{
n++;
p=p-next ;
}//得到链表结点的个数
p=head;
if(i==n)//i结点在结尾的时候
{
while(p-next!=NULL)
{
q=p;
p=p-next;
}
q-next=NULL;
delete p;
return 1;
}
else if(ini1)//i结点在中间的时候
{
for(int j=1;ji;j++)
{
q=p;//q中放i前的结点
p=p-next ;//p中放第i个结点
}
q-next=p-next;
delete p;
return 1;
}
else if(i==1)//i结点在首位的时候
{
q=p-next;
head=q;
delete p;
return 1;
}
else
return 0;
}
else
return 0;
}
void main()
{
list A;
int data[10]={1,2,3,4,5,6,7,8,9,10};
A.Insertlist(0,data[0]);
for(int i=1;i10;i++)
A.Insertlist(0,data[i]);
A.Display();
menu:cout"1.遍历链表"'\t'"2.查找链表"'\t'"3.插入链表"endl;
cout"4.删除链表"'\t'"5.链表长度"'\t'"6.置空链表"endl;
int m;
do
{
cout"请输入你想要进行的操作（选择对应操作前面的序号）："endl;
cinm;
}while(m1||m6);//当输入的序号不在包括中，让他重新输入
switch(m)
{
case 1:
{
A.Display ();
goto menu;
};break;
case 2:
{
cout"请输入你想要找到的结点："endl;
int c;
cinc;//输入你想要找到的结点
if(A.Find (c)==1)
{
cout"可以找到"cendl;
A.Display ();//重新显示出链表A
}
else
{
cout"链表中不存在"cendl;
A.Display ();//重新显示出链表A
}
goto menu;
};break;
case 3:
{
cout"请选择你要插入的方式(选择前面的序号进行选择）"endl;
cout"1.将特定的结点加入到特定的结点前"'\t'"2.将特定的结点加到特定的位置后"endl;
int b1;
do
{
cout"请输入你想要插入的方式（选择前面的序号进行选择）："endl;
cinb1;
}while(b11||b12);//当输入的序号不在包括中，让他重新输入
if(b1==1)
{
cout"请输入你想要插入的数和想要插入的结点（为此结点之前插入）："endl;
int a1,a2;
cina1a2;
A.Insertlist (a1,a2);//将a1插入到结点为a2结点之前
cout"此时链表为："endl;
A.Display ();//重新显示出链表A
}
else
{
cout"请输入你想要插入的数和想要插入的位置（为此结点之后插入）："endl;
int a1,a2;
cina1a2;
A.Insert (a1,a2);//将a1插入到结点位置为a2的结点之后
cout"此时链表为："endl;
A.Display ();//重新显示出链表A
}
goto menu;
};break;
case 4:
{
cout"请选择你要删除的方式(选择前面的序号进行选择）"endl;
cout"1.删除特定的结点"'\t'"2.删除特定位置的结点"endl;
int b1;
do
{
cout"请输入你想要插入的方式（选择前面的序号进行选择）："endl;
cinb1;
}while(b11||b12);//当输入的序号不在包括中，让他重新输入
if(b1==1)
{
cout"请输入你想要删除的结点："endl;
int a;
cina;//输入你想要删除的结点
if(A.Delete (a)==1)
{
cout"成功删除"aendl;
cout"删除后的链表为："endl;
A.Display ();
}
else
{
cout"此链表为："endl;
A.Display ();//重新显示出链表A
cout"链表中不存在"aendl;
}
}
else
{
cout"请输入你想要删除的结点位置："endl;
int b;
cinb;//输入你想要删除的结点的位置
if(A.Remove(b)==1)
{
cout"成功删除第"b"个结点"endl;
cout"删除后的链表为："endl;
A.Display ();//重新显示出链表A
}
else
{
cout"当前链表的结点个数为："A.Length ()endl;
cout"您输入的结点位置越界"endl;
}
}
goto menu;
};break;
case 5:
{
cout"这个链表的结点数为:"A.Length ()endl;
goto menu;
};break;
case 6:
{
A.MakeEmpty ();
cout"这个链表已经被置空"endl;
goto menu;
};break;
}
}
评论(3)|1
sunnyfulin |六级采纳率46%
擅长：C/C++JAVA相关Windows数据结构及算法百度其它产品
按默认排序|按时间排序
其他1条回答
2012-04-23 17:41121446881|六级
我写了一个C语言的，只给你两个结构体和一个初始化函数：
#include "stdio.h"
#include "malloc.h"
struct adjacentnext//邻接表项结构体
{
int element;
int quanvalue;
struct adjacentnext *next;
};
struct adjacenthead//邻接表头结构体
{
char flag;
int curvalue;
int element;
struct adjacenthead *previous;
struct adjacentnext *son;
};
//初始化图，用邻接表实现
struct adjacenthead *mapinitialnize(int mapsize)
{
struct adjacenthead *ahlists=NULL;
struct adjacentnext *newnode=NULL;
int i;
int x,y,z;
ahlists=malloc(sizeof(struct adjacenthead)*mapsize);
if(ahlists==NULL)
return NULL;
for(i=0;imapsize;i++)
{
ahlists[i].curvalue=0;
ahlists[i].flag=0;
ahlists[i].previous=NULL;
ahlists[i].son=NULL;
ahlists[i].element=i+1;
}
scanf("%d%d%d",x,y,z);//输入源结点，目的结点，以及源结点到目的结点的路权值
while(x!=0y!=0)//x,y至少有一个零就结束
{
newnode=malloc(sizeof(struct adjacentnext));
newnode-element=y;
newnode-quanvalue=z;
newnode-next=ahlists[x-1].son;
ahlists[x-1].son=newnode;
scanf("%d%d%d",x,y,z);
}
return ahlists;//返回邻接表头
}
邻接表 判断有向图是否有环 python
邻接表还是逆邻接表看如果是逆邻接表，每个顶点出发邻接表的链表中的结点个数就是入度
如果是邻接表过程如下：
有一个辅助数组，大小就是顶点数量，所有元素初值都为0
从头到尾遍历每个顶点出发的邻接表的结点，只要当前结点的数据是几（也就是第几个结点被有向弧进入了），这个下标的辅助数组元素加1，等所有的邻接表的小链表遍历完了，这个辅助数组中各个下标的数字就是该顶点的入度
如何用邻接表存储图结构
我看不太懂这个程序，不过我有些过图的邻接表表示，看对你有没有帮助吧。
#include iostream
#include fstream
#include vector
typedef int QElemTyep;
#include "queue.h"
using namespace std;
typedef int Status;
#define MAX_VERTEX_NUM 30 //图的最大顶点数
enum BOOL {False,True};
BOOL visited[MAX_VERTEX_NUM]; //全局变量--访问标志数组
typedef struct ArcNode{
//弧结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info; //保存边的信息，可以简单的改为 int w;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
class Graph{
public: AdjList vertices; //记录顶点信息，指向第一条依附该顶点的弧的指针
int vexnum,arcnum; //图的当前顶点和弧数
int GraphKind; //图的种类，0---无向图，1---有向图
Graph(int vexnum,int arcnum,int kind)
{
this-vexnum=vexnum;
this-arcnum=arcnum;
this-GraphKind=kind;
}
};
void CreateGraph(Graph G,VertexType *V,ArcType *VR){
//构造邻接表结构的图G
int i;
ArcNode *s;
for(i=1;i=G.vexnum;i++) //初始化指针数组
{
G.vertices[i].data=V[i];
G.vertices[i].firstarc=NULL;
}
for(i=1;i=G.arcnum;i++)
{
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个弧结点
s-nextarc=G.vertices[VR[i].start].firstarc; //插入到邻接表中
s-adjvex=VR[i].end;
G.vertices[VR[i].start].firstarc=s;
if(G.GraphKind==0) {
//若是无向图，再插入到终点的弧链中
s=(ArcNode *)malloc(sizeof(ArcNode));
s-nextarc=G.vertices[VR[i].end].firstarc;
s-adjvex=VR[i].start;
G.vertices[VR[i].end].firstarc=s;
}
}
}
